ผลต่างระหว่างรุ่นของ "Ipsc2012"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 3: | แถว 3: | ||
== Problem E – Evil matching == | == Problem E – Evil matching == | ||
| − | ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/e.html] | + | : ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/e.html] |
| − | หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive] | + | : หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive] |
ให้ลำดับของจำนวนเต็มบวก T = t<sub>1</sub>,t<sub>2</sub>,…,t<sub>n</sub> (text) และ P = p<sub>1</sub>,p<sub>2</sub>,…,p<sub>m</sub> (pattern). นิยามคลาสสิกของการจับคู่ก็คือ เราจะบอกว่า P นั้น match กับ T ที่ตำแหน่ง k ถ้า p<sub>1</sub> = t<sub>k</sub>, p<sub>2</sub> = t<sub>k+1</sub>, …, และ p<sub>m</sub> = t<sub>k+m−1</sub>. เราสามารถหาตำแหน่งที่ P match กับ T ได้ โดยอาจจะใช้อัลกอริทึมเช่น Knuth-Morris-Pratt algorithm. | ให้ลำดับของจำนวนเต็มบวก T = t<sub>1</sub>,t<sub>2</sub>,…,t<sub>n</sub> (text) และ P = p<sub>1</sub>,p<sub>2</sub>,…,p<sub>m</sub> (pattern). นิยามคลาสสิกของการจับคู่ก็คือ เราจะบอกว่า P นั้น match กับ T ที่ตำแหน่ง k ถ้า p<sub>1</sub> = t<sub>k</sub>, p<sub>2</sub> = t<sub>k+1</sub>, …, และ p<sub>m</sub> = t<sub>k+m−1</sub>. เราสามารถหาตำแหน่งที่ P match กับ T ได้ โดยอาจจะใช้อัลกอริทึมเช่น Knuth-Morris-Pratt algorithm. | ||
| แถว 31: | แถว 31: | ||
== Problem G – Gems in the maze == | == Problem G – Gems in the maze == | ||
| − | ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/g.html] | + | : ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/g.html] |
| + | |||
| + | : หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive] | ||
Scrooge McDuck มีแผนที่จะเพิ่มความมั่งคั่งให้กับตนเอง เขาค้นพบถ้ำมหาสมบัติที่ประกอบด้วยห้องในนั้น n ห้อง ห้องมีหมายเลข 0 ถึง n-1 แต่ละห้องมีอัญมนีหนึ่งชิ้น ห้องเชื่อมต่อกันด้วยทางเดิดที่เดินได้ทางเดียว แต่ละห้องจะมีทางเดินออกจากห้องสองทาง ทางหนึ่งพาไปยังห้องหมายเลข (a ⋅ v<sup>2</sup> + b ⋅ v + c) mod n สำหรับห้องหมายเลข v และอีกทางจะพาคุณออกไปนอกถ้ำมหาสมบัตินี้ | Scrooge McDuck มีแผนที่จะเพิ่มความมั่งคั่งให้กับตนเอง เขาค้นพบถ้ำมหาสมบัติที่ประกอบด้วยห้องในนั้น n ห้อง ห้องมีหมายเลข 0 ถึง n-1 แต่ละห้องมีอัญมนีหนึ่งชิ้น ห้องเชื่อมต่อกันด้วยทางเดิดที่เดินได้ทางเดียว แต่ละห้องจะมีทางเดินออกจากห้องสองทาง ทางหนึ่งพาไปยังห้องหมายเลข (a ⋅ v<sup>2</sup> + b ⋅ v + c) mod n สำหรับห้องหมายเลข v และอีกทางจะพาคุณออกไปนอกถ้ำมหาสมบัตินี้ | ||
รุ่นแก้ไขเมื่อ 04:30, 2 มิถุนายน 2556
หน้านี้รวมคำแปลโจทย์จากการแข่งขัน Internet Problem Solving Contest ปี 2012
Problem E – Evil matching
- ต้นฉบับและข้อมูลนำเข้า: [1]
- หน้ารวมโจทย์ทั้งหมด: [2]
ให้ลำดับของจำนวนเต็มบวก T = t1,t2,…,tn (text) และ P = p1,p2,…,pm (pattern). นิยามคลาสสิกของการจับคู่ก็คือ เราจะบอกว่า P นั้น match กับ T ที่ตำแหน่ง k ถ้า p1 = tk, p2 = tk+1, …, และ pm = tk+m−1. เราสามารถหาตำแหน่งที่ P match กับ T ได้ โดยอาจจะใช้อัลกอริทึมเช่น Knuth-Morris-Pratt algorithm.
เพื่อลดความน่าเบื่อจากอะไรง่าย ๆ เราจะนิยามอะไรให้ยากขึ้นสักหน่อย เราจะกล่าวว่า P evil-match กับ T ที่ตำแหน่ง k ถ้ามีลำดับของดัชนี k = a0 < a1 < ⋯ < am ที่
- ta0 + ta0+1 + ⋯ + ta1−1 = p1
- ta1 + ta1+1 + ⋯ + ta2−1 = p2
- ...
- tam−1 + tam−1+1 + ⋯ + tam−1 = pm
นั่นคือ เราสามารถที่จะรวมข้อมูลใน text เป็นกลุ่ม ๆ เข้าด้วยกันก่อนที่จะไปจับคู่กับ pattern ยกตัวอย่างเช่น ถ้าเรามี T = 1,2,1,1,3,2 และ P = 3,2, เราจะมีสอง evil-matches: อันแรกที่ตำแหน่ง k = 1 (with a1 = 3,a2 = 5), อันที่สองที่ k = 5 (with a1 = 6,a2 = 7).
ค่า evil compatibility ของ text T กับ pattern P คือจำนวนของตำแหน่ง k ที่แตกต่างกันที่ P evil-match กัย T ที่ตำแหน่ง k
โจทย์
ให้ text T และ pattern สองลำดับ P1, P2 คำนวณ
- ค่า evil compatibility ของ T กับ P1
- ค่า evil compatibility ของ T กับ P2
- จำนวนเต็มบวก n ที่น้อบที่สุดที่ทำให้ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 มีค่ามากที่สุด (เมื่อเครื่องหมาย ⋅ แทนการต่อกันของลำดับ)
- ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 สำหรับค่า n นั้น
Problem G – Gems in the maze
- ต้นฉบับและข้อมูลนำเข้า: [3]
- หน้ารวมโจทย์ทั้งหมด: [4]
Scrooge McDuck มีแผนที่จะเพิ่มความมั่งคั่งให้กับตนเอง เขาค้นพบถ้ำมหาสมบัติที่ประกอบด้วยห้องในนั้น n ห้อง ห้องมีหมายเลข 0 ถึง n-1 แต่ละห้องมีอัญมนีหนึ่งชิ้น ห้องเชื่อมต่อกันด้วยทางเดิดที่เดินได้ทางเดียว แต่ละห้องจะมีทางเดินออกจากห้องสองทาง ทางหนึ่งพาไปยังห้องหมายเลข (a ⋅ v2 + b ⋅ v + c) mod n สำหรับห้องหมายเลข v และอีกทางจะพาคุณออกไปนอกถ้ำมหาสมบัตินี้
คุณสามารถเริ่มในถ้ำที่ตำแหน่งใดก็ได้ จากนั้นจะสามารถเดินไปมาตามทางเดินเพื่อเก็บอัญมนี แต่เมื่อคุณออกจากถ้ำแล้ว คุณจะไปทำให้ถ้ำระเบิดและทุกอย่างที่คุณยังไม่ได้เก็บไปก็จะหายไปหมด
Scrooge ต้องการทราบจำนวนอัญมนีที่มากที่สุดที่เขาเอาออกมาจากถ้ำมหาสมบัติได้
