Baltic2012

BOI 2012 Day 1: BRACKETS

(หน่วยความจำ 64 MB, เวลาทำงาน 1.0 sec, คะแนนเต็ม 100 คะแนน)

เราเริ่มต้นโดยการนิยาม ประโยควงเล็บที่ถูกต้อง (correct string of brackets) กันก่อน โดยนิยามดังนี้:

- ( ) และ [ ] จัดเป็นประโยควงเล็บที่ถูกต้อง

- ถ้า A เป็นประโยควงเล็บที่ถูกต้องแล้ว ดังนั้น (A) และ [A] จะเป็นประโยควงเล็บที่ถูกต้องด้วย

- ถ้า A และ B เป็นประโยควงเล็บที่ถูกต้องแล้ว ประโยค AB ที่ได้จากการต่อกัน (concatenate) ของข้อความทั้งสองจะเป็นประโยควงเล็บที่ถูกต้องด้วย

ในประโยควงเล็บที่ถูกต้องจะต้องมีวงเล็บสี่เหลี่ยม [ ] อย่างน้อยหนึ่งคู่ คือจะต้องประกอบด้วยอักษร [ และ ] ภายในประโยค เมื่ออักษรวงเล็บสี่เหลี่ยมเปิดและอักษรวงเล็บสี่เหลี่ยมปิดในประโยควงเล็บที่ถูกต้องถูกแทนที่ด้วยอักษรวงเล็บโค้งเปิด เราจะเรียกประโยคนี้ว่าประโยควงเล็บที่บกพร่อง

