ผลต่างระหว่างรุ่นของ "Ipsc2012"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย 'หน้านี้รวมคำแปลโจทย์จากการแข่งขัน [http://ipsc.ksp.sk/ Internet Probl...')
 
แถว 1: แถว 1:
 
หน้านี้รวมคำแปลโจทย์จากการแข่งขัน [http://ipsc.ksp.sk/ Internet Problem Solving Contest] ปี 2012
 
หน้านี้รวมคำแปลโจทย์จากการแข่งขัน [http://ipsc.ksp.sk/ Internet Problem Solving Contest] ปี 2012
  
== Problem A Abundance of sweets ==
+
== Problem E Evil matching ==
 +
 
 +
ให้ลำดับของจำนวนเต็มบวก 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.
 +
 
 +
เพื่อลดความน่าเบื่อจากอะไรง่าย ๆ เราจะนิยามอะไรให้ยากขึ้นสักหน่อย เราจะกล่าวว่า  P '''evil-match''' กับ T ที่ตำแหน่ง  k ถ้ามีลำดับของดัชนี k = a<sub>0</sub> < a<sub>1</sub> < ⋯ < a<sub>m</sub> ที่
 +
 
 +
* t<sub>a0</sub> + t<sub>a0+1</sub> + ⋯ + t<sub>a1−1</sub> = p<sub>1 </sub>
 +
* t<sub>a1</sub> + t<sub>a1+1</sub> + ⋯ + t<sub>a2−1</sub> = p<sub>2</sub>
 +
* ...
 +
* t<sub>am−1</sub> + t<sub>am−1+1</sub> + ⋯ + t<sub>am−1</sub> = p<sub>m</sub>
 +
 
 +
นั่นคือ เราสามารถที่จะรวมข้อมูลใน 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).

รุ่นแก้ไขเมื่อ 04:08, 2 มิถุนายน 2556

หน้านี้รวมคำแปลโจทย์จากการแข่งขัน Internet Problem Solving Contest ปี 2012

Problem E – Evil matching

ให้ลำดับของจำนวนเต็มบวก 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).