This repository has been archived by the owner on Apr 22, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1046.html
56 lines (55 loc) · 9.27 KB
/
1046.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
<p><span style="font-family: Courier New">วันหนึ่ง เพื่อนรักของผม โปรเฟสเซอร์ลูนี่ วิ่งกระหืดกระหอบเข้ามาในห้องทำงานของผมแต่เช้า หน้าของเขาแดงกล่ำคล้ายกับเขากำลังโกรธจัด พร้อมกับกล่าวขึ้นว่า "ไอ้พวกผู้ผลิตมือถือเฮงซวยทั้งหลายเอ๊ย นี่ดูซิ ฉันต้องการส่ง SMS แต่ใช้เวลาพิมพ์ข้อความนี่มาสิบกว่านาทีแล้ว" ผมพยายามพูดให้เขาคลายความโกรธลง "อ้าว! ทำไมล่ะ ไม่น่าจะนานขนาดนี้นะ" ลูนี่เสริมต่อทันทีว่า "เห็นมั้ยล่ะว่า เขาจัดวางตัวอักษรในแต่ละปุ่มอย่างไม่เข้าท่าเลย นี่!ตัวอักษร เอส ถูกจัดไว้เป็นตัวที่สี่ของปุ่ม ฉันต้องกดปุ่มเลข 7 ถึงสี่ครั้งจึงจะได้ตัวเอส แล้วอย่างตัว อี ทำไมไม่จัดไว้เป็นตัวแรกของปุ่ม ต้องกดถึงสองครั้งกว่าจะได้ตัวอี นี่มันเป็นการออกแบบโดยไม่ใช้สมองเลยนะเนี่ย"<br />
<br />
"ใจเย็นไว้เพื่อน" ผมกล่าวขึ้น "รูปแบบนี้เขาใช้กันมาตั้งนานแล้ว ก่อนที่จะมีการใช้งาน SMS อีกนะ เขาก็เลยต้องคงไว้แบบนั้นแหละ" <br />
<br />
"นั่นมันเป็นข้อแก้ตัวต่างหาก" ดูเหมือนว่าลูนี่จะโกรธมากขึ้น "ถึงเวลาต้องเปลี่ยนเจ้ารูปแบบการวางตัวอักษรนี่แล้ว อีกอย่างก็คือทำไมต้องวางตัวอักษรไว้แค่ในปุ่มแค่ 8 ปุ่มเท่านั้น ทำไมไม่ใช้ให้ครบทั้ง 12 ปุ่มเลย และก็ทำไมต้องเรียงตัวอักษรด้วย" "ฉันก็...ไม่รู้เหมือนกัน" ผมกล่าวอย่างจนปัญญา<br />
<br />
เขาพูดต่อ "ฉันว่าน่าจะมีใครที่มาปรับปรุงเจ้ารูปแบบการวางตำแหน่งตัวอักษรนี่นะ" ผมคิดว่าลูนี่ก็เหมือนคนทั่ว ๆ ไปที่ชอบบ่น แต่ไม่เห็นเสนอทางแก้ปัญหาที่เป็นไปได้เลย <br />
<br />
ในโจทย์ข้อนี้ พวกเราต้องหาทางช่วยลูนี่แล้วล่ะ ด้วยการหารูปแบบการวางตัวอักษรที่จะช่วยให้ผู้ป้อนข้อความกดปุ่มเป็นจำนวนครั้งที่น้อยที่สุด โดยที่โจทย์จะกำหนดสิ่งต่อไปนี้มาให้ (1) จำนวนของปุ่ม (2) จำนวนสูงสุดของตัวอักษรที่สามารถกำหนดให้กับแต่ละปุ่มได้ (3) จำนวนตัวอักษรที่มีทั้งหมดในภาษานั้น และ (4) ความถี่ที่แต่ละตัวอักษรจะปรากฏอยู่ในข้อความ โดยที่ตัวอักษรใดจะถูกวางอยู่ในปุ่มใด และจะเรียงลำดับในแต่ละปุ่มอย่างใดก็ได้ แต่ละตัวอักษรจะถูกกำหนดให้กับปุ่มใดได้เพียงครั้งเดียวเท่านั้น และอย่าลืมว่าจำนวนตัวอักษรที่มีทั้งหมดในภาษาอาจจะไม่ใช่ 26 ก็ได้ถ้าภาษานั้นไม่ใช่ภาษาอังกฤษ<br />
<br />
ตัวอย่างของการกำหนดตัวอักษรภาษาอังกฤษให้กับปุ่มต่าง ๆ ที่ใช้กันอยู่ คือ<br />
<br />
key 2: abc<br />
key 3: def<br />
key 4: ghi<br />
key 5: jkl<br />
key 6: mno<br />
key 7: pqrs<br />
key 8: tuv<br />
key 9: wxyz<br />
<br />
เมื่อกดปุ่มใดในครั้งแรกจะเป็นการเลือกตัวอักษรตัวแรก และถ้ากดต่อไปอีกจะเป็นการเลือกตัวอักษรตัวถัดไปที่กำหนดไว้สำหรับปุ่มนั้น ๆ ตัวอย่างเช่น ถ้าต้องการพิมพ์คำว่า "SNOW" ต้องกดปุ่ม "7" สี่ครั้ง เพื่อให้ได้ตัวอักษร "S" ตามด้วยปุ่ม "6" สองครั้งเพื่อให้ได้ตัวอักษร "N" ตามด้วยปุ่ม "6" อีกสามครั้งเพื่อให้ได้ตัวอักษร "O" และสุดท้ายตามด้วยปุ่ม "9" หนึ่งครั้งเพื่อให้ได้ตัวอักษร "W" ดังนั้นจำนวนการกดปุ่มทั้งหมดคือ 10 ครั้ง<br />
<br />
<strong><u>ข้อมูลนำเข้า</u></strong><br />
<strong>บรรทัดแรก </strong>ประกอบด้วยจำนวนเต็ม 3 ค่าคั่นด้วยช่องว่างหนึ่งช่อง ตามลำดับดังนี้ จำนวนตัวอักษรมากที่สุดที่สามารถกำหนดให้ได้กับแต่ละปุ่ม (P) จำนวนปุ่มที่มี (K) และจำนวนตัวอักษรที่มีในภาษานั้น (L)<br />
<strong>บรรทัดที่สอง</strong> ประกอบด้วยจำนวนเต็มที่ไม่ติดลบ L ตัว แต่ละตัวหมายถึงความถี่ของแต่ละตัวอักษร นั่นคือ ตัวแรกเป็นจำนวนครั้งที่ตัวอักษรตัวแรกปรากฏในข้อความ ตัวที่สองเป็นจำนวนครั้งที่ตัวอักษรตัวที่สองปรากฏในข้อความ เรื่อย ๆ ไปจนครบ L ตัว <br />
<br />
<strong><u>ข้อมูลส่งออก</u></strong><br />
เป็นจำนวนครั้งของการกดปุ่มเพื่อพิมพ์ข้อความดังกล่าว เมื่อใช้รูปแบบการจัดเรียงตัวอักษรบนปุ่มแบบที่ดีที่สุด<br />
<br />
<u><strong>ข้อจำกัดของชุดทดสอบ<br />
</strong></u>P * K ≥ L <br />
0 ≤ ความถี่ที่แต่ละตัวอักษรถูกใช้ในข้อความ ≤ 1 000 000 <br />
1 ≤ N ≤ 100<br />
1 ≤ P ≤ 1 000<br />
1 ≤ K ≤ 1 000<br />
1 ≤ L ≤ 1 000</span><span style="font-family: Courier New"><br />
<br />
<u><strong>ที่มา:</strong></u><strong> </strong></span><strong><span style="font-family: Courier New">Google Code Jam 2008 Round 1-C</span></strong></p>
<table>
<tr>
<th>ข้อมูลนำเข้า</th>
<th>ข้อมูลส่งออก</th>
</tr>
<tr>
<td>3 2 6
<br />8 2 5 2 4 9</td>
<td>47</td>
</tr>
<tr>
<td>3 9 26
<br />1 1 1 100 100 1 1 1 1 1 1 1 1 1 1 1 1 10 11 11 11 11 1 1 1 100
<br /></td>
<td>397</td>
</tr></table>