ตัวอย่างเช่น ประโยค ( ( และประโยค ( ( ( ( ( ) ) ) นับเป็นประโยควงเล็บที่บกพร่องทั้งคู่ เนื่องจากสำหรับประโยคแรกนั้นสามารถถูกสร้างขึ้นจากประโยควงเล็บที่ถูกต้องคือ [ ] สำหรับประโยคที่สองนั้นอาจถูกสร้างขึ้นได้จากประโยควงเล็บที่ถูกต้องแบบใดแบบหนึ่งในสี่แบบนี้คือ [ ] ( ( ( ) ) ), ( [ ] ( ( ) ) ), ( ( [ ] ( ) ) ) หรือ ( ( ( [ ] ) ) )

งานของคุณคือ กำหนดประโยควงเล็บที่บกพร่องมาให้หนึ่งประโยค ให้คุณหาจำนวนประโยควงเล็บที่ถูกต้องที่เป็นไปได้ทั้งหมดที่สามารถใช้สร้างประโยควงเล็บที่บกพร่องที่กำหนด

ข้อมูลนำเข้า

บรรทัดแรกรับจำนวนเต็มคู่หนึ่งจำนวน N (2 ≤ N ≤ 30,000) ซึ่งแสดงความยาวของประโยควงเล็บที่บกพร่อง บรรทัดที่สองรับอักษรวงเล็บโค้งเปิด “(“ หรือ อักษรวงเล็บโค้งปิด “)” จำนวน N อักษร ที่แสดงประโยควงเล็บที่บกพร่อง

ข้อมูลส่งออก

ให้แสดงคำตอบด้วยจำนวนเต็มหนึ่งจำนวน ที่แสดงถึงจำนวนทั้งหมดที่เป็นไปได้ของประโยควงเล็บที่ถูกต้องที่ใช้ในการสร้างประโยควงเล็บที่บกพร่องที่กำหนด ทั้งนี้จำนวนที่เป็นไปได้อาจมีค่ามาก ดังนั้นให้ตอบด้วยค่าจำนวนเต็มที่เป็นคำตอบหารเอาเศษ (modulo) ด้วย 1 000 000 009

ตัวอย่าง 1

ข้อมูลนำเข้า

4 
( ( ( )

ข้อมูลส่งออก

2

ประโยควงเล็บที่ถูกต้องที่เป็นไปได้

[ ] ( ),  ( [ ] )

ตัวอย่าง 2

ข้อมูลนำเข้า

8 
( ( ( ( ( ( ( ( 

ข้อมูลส่งออก

14

ประโยควงเล็บที่ถูกต้องที่เป็นไปได้

[ ] [ ] [ ] [ ],  [ [ ] ] [ ] [ ],  [ [ ] ] [ [ ] ],  [ ] [ ] [ [ ] ],  [ [ [ ] ] ] [ ],  [ [ ] [ ] ] [ ],
[ ] [ [ ] [ ] ],  [ ] [ [ [ ] ] ],  [ [ [ [ ] ] ] ],  [ [ ] [ [ ] ] ],  [ [ [ ] ] [ ] ],  [ [ ] [ ] [ ] ],
[ [ [ ] [ ] ] ],  [ ] [ [ ] ] [ ]

การให้คะแนน

ข้อมูลทดสอบที่มี N ≤ 50 จะมีค่า 20 คะแนน

ข้อมูลทดสอบที่มี N ≤ 1,000 จะมีค่า 45 คะแนน

---

BOI 2012 Day 1: Mobile

หน่วยความจำ 64 MB, เวลาทำงาน 0.6 sec, คะแนนเต็ม 100 คะแนน

เจ้าของกิจการเครือข่ายเน็ตเวิร์คอันเป็นที่รู้จักกันดีในนาม มะนาวโคออเปอเรชั่น ต้องการสร้างสถานีฐานที่ใช้ในการกระจายสัญญาณมือถือเป็นจำนวนมาก โดยเป้าหมายคือต้องการครอบคลุมพื้นที่การใช้งานทุกจนบนทางด่วนที่ถูกสร้างขึ้นใหม่ แต่เป็นที่ทราบกันดีกว่าพนักงานในบริษัทมะนาวโคออเปอเรชั่นนี้ มักจะทำงานลวกลวกแบบขอไปที ทำให้การควบคุมสัญญาณความแรงของแต่ละฐานนั้นไม่สามารถทำแยกกันได้ จะทำได้ก็พียงแต่การกำหนดความแรงในการส่งสัญญาณคงที่ และทุกสถานีฐานจะส่งสัญญาณด้วยความแรงเท่ากันตามค่าที่กำหนดนี้ อย่างไรก็ตามบริษัทก็ต้องการใช้พลังงานในการส่งสัญญาณให้น้อยที่สุดเท่าที่จะเป็นได้ ดังนั้นบริษัทจึงต้องการทราบถึงระยะห่างที่มากที่สุดจากจุดใดๆ บนทางด่วนไปยังสถานีฐานที่ใกล้ที่สุด

ข้อมูลนำเข้า

บรรทัดแรกรับจำนวนเต็มสองจำนวน N (1 ≤ N ≤ 106) และ L (1 ≤ L ≤ 109) ซึ่งหมายถึงจำนวนสถานีฐานทั้งหมด และความยาวของทางด่วนที่สร้างขึ้น ตามลำดับ

จากนั้นอีก N บรรทัด จะรับข้อมูลจำนวนเต็มสองจำนวน xi และ yi (-109 ≤ xi, yi ≤ 109) ซึ่งแสดงถึงตำแหน่งของสถานีฐานแต่ละแห่ง โดยจะไม่มีสถานีคู่ใดอยู่ในตำแหน่งเดียวกัน และคู่อันดับนี้จะถูกเรียงลำดับจากน้อยไปมาก (อาจซ้ำได้) ตามค่า xi และหากสองคู่ลำดับใดมีค่า xi เท่ากันจะเรียงลำดับตามค่า yi จากน้อยไปมาก

กำหนดให้ทางด่วนเป็นเส้นตรงที่เริ่มต้นจากคู่ลำดับ (0,0) และสิ้นสุดที่คู่ลำดับ (L,0)

ข้อมูลส่งออก

ให้แสดงคำตอบด้วยจำนวนเต็มหนึ่งจำนวน ที่แสดงถึงระยะทางที่มากที่สุดจากจุดใดๆ บนทางด่วนไปยังสถานีฐานที่ใกล้ที่สุด คำตอบของคุณจะนับว่าถูกต้องเมื่อระยะทางนี้ห่างไม่เกิน 10-3 จากคำตอบของเฉลย

ตัวอย่าง

ข้อมูลนำเข้า

2 10
0 0
11 1

ข้อมูลส่งออก

5.545455

การให้คะแนน

• ข้อมูลทดสอบที่มี N ≤ 5,000 จะมีค่า 25 คะแนน
• ข้อมูลทดสอบที่มี N ≤ 100,000 จะมีค่า 50 คะแนน

คำเตือน

ควรใช้ double precision floating point เป็นอย่างน้อยในการคำนวณ เนื่องจากประเภทข้อมูลที่เล็กกว่านี้อาจทำให้คำตอบผิดเพี้ยนมากเกินขอบเขตที่กำหนดได้

BOI 2012 Day 1: PEAKS

(หน่วยความจำ 64 MB, เวลาทำงาน 0.5 sec, คะแนนเต็ม 100 คะแนน)

นักปีนเขาผู้หนึ่งอาศัยอยู่บนเกาะแห่งยอดเขาและยืนอยู่บนยอดเขาแห่งหนึ่ง ต้องการไปพิชิตยอดเขาที่สูงขึ้นไป

เพื่อความชัดเจน ทุกจุดบนเกาะแห่งนี้จะมีค่าแสดงความสูงที่เป็นบวกที่ห่างจากระดับน้ำทะเลอยู่ (ความสูงของระดับน้ำทะเลคือ 0) สมมติว่านักปีนเขาเริ่มต้นที่ยอดเขาหนึ่งที่ระดับความสูง Ei นักปีนเขาผู้นี้ต้องการไปยังยอดเขาที่สูงขึ้นที่ระดับความสูง Ej (Ej > Ei) ใดๆ และเนื่องจากนักปีนเขาได้อยู่ที่จุดยอดเขาแล้วดังนั้นไม่มีทางใดที่ติดกับเขาที่เป็นทางขึ้นเขาอีก ดังนั้นเขาจำต้องที่จะลงเขาไปก่อนเพื่อที่จะปีนขึ้นไปยังเขาลูกใหม่ อย่างไรก็ตามเส้นทางการลงเขามันย่อมไม่น่าหลงใหลเท่ากับการขึ้นเขา ดังนั้นนักปีนเขาผู้นี้จึงต้องการหาความสูงที่มากที่สุดที่เขาจำเป็นจะต้องลงไปเพื่อที่จะสามารถพิชิตยอดเขายอดใหม่ที่สูงกว่ายอดเขาปัจจุบันได้

ตัวอย่างเช่น สมมติให้เกาะแห่งยอดเขานี้มีลักษณะดังรูปทางขวา และนักปีนเขาเริ่มต้นที่ยอดเขาที่ตำแหน่งความสูง E4 แล้ว จะมียอดเขาที่สูงกว่านี้อีก 3 แห่งคือ (E5, E6 และ E7) ตำแหน่งบนเส้นทางที่ต่ำกว่ายอดเขาปัจจุบันและมีระดับความสูงสูงที่สุด ที่เป็นทางขึ้นไปยังยอดเขา E7 คือตำแหน่ง E2 เนื่องจากนักปีนเขาไม่จำเป็นต้องลงไปต่ำกว่า E2 เพื่อปีนไปยังยอดเขา E7 (หากนักปีนเขาต้องการไปยอดเขาอื่น เขาจำเป็นที่จะต้องลงไปที่ความสูง E1) ดังนั้นคำตอบคือ E2 สมมติว่านักปีนเขาเริ่มต้นที่ยอดเขา E5 ตำแหน่งที่สูงที่สุดที่เขาจำเป็นต้องลงไปเพื่อพิชิตยอดเขาที่สูงกว่าคือระดับความสูง E3 (ทางไปยังยอดเขา E6), ถ้านักปีนเขาเริ่มต้นที่ E6 เขาจะต้องลงไปที่ระดับความสูง E1

แผนที่ของเกาะแห่งยอดเขาเป็นแผนที่สี่เหลี่ยม 2 มิติที่ประกอบไปด้วย NxM ช่องและค่าระดับความสูงของพื้นที่ในแต่ละช่อง สำหรับสองช่องใดๆ จะติดกัน ถ้าสองช่องนั้นมีจุดใดๆ ร่วมกัน กล่าวคือช่องใดๆ (ยกเว้นช่องที่ขอบ) จะติดกับช่องอื่นๆอีก 8 ช่อง, เส้นทางคือลำดับอนุกรม (sequence) ของช่องที่ติดกัน, ที่ราบสูงคือกลุ่มของช่องตั้งแต่หนึ่งช่องขึ้นไปติดกันและมีความสูงเท่ากัน สำหรับช่องคู่ใดๆ ในที่ราบสูงสามารถไปถึงช่องอื่นๆ ในที่ราบสูงเดียวกันได้โดยใช้เส้นทางภายในที่ราบสูงนี้, ช่องใดๆ ที่ติดกันและมีความสูงเท่ากันจะถือว่าอยู่ในที่ราบสูงเดียวกัน, ยอดเขาคือที่ราบสูงที่ไม่ติดกันกับช่องใดๆ ที่มีความสูงมากกว่า

หน้าที่ของคุณคือ เขียนโปรแกรมเพื่อหายอดเขาทั้งหมดภายในเกาะแห่งยอดเขานี้ และสำหรับแต่ละยอดเขาให้หาความสูงที่มากที่สุดของเส้นทางที่นักปีนเขาสามารถไปยังยอดเขาอื่นที่สูงกว่า สำหรับยอดเขาที่สูงที่สุดในเกาะ (จะไม่มียอดเขาที่สูงกว่าแล้ว) เราจะถือว่านักปีนเขาต้องการออกจากเกาะนี้ไปเพื่อไปหายอดเขาที่สูงกว่าที่อื่น ดังนั้นคำตอบจะเป็น 0 (ซึ่งหมายถึงระดับของน้ำทะเล)

ข้อมูลนำเข้า

บรรทัดแรกรับจำนวนเต็มสองจำนวน N และ M (1 ≤ N, M ≤ 2000 ; NxM ≤ 105) ที่แสดงยาวและความกว้างของแผนที่เกาะแห่งยอดเขา ตามลำดับ

ต่อมาอีก N บรรทัด รับข้อมูลแผนที่ โดยแต่ละบรรทัดจะรับจำนวนเต็ม M จำนวนคั่นด้วยเว้นวรรค ที่แสดงความสูงของพื้นที่ในแต่ละช่อง โดยค่าความสูง Eij (1 ≤ Eij ≤ 106), ความสูงของช่อง Eij (ช่องในแถวที่ i และคอลัมน์ที่ j) จะตรงกับข้อมูลนำเข้าในตัวที่ j ในบรรทัดที่ i+1

ข้อมูลส่งออก

บรรทัดแรกให้แสดงค่าจำนวนเต็ม P ที่แสดงถึงถึงจำนวนยอดเขาที่มีทั้งหมดในเกาะแห่งยอดเขานี้

ต่อมาอีก P บรรทัด ให้แสดงจำนวนเต็มสองจำนวน คือ ความสูงของยอดเขาแต่ละยอดที่พิจารณาอยู่ และอีกจำนวนหนึ่งคือความสูงของจุดที่สูงที่สุดภายในเส้นทางที่ใช้ในการเดินทางจากยอดเขานี้ไปยังยอดเขาอื่นที่สูงกว่า

โดยให้เรียงลำดับคำตอบให้เรียงตามค่าความสูงของยอดเขาจากมากไปน้อย ถ้าเท่ากันให้เรียงค่าความสูงของจุดที่สูงที่สุดในเส้นทางที่ใช้ไปยังยอดเขาอื่นจากมากไปน้อย

ตัวอย่าง 1

ข้อมูลนำเข้า

6 6 
21 16 9  11 6  7
21 21 10 14 15 9 
18 20 8  9  13 14
11 10 9  9  8  13
8  12 12 14 13 8
7  13 12 9  5  1

ข้อมูลส่งออก

4
21 0
15 11
14 13
13 12

อธิบาย

ยอดเขาทั้งหมดแสดงด้วยเครื่องหมายวงกลม

เส้นทางหนึ่งที่เป็นไปได้ ในการปีนเขาจากยอดเขาความสูง 15 ไปยังยอดเขาที่สูงกว่า แสดงด้วยช่องสีดำ

ตัวอย่าง 2

ข้อมูลนำเข้า

5 3
16 14 16
14 14 15
12 17 16
12 13 10
16 11 16

ข้อมูลส่งออก

5
17 0
16 15
16 14
16 13
16 13

การให้คะแนน

ข้อมูลทดสอบที่มี N ≤ 2 หรือ M ≤ 2 จะมีค่า 15 คะแนน

ข้อมูลทดสอบที่มี P ≤ 500 จะมีค่า 50 คะแนน

ข้อมูลทดสอบที่มี P ≤ 5000 จะมีค่า 80 คะแนน

---

BOI 2012 Day 2: Fire

(หน่วยความจำ 64 MB, เวลาทำงาน 1.0 sec, คะแนนเต็ม 100 คะแนน)

เมืองขอบฟ้ากว้างใหญ่ไร้พรมแดนตั้งอยู่บนตารางกริดสี่เหลี่ยมจัตุรัสขนาดไม่จำกัด โดยเส้นตารางทั้งหมดนั้นจะสามารถใช้เป็นถนนได้ และถนนสองเส้นใดๆ จะขนานกันหรือไม่ก็ตั้งฉากกันอย่างใดอย่างหนึ่งเท่านั้น กำหนดให้ระยะทางระหว่างถนนสองเส้นที่ใกล้กันที่สุดที่ขนานกัน คือหนึ่งหน่วย ถนนที่วางตัวในแนว ตะวันตก-ตะวันออก จะเรียกว่าเป็นถนนแนนนอน ถนนเหล่านี้สามารถระบุได้โดยใช้เพียงตำแหน่งในแนว เหนือ-ใต้, ส่วนถนนที่วางตัวในแนว เหนือ-ใต้ จะเรียกว่าถนนแนวตั้ง ถนนเหล่านี้สามารถระบุได้โดยใช้เพียงตำแหน่งในแนว ตะวันตก-ตะวันออก

ชาวบ้านทุกคนจะอาศัยอยู่ในบ้าน ที่ซึ่งมีทางเข้าตั้งอยู่บนจุดตัดกันระหว่างถนนแนวตั้งและถนนแนวนอนคู่หนึ่ง อย่างไรก็ตามชาวบ้านหลายคนสามารถอาศัยอยู่ในบ้านหลังเดียวกันได้

ท่านขุนศึกผู้เป็นเจ้าเมืองขอบฟ้ากว้างใหญ่ไร้พรมแดน ต้องการสร้างภาพเพื่อเพิ่มคะแนนนิยมจากชาวบ้านภายในเมืองขึ้น ดังนั้นเขาต้องการจัดงานยิงพลุสร้างภาพขึ้น ณ ตำแหน่งจุดตัดระหว่างถนนแนวนอนสายหลักของเมือง (ที่ตำแหน่ง 0) และถนนแนวตั้งเส้นใดเส้นหนึ่ง ท่านขุนศึกรู้ดีว่าชาวบ้านทุกคนมีความสนใจที่ออกจากบ้านของตนเพื่อดูพลุ การจุดพลุครั้งนี้ทำขึ้นที่จุดตัดระหว่างถนนสองเส้นดังนั้นพลุสามารถถูกมองเห็นได้จากตำแหน่งใดๆ บนถนนทั้งสองสายนั้น และเนื่องจากเหตุผลด้านความปลอดภัย ชาวบ้านที่ดูพลุจะสามารถดูพลุได้โดยต้องยืนอยู่ห่างจากสถานที่จัดงานไม่น้อยกว่า S หน่วย ดังนั้นเมื่อจุดพลุ ชาวบ้านในบริเวณดังกล่าวจะต้องเดินออกจาบริเวณอันตรายไปยังจุดที่ปลอดภัยก่อนจึงจะสามารถดูพลุได้ ถ้าสมมติให้งานจุดพลุนี้จัดขึ้นบนจุดตัดของถนนแนวตั้งหมายเลข V (กับถนนแนวนอนสายหลัก) ชาวบ้านทุกคนก็จะออกไปดูพลุบนถนนแนวนอนสายหลัก (หมายเลข 0) หรือไม่ก็ดูพลุบนถนนแนวตั้งหมายเลข V โดยที่ไม่สามารถอยู่ใกล้กับจุดที่จัดงานน้อยกว่า S หน่วย ตัวอย่าง ถ้า S=2 การดูพลุจะทำได้บนถนนแนวนอนสายหลักทุกตำแหน่งยกเว้นตำแหน่ง V-1, V และ V, และการดูพลุก็ยังสามารถที่จะดูบนถนนแนวตั้งหมายเลข V ในทุกตำแหน่งยกเว้นเช่นกัน ตำแหน่งในแนวนอนเป็น -1,0, และ 1

ทั้งนี้ผลงานความน่าพิสมัยของการดูพลุนั้นขึ้นโดยตรงกับระยะทางที่ชาวบ้านต้องเดินออกจากบ้านไปยังจุดที่สามารถมองเห็นพลุได้ ดังนั้นการจัดงานยิงพลุสร้างภาพนี้จึงเป็นต้องเลือกตำแหน่งการจัดงานอย่างรอบคอบเพื่อทำให้ระยะทางการเดินของชาวบ้านโดยรวมทั้งเมืองน้อยที่สุด

ตัวอย่างเช่น ถ้า S=2 และในเมืองนี้มีชาวบ้านทั้งหมด 7 คน แสดงดังรูป (มีชาวบ้านสองคนอยู่ที่ตำแหน่ง (-4,8) แล้วตำแหน่งที่ดีที่สุดในการจัดงานยิงพลุครั้งนี้คือ ตำแหน่งที่ตัดกับถนนแนวตั้งหมายเลข 8 ซึ่งจะทำให้ระยะทางการเดินรวมของชาวบ้านเป็น 9 หน่วย

หน้าที่ของคุณคือ ให้เขียนโปรแกรมเพื่อหาผลรวมระยะทางที่น้อยที่สุด ที่ชาวบ้านต้องเดินเพื่อการดูงานยิงพลุ

ข้อมูลนำเข้า

• บรรทัดแรก รับจำนวนเต็มสองจำนวน คั่นด้วยช่องว่าง ที่หมายถึง จำนวนชาวบ้านทั้งหมดในเมือง N (N ≤ 105) และระยะปลอดภัย S (S ≤ 106) หน่วย
• ต่อมาอีก N บรรทัด เป็นข้อมูลตำแหน่งบ้านของชาวบ้านแต่ละคน ในแต่ละบรรทัดจะประกอบไปด้วยจำนวนเต็มสองจำนวน Hi และ Vi คั่นด้วยช่องว่าง โดยที่ Hi และ Vi (-109 ≤ Hi, Vi ≤ 109) หมายถึงหมายเลขของถนนแนวนอนและถนนแนวตั้ง ที่บ้านของชาวเมืองคนที่ i นั้นตั้งอยู่

ข้อมูลส่งออก

• ให้แสดงคำตอบด้วยจำนวนเต็มหนึ่งจำนวน ที่แสดงระยะทางรวมที่น้อยที่สุดที่ชาวบ้านทุกคนใช้ในการเดินเพื่อไปดูพลุ

ตัวอย่าง ข้อมูลนำเข้า

7 2
3 -2
0 8
-4 8
-1 4
-2 13
-4 8
1 5

ข้อมูลส่งออก

9

การให้คะแนน

ข้อมูลทดสอบที่มี 0 ≤ Vi ≤ 5000 จะมีค่า 20 คะแนน

ข้อมูลทดสอบที่มี N ≤ 5000 จะมีค่า 40 คะแนน

---

BOI 2012 Day 2: Melody เครื่องดนตรีประหลาด

หน่วยความจำ 128 MB, เวลาทำงาน 1.0 sec, คะแนนเต็ม 100 คะแนน

โคทาโร่ชอบที่จะเล่นเครื่องดนตรีประหลาดและไม่มีใครรู้ว่าเครื่องดนตรีนั้นคือเครื่องดนตรีอะไร เครื่องดนตรีนี้ประกอบไปด้วยรู S รูและเขาสามารถที่จะเล่นเสียงโน้ตที่แตกต่างกันได้ N โน้ต (ระบุด้วยตัวเลขจาก 1 ถึง N) โดยพายจะใช้นิ้วของเค้าปิดรูแต่ละรูด้วยเนคนิคที่เฉพาะตัว (ของโคทาโร่) ที่แตกต่างกันถึง 10 รูปแบบ (ระบุด้วยตัวเลขจาก 0 ถึง 9) โน้ตแต่ละตัวที่พายเล่นนั้นจะขึ้นกับวิธีในการปิดรูเฉพาะแบบของแต่ละโน้ตซึ่งจะไม่ซ้ำกับโน้ตอื่นๆ ดังนั้นโน้ตหนึ่งๆ สามารถอธิบายได้ด้วยลำดับอนุกรม (sequence) ของการปิดรูแต่ละรู และความแปลกของเครื่องดนตรีประหลาดชิ้นนี้คือ ถ้ารูถูกปิดแบบไม่ถูกต้อง (คือไม่ตรงกับโน้ตใดๆ) เครื่องดนตรีจะส่งเสียงแปร่งประหลาดไม่น่าฟังออกมา ดังนั้นโคทาโร่จึงเลือกที่จะเล่นโน้ตอื่นที่ผิดแทนการสร้างเสียงประหลาดเหล่านั้น

ตอนนี้โคทาโร่ได้มาโอกาสเข้ามาอยู่ในวงของ อ. สตีฟพาย ซึ่งเป็นวงดนตรีที่มีความสามารถมาก ซึ่งจังหวะดนตรีและการเปลี่ยนแปลงโน้ตนั้นก็ต้องเกิดขึ้นอย่างรวดเร็ว ทั้งนี้พายได้เขียนเนื้อเพลงขึ้น (ซึ่งก็คือ ลำดับของตัวเลขที่ใช้ในการอ้างอิงตัวโน้ตแต่ละตัว) แม้ว่าโคทาโร่ได้เล่นร่วมกับวงดนตรีนี้ แต่ทว่าความสามารถของโคทาโร่ก็จำกัด ทำให้เขาสามารถเล่นโน้ตสองตัวใดๆ ที่ติดกันได้ถ้าวิธีการปิดรูเพื่อสร้างเสียงโน้ตตัวที่สองมีความแตกต่างกันไม่เกิน G รูกับวิธีการปิดรูในการสร้างเสียงโน้ตตัวแรก ดังนั้นเมื่อพบโน้ตที่ยากเกินความสามารถในเนื้อเพลงที่พายเขียน โคทาโร่จึงจะเลือกที่จะเล่นโน้ตผิดแทน การเล่นโน้ตที่ผิดแต่ละโน้ตนั้นจะเรียกว่าโน้ตเพี้ยน

หน้าที่ของคุณคือ รับข้อมูลเนื้อเพลงต้นฉบับที่ อ. สตีฟ พายเขียนให้ จากนั้นให้แก้ไขเนื้อเพลงเพื่อให้โคทาโร่เล่น โดยให้มีโน้ตเพี้ยนน้อยที่สุด

ข้อมูลนำเข้า

• บรรทัดแรก รับจำนวนเต็มสามจำนวนคั่นด้วยช่องว่าง ที่แสดง จำนวนโน้ตที่เป็นไปได้ทั้งหมด N (1 ≤ N ≤ 100), จำนวนรูของเครื่องดนตรี S, ความเร็วในการใช้นิ้ว G (1 ≤ G < S ≤ 100)
• ต่อมาอีก N บรรทัด หมายถึงข้อมูลโน้ตแต่ละตัว โดยในแต่ละบรรทัดจะประกอบไปด้วยตัวเลข S หลักโดยไม่มีช่องว่างคั่น ตัวเลขหลักที่ j ในบรรทัด i+1 จะหมายถึงรูปแบบเทคนิคที่ใช้ในการปิดรูที่ j เพื่อใช้ในการเล่นโน้ตตัวที่ i (โคทาโร่ใช้ 10 เทคนิคที่แตกต่างกันในการปิดรู ดังนั้นค่านี้จะมีค่าเป็นจำนวนเต็มจาก 0 ถึง 9) และโน้ตสองตัวใดๆ จะไม่ซ้ำกัน
• บรรทัดต่อมา (บรรทัดที่ N+2) รับความยาวของเนื้อเพลงต้นฉบับ L (1 ≤ L ≤ 105)
• บรรทัดสุดท้าย (บรรทัดที่ N+3) รับข้อมูลเนื้อเพลงต้นฉบับ โดยเป็นลำดับของตัวเลขจำนวน L ตัว คั่นด้วยช่องว่าง หมายเลขแต่ละตัวแสดงถึงหมายเลขอ้างอิงของโน้ตตามลำดับด้านบน

ข้อมูลส่งออก

• บรรทัดแรก ให้แสดงคำตอบด้วยจำนวนเต็มไม่ลบหนึ่งจำนวน ที่แสดงจำนวนครั้งที่น้อยที่สุดที่โน้ตเพี้ยนปรากฎ
• บรรทัดที่สอง ให้แสดงเนื้อเพลงที่แก้ไขแล้วที่โคทาโร่สามารถเล่นได้ ซึ่งจะประกอบไปด้วยตัวเลขจำนวนเต็ม L จำนวน ที่แสดงเลขอ้างอิงของโน้ตแต่ละตัว ถ้าสามารถแก้ไขเนื้อเพลงได้มากกว่าหนึ่งรูปแบบให้ตอบแบบใดก็ได้

ตัวอย่าง

ข้อมูลนำเข้า

5 4 2
1111
2101
2000
0100
0000
7
1 5 4 5 3 2 1	

ข้อมูลส่งออก

1
1 2 4 5 3 2 1	

อธิบาย

โคทาโร่ไม่มีความสามารถสามารถพอที่จะเล่นโน้ต 5 ต่อจากโน้ต 1 ทันที เขาจึงต้องการเล่นโน้ต 2 แทนโน้ต 5

การให้คะแนน

• ข้อมูลทดสอบที่มี L ≤ 100 จะมีค่า 40 คะแนน
• ข้อมูลทดสอบที่มี L ≤ 5000 จะมีค่า 65 คะแนน

BOI 2012 Day 2: Tiny เตตริสน้อย

หน่วยความจำ 128 MB, เวลาทำงาน 1.0 sec, คะแนนเต็ม 100 คะแนน

สำหรับผู้ที่อายุมากแล้วทั้งหลายคงยังรำลึกถึงเกม “เตตริส” หรือ “TETRIS” อันเลื่องชื่อ ของ Alexey Pajitnov ได้ โดยในเกมนี้วัตถุแต่ละชิ้นประกอบด้วยบล็อคจำนวน 4 บล็อคติดกัน หล่นลงมาจากฟ้าด้านบน และจุดมุ่งหมายของเกมนี้คือพยายามหมุนวัตถุชิ้นต่างๆ เพื่อวางลงบนกล่อง(พื้นที่ว่าง) เพื่อให้บล็อคต่อกันเต็มแถวแนวนอนโดยไม่มีช่อง ว่างกั้น ให้ได้มากที่สุด แต่ละครั้งที่เกิดแถวแนวนอนที่บล็อคเต็มทุกช่องในแถวนั้น บล็อคทั้งหมดในแนวนั้นจะหายไปและเปลี่ยนเป็นข่องว่างแทน สำหรับโจทย์ข้อนี้เราจะพิจารณา เกมที่ง่ายขึ้นโดยเราเรียกว่า “เตตริสน้อย” ในเกมนี้วัตถุทั้งมดที่เราสนใจจะมีอยู่ 9 แบบเท่านั้นที่ประกอบไปด้วยบล็อคตั้งแต่ 1 ถึง 3 ช่อง ดังรูป หมายเลขด้านล่างใช้สำหรับการอ้างถึงรูปแบบที่แตกต่างกันของวัตถุ

เกมนี้ก็เช่นเดียวกัน คือ วัตถุแต่ละชิ้นจะตกลงมาจากด้านบน เพื่อที่จะใส่ไปในกล่องสี่เหลี่ยมขนาดสูง 9 หน่วยและยาว 9 หน่วย แต่เกมนี้จะง่ายกว่าเกมเตตริสคือวัตถุแต่ละชิ้นจะไม่สามารถหมุนได้ และนอกจากนี้วัตถุแต่ละชิ้นไม่สามารถเคลื่อนที่ไปทางซ้ายหรือขวาภายหลังจากการตกลงมาแล้ว ดังนั้นสำหรับวัตถุแต่ละชิ้นนั้นผู้เล่นสามารถเพียงที่จะเลือกตำแหน่งเริ่มต้นที่วัตถุจะตกได้ โดยระบุตำแหน่งในแนวคอลัมน์ของกล่องสี่เหลี่ยม (เป็นจำนวนเต็มตั้งแต่ 1 ถึง 9) โดยตำแหน่งที่ระบุนี้จะใช้อ้างอิงถึงบล็อคซ้ายสุดของวัตถุที่พิจารณาอยู่ในขณะนั้น (แสดงโดยสัญลักษณ์ x ดังรูป)

แต่ละเกมจะประกอบด้วยลำดับการตกจำนวนจำกัด โดยจะมีวัตถุทั้งหมด N ชิ้นตกลงมา หน้าที่ของเราคือใส่วัตถุเหล่านี้ลงไปในกล่องตามลำดับให้ได้มากที่สุด หรือการวางวัตถุที่ไม่ถูกต้องคือมีบางส่วนอยู่นอกกล่องเกมจะจบลง คะแนนของเกมจะเท่ากับจำนวนวัตถุทั้งหมดที่สามารถวางลงไปในกล่องได้สำเร็จ

เมื่อเริ่มเกมตัวนับคะแนนจะถูกกำหนดให้เป็น 0

วิธีการดำเนินการของเกมจะเป็นตามลำดับด้านล่าง:

1. ผู้เล่นสามารถเลือกคอลัมน์ ที่ต้องการวางโดยเทียบกับตำแหน่งซ้ายสุดของวัตถุปัจจุบัน
2. ถ้าคอลัมน์ถูกกำหนดอย่างถูกต้อง (เช่น คอลัมน์ 8 จะไม่สามารถใช้ได้สำหรับวัตถุชนิดที่ 5 ได้), วัตถุจะตกลงมาจนกว่าจะเจอสิ่งกีดขวาง แต่ถ้าคอลัมน์ถูกกำหนดไม่ถูกต้อง เกมจะจบลง
3. ถ้าวัตถุสามารถบรรจุอยู่ในกล่องได้อย่างสมบูรณ์ (ทุกบล็อคของวัตถุอยู่ในกล่องขนาด 9x9), ตัวนับคะแนนจะมีค่าเพิ่มขึ้น 1, แต่ถ้าบางส่วนของวัตถุไม่สามารถบรรจุในกล่องได้ เกมจะจบลง
4. จากนั้นให้ตรวจสอบว่ามีแถวในแนวนอนใดบ้างที่มีบล็อคบรรจุอยู่เต็มโดยไม่มีช่องว่าง ถ้ามีแถวดังกล่าว แถวแนวนอนนั้นจะหายไปและแถวอื่นๆด้านบนจะตกลงมาโดยไม่เปลี่ยนรูปแบบบล็อคที่ค้างอยู่
5. ถ้ายังมีวัตถุเหลืออยู่ ให้ดำเนินการตามข้อ 1) อีกครั้ง, หรือไม่ก็เกมจะจบลง

คะแนนที่ได้ในแต่ละเกมจะเท่ากับค่าของตัวนับคะแนนเมื่อเกมจบลง

ตัวอย่าง (ประกอบกับรูปในโจทย์) ลำดับที่แสดงชนิดของวัตถุจำนวน 20 ชิ้นที่จะตกลงมาคือ 5,4,1,6,7,6,4,4,7,9,5,5,6,8,3,4,3, 7,4,2 สมมติให้วัตถุจำนวน 17 ชิ้นได้ตกลงมาแล้วอย่างสำเร็จโดยลำดับการว่างวัตถุในแนวคอลัมน์ คือ 1,2,2,4,8,8,7,4,8,6,1,1,4,8,3,7,7 ในขณะนี้ยังไม่มีแถวแนวนอนใดเต็ม, ตัวนับคะแนนมีค่าเป็น 17, และขณะนี้วัตถุชนิดที่ 7 กำลังจะตกลงมา (สถานะปัจจุบันของกล่องแสดงดังรูปทางขวา โดยอักษรในรูปจะแสดงลำดับของวัตถุที่ตกลงมา)

ขณะที่วัตถุชนิดที่ 7 ตกลงมานั้น การตกลงมาที่ถูกต้องนั้นมีเพียง 2 ความเป็นไปได้คือ

1. ตกลงที่คอลัมน์ 1
2. ตกลงที่คอลัมน์ 5 (ซึ่งจะทำให้เกิดแถวที่มีบล็อคเต็มและจะหายไป)

ข้อมูลนำเข้า

• บรรทัดแรก รับจำนวนเต็มหนึ่งจำนวน ที่แสดงจำนวนวัตถุทั้งหมด N
• ต่อมาอีก N บรรทัด รับข้อมูลจำนวนเต็มหนึ่งจำนวนที่มีค่าตั้งแต่ 1 ถึง 9 ที่แสดงถึงชนิดของวัตถุ, ชนิดของวัตถุชิ้นที่ i จะแสดงในบรรทัดที่ i+1

ข้อมูลส่งออก

• ให้แสดงคำตอบเป็นจำนวนไม่เกิน N บรรทัด โดยแต่ละบรรทัดแสดงหมายเลขคอลัมน์ที่วัตถุจะตก, บรรทัดที่ i จะหมายถึงคอลัมน์ที่ต้องการให้วัตถุชิ้นที่ i ตกลงมา

ในแต่ละเกมนั้น โจทย์การันตีว่าจะมีวิธีการที่วัตถุทุกชิ้นสามารถใส่ในกล่องได้ (คือค่าของตัวนับคะแนนสามารถเป็น N ได้ขณะเกมจบ)

การให้คะแนน (ให้ดูเฉยๆครับ เราไม่ได้ทำครับ)

มีทั้งหมด 5 เกมเกมละ 20 คะแนน โดยคะแนนที่จะได้แต่ละเกมจะคิดเป็นสัดส่วนตามคะแนนของคนที่ทำได้คะแนนสูงสุด ตามสูตรดังนี้: 20 × your_score/maximum_score_among_all_contestants

ขณะสอบคุณจะได้รับ feedback และคะแนนที่คุณทำได้โดยสมมติว่ามีคนทำได้เต็ม และเมื่อแข่งเสร็จคะแนนของคุณจะถูกคำนวณอีกครั้งตามสัดส่วนคะแนนของคนที่ได้มากที่สุด