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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 33: แถว 33:
 
=== Periodicity (day1) ===
 
=== Periodicity (day1) ===
 
Source: [http://main.edu.pl/en/archive/oi/18/okr]
 
Source: [http://main.edu.pl/en/archive/oi/18/okr]
 +
 +
โจทย์โดย Wojciech Rytter
 +
 +
Byteasar เป็นกษัตริย์ของ Bitotia มีความต้องการที่จะเปลี่ยนชื่อพลเมืองทุกคนในเมืองของเขา  ชื่อของชาว Bitotian นั้นมักจะมีส่วนของชื่อที่ซ้ำ ๆ กัน เช่น Abiabuabiab  มีคำว่า  abiab ปรากฏซ้ำสองครั้ง  Byteasar ต้องการเปลี่ยนชื่อพลเมืองให้เป็นลำดับของบิตที่มีความยาวเท่ากับชื่อเดิม และยังต้องการให้ชื่อใหม่นั้น ยังคงลักษณะการซ้ำกันของชื่อเดิมด้วย
 +
 +
ในส่วนต่อไป เราจะพิจารณาตัวอักษรพิมพ์ใหญ่และพิมพ์เล็กว่าเหมือนกัน  สำหรับลำดับของตัวอักขระ (อาจจะเป็นตัวอักษรหรือบิตก็ได้) '''w = w<sub>1</sub> w<sub>2</sub> ... w<sub>k</sub>''' เราจะกล่าวว่าจำนวนเต็ม '''p''' เป็น '''รอบ''' (period) ของ '''w''' ถ้า '''w<sub>i</sub> = w<sub>i+p</sub>''' สำหรับทุก ๆ ค่า '''i=1,...,k-p'''  เราจะเรียกเซตของรอบในสตริง '''w''' ว่า '''Per(w)'''  เช่น '''Per(ABIABUABIAB) = {6,9}''', '''Per(01001010010) = {5,8,10}''', และ '''Per(0000) = {1,2,3}'''

รุ่นแก้ไขเมื่อ 09:08, 17 พฤษภาคม 2556

Stage III

Party (day1)

Source: [1]

โจทย์โดย Jakub Onufry Wojtaszczyk

Byteasar ต้องการจัดปาร์ตีให้สุดยอด และมันจะสุดยอดได้แน่ ๆ ถ้าแขกทุกคนรู้จักกันทั้งหมด เขาพยายามจะหารายการของแขกที่จะเชิญมาให้ได้แบบนั้น

เขามีเพื่อน n คน (n หารด้วย 3 ลงตัว) โชคดีที่เขาทราบว่าเพื่อน ๆ ของเขาโดยมากจะรู้จักกัน ยิ่งไปกว่านั้น เขาจำได้ว่าเขาเพิ่งไปงานปาร์ตีที่ มีเพื่อนจำนวน 2n/3 คน และทุกคนรู้จักกันหมด อย่างไรก็ตาม Byteasar พลาดที่จำไม่ได้ว่าใครไปงานนั้นบ้าง

Byteasar ไม่จำเป็นต้องจัดงานใหญ่มาก แต่เขาต้องการจะจัดงานที่มีแขกอย่างน้อย n/3 คน รบกวนคุณช่วยเขาด้วย

Inspection (day1)

Source: [2]

โจทย์โดย Wojciech Rytter และ Bartosz Szreder.

ระบบรางรถไฟของ Byteotian Railways (BR) ประกอบด้วยส่วนของรางเชื่อมระหว่างสถานีที่สามารถเดินทางได้สองทาง แต่ละคู่ของสถานีจะเชื่อมกันด้วยส่วนของรามเชื่อมไม่เกินหนึ่งเส้น นอกจากนี้ ระหว่างคู่ของสถานีใด ๆ จะมีเส้นทางเชื่อมถึงกันแค่เส้นเดียว (เส้นทางนั้นอาจจะใช้ส่วนของรางหลายส่วน แต่จะต้องไม่ผ่านสถานีใด ๆ มากกว่าหนึ่งครั้ง)

Byteasar เป็นผู้ตรวจสอบนอกเครื่องแบบ หน้าที่ของเขาคือจะเลือกสถานีหนึ่ง (เรียกว่า S เป็นศูนย์กลางของงานของเขา และจากสถานีนั้น จะเดินทางไปยังทุก ๆ สถานี สถานีละหนึ่งครั้ง การเดินทางของเขาจะมีเงื่อนไขดังนี้

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

เวลาที่ใช้ในการเดินทางแต่ละส่วนของรางนั้นเท่ากัน กล่าวคือ หนึ่งชั่วโมงพอดี

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

Periodicity (day1)

Source: [3]

โจทย์โดย Wojciech Rytter

Byteasar เป็นกษัตริย์ของ Bitotia มีความต้องการที่จะเปลี่ยนชื่อพลเมืองทุกคนในเมืองของเขา ชื่อของชาว Bitotian นั้นมักจะมีส่วนของชื่อที่ซ้ำ ๆ กัน เช่น Abiabuabiab มีคำว่า abiab ปรากฏซ้ำสองครั้ง Byteasar ต้องการเปลี่ยนชื่อพลเมืองให้เป็นลำดับของบิตที่มีความยาวเท่ากับชื่อเดิม และยังต้องการให้ชื่อใหม่นั้น ยังคงลักษณะการซ้ำกันของชื่อเดิมด้วย

ในส่วนต่อไป เราจะพิจารณาตัวอักษรพิมพ์ใหญ่และพิมพ์เล็กว่าเหมือนกัน สำหรับลำดับของตัวอักขระ (อาจจะเป็นตัวอักษรหรือบิตก็ได้) w = w1 w2 ... wk เราจะกล่าวว่าจำนวนเต็ม p เป็น รอบ (period) ของ w ถ้า wi = wi+p สำหรับทุก ๆ ค่า i=1,...,k-p เราจะเรียกเซตของรอบในสตริง w ว่า Per(w) เช่น Per(ABIABUABIAB) = {6,9}, Per(01001010010) = {5,8,10}, และ Per(0000) = {1,2,3}