ผลต่างระหว่างรุ่นของ "Poi18"
Jittat (คุย | มีส่วนร่วม) |
|||
(ไม่แสดง 7 รุ่นระหว่างกลางโดยผู้ใช้ 1 คน) | |||
แถว 3: | แถว 3: | ||
=== Party (day1) === | === Party (day1) === | ||
Source: [http://main.edu.pl/en/archive/oi/18/imp] | Source: [http://main.edu.pl/en/archive/oi/18/imp] | ||
+ | |||
+ | โจทย์โดย Jakub Onufry Wojtaszczyk | ||
Byteasar ต้องการจัดปาร์ตีให้สุดยอด และมันจะสุดยอดได้แน่ ๆ ถ้าแขกทุกคนรู้จักกันทั้งหมด เขาพยายามจะหารายการของแขกที่จะเชิญมาให้ได้แบบนั้น | Byteasar ต้องการจัดปาร์ตีให้สุดยอด และมันจะสุดยอดได้แน่ ๆ ถ้าแขกทุกคนรู้จักกันทั้งหมด เขาพยายามจะหารายการของแขกที่จะเชิญมาให้ได้แบบนั้น | ||
แถว 15: | แถว 17: | ||
โจทย์โดย Wojciech Rytter และ Bartosz Szreder. | โจทย์โดย Wojciech Rytter และ Bartosz Szreder. | ||
− | ระบบรางรถไฟของ Byteotian Railways (BR) ประกอบด้วยส่วนของรางเชื่อมระหว่างสถานีที่สามารถเดินทางได้สองทาง | + | ระบบรางรถไฟของ Byteotian Railways (BR) ประกอบด้วยส่วนของรางเชื่อมระหว่างสถานีที่สามารถเดินทางได้สองทาง แต่ละคู่ของสถานีจะเชื่อมกันด้วยส่วนของรางเชื่อมไม่เกินหนึ่งเส้น นอกจากนี้ ระหว่างคู่ของสถานีใด ๆ จะมีเส้นทางเชื่อมถึงกันแค่เส้นเดียว (เส้นทางนั้นอาจจะใช้ส่วนของรางหลายส่วน แต่จะต้องไม่ผ่านสถานีใด ๆ มากกว่าหนึ่งครั้ง) |
Byteasar เป็นผู้ตรวจสอบนอกเครื่องแบบ หน้าที่ของเขาคือจะเลือกสถานีหนึ่ง (เรียกว่า '''S''' เป็นศูนย์กลางของงานของเขา และจากสถานีนั้น จะเดินทางไปยังทุก ๆ สถานี สถานีละหนึ่งครั้ง การเดินทางของเขาจะมีเงื่อนไขดังนี้ | Byteasar เป็นผู้ตรวจสอบนอกเครื่องแบบ หน้าที่ของเขาคือจะเลือกสถานีหนึ่ง (เรียกว่า '''S''' เป็นศูนย์กลางของงานของเขา และจากสถานีนั้น จะเดินทางไปยังทุก ๆ สถานี สถานีละหนึ่งครั้ง การเดินทางของเขาจะมีเงื่อนไขดังนี้ | ||
แถว 31: | แถว 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}''' | ||
+ | |||
+ | Byteasar ตัดสินใจว่า ทุก ๆ ชื่อจะต้องเปลี่ยนเป็นลำดับของบิต โดยที่ | ||
+ | |||
+ | * มีความยาวเท่ากับชื่อเดิม | ||
+ | * มีเซตของรอบเท่ากับชื่อเดิม | ||
+ | * และเป็นชื่อที่มีลำดับ lexicographical น้อยที่สุดในบรรดาบิตสตริงทั้งหมดที่สอดคล้องกับเงื่อนไขทั้งสอง | ||
+ | |||
+ | ยกตัวอย่างเช่น ชื่อ ABIABUABIAB จะถูกเปลี่ยนเป็น 01001101001, BABBAB เป็น 010010, และ BABURBAB เป็น 01000010 | ||
+ | |||
+ | Byteasar ให้คุณเขียนโปรแกรมเพื่อช่วยในการเปลี่ยนชื่อครั้งนี้ ถ้าคุณทำสำเร็จ คุณอาจจะเก็บชื่อเดิมของคุณไว้ก็ได้! | ||
+ | |||
+ | === Meteors (day2) === | ||
+ | Source: http://main.edu.pl/en/archive/oi/18/met | ||
+ | |||
+ | โจทย์โดย: Paweł Mechlinski และ Jakub Pachocki | ||
+ | |||
+ | Byteotian Interstellar Union (BIU) ได้ค้นพบดาวเคราะห์ดวงใหม่ ดาวดวงนี้ไม่เหมาะต่อการอยู่อาศัยเนื่องจากมีพายุดาวตก แต่นั่นก็ทำให้เป็นดาวที่เหมาะจะศึกษาเกี่ยวกับอวกาศ | ||
+ | |||
+ | แต่ละรัฐที่เป็นสมาชิกของ BIU ได้วางสถานีอวกาศอยู่ใกล้กับวงโคจรของดาวดังกล่าว เป้าหมายของสถานีอวกาศเหล่านี้คือการเก็บตัวอย่างสะเก็ดหินดาวตกที่วิ่งผ่าน ทาง BIU ได้แบ่งวงโคจรของดาวเคราะห์ออกเป็น '''m''' เซคเตอร์ โดยที่เซคเตอร์ '''1''' จะติดกับเซคเตอร์ '''m''' ในแต่ละเซคเตอร์จะมีสถานีอวกาศหนึ่งสถานี ซึ่งเป็นของรัฐที่เป็นสมาชิกหนึ่ง จากรัฐจำนวน '''n''' รัฐที่เป็นสมาชิกของ BIU | ||
+ | |||
+ | แต่ละรัฐได้ประกาศล่วงหน้าเกี่ยวกับจำนวนสะเก็ดดาวตกที่ต้องการเก็บ งานของคุณคือคำนวณเวลาที่แต่ละรัฐจะสามารถหยุดการเก็บสะเก็ดดาวเนื่องจากได้จำนวนสะเก็ดดาวตามเป้าหมายแล้ว | ||
+ | |||
+ | '''Input''' | ||
+ | |||
+ | บรรทัดแรกระบุจำนวนเต็ม '''n''' และ '''m''' ('''1 <= n,m <= 300000) แทนจำนวนรัฐที่เป็นสมาชิกของ BIU และจำนวนเซคเตอร์ของวงโคจร | ||
+ | |||
+ | บรรทัดที่สอง ระบุจำนวนเต็ม '''m''' จำนวน '''oi''' ('''1 <= oi <= n''') แทนหมายเลขของรัฐที่เป็นเจ้าของสถานีอวกาศที่เซกเตอร์ '''i''' | ||
+ | |||
+ | บรรทัดที่สาม ระบุจำนวนเต็ม '''n''' จำนวน '''pi''' ('''1 <= pi <= 10<sup>9</sup>''') แทนจำนวนสะเก็ดดาวที่รัฐที่ '''i''' ตั้งเป้าจะเก็บ | ||
+ | |||
+ | บรรทัดที่สี่ระบุจำนวนเต็ม '''k''' ('''1 <= k <= 300,000''') แทนจำนวนเหตุการณ์ฝนดาวตกที่ทำนายว่าจะเกิดขึ้น จากนั้นอีก '''k''' บรรทัด ระบุข้อมูลเกี่ยวกับฝนดาวตก บรรทัดที่ '''i''' ของข้อมูลชุดนี้ ระบุจำนวนเต็มสามจำนวน '''li, ri, ai''' เพื่อบอกว่า จะมีฝนดาวตกเกิดขึ้นในเซกเตอร์ '''li, li+1,..., ri''' (ถ้า '''li <= ri''') หรือ '''li,li+1,...,m,1,...ri''' (ถ้า '''li > ri''') ฝนดาวตกนี้จะทำให้สถานีอวกาศที่อยู่ในเซกเตอร์ดังกล่าวทุกสถานีเก็บตัวอย่างสะเก็ดดาวได้สถานีละ '''ai''' ชิ้น | ||
+ | |||
+ | ในข้อมูลชุดทดสอบที่มีคะแนนรวมไม่น้อยกว่า 20%: '''n,m,k <= 1 000''' |
รุ่นแก้ไขปัจจุบันเมื่อ 15:02, 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}
Byteasar ตัดสินใจว่า ทุก ๆ ชื่อจะต้องเปลี่ยนเป็นลำดับของบิต โดยที่
- มีความยาวเท่ากับชื่อเดิม
- มีเซตของรอบเท่ากับชื่อเดิม
- และเป็นชื่อที่มีลำดับ lexicographical น้อยที่สุดในบรรดาบิตสตริงทั้งหมดที่สอดคล้องกับเงื่อนไขทั้งสอง
ยกตัวอย่างเช่น ชื่อ ABIABUABIAB จะถูกเปลี่ยนเป็น 01001101001, BABBAB เป็น 010010, และ BABURBAB เป็น 01000010
Byteasar ให้คุณเขียนโปรแกรมเพื่อช่วยในการเปลี่ยนชื่อครั้งนี้ ถ้าคุณทำสำเร็จ คุณอาจจะเก็บชื่อเดิมของคุณไว้ก็ได้!
Meteors (day2)
Source: http://main.edu.pl/en/archive/oi/18/met
โจทย์โดย: Paweł Mechlinski และ Jakub Pachocki
Byteotian Interstellar Union (BIU) ได้ค้นพบดาวเคราะห์ดวงใหม่ ดาวดวงนี้ไม่เหมาะต่อการอยู่อาศัยเนื่องจากมีพายุดาวตก แต่นั่นก็ทำให้เป็นดาวที่เหมาะจะศึกษาเกี่ยวกับอวกาศ
แต่ละรัฐที่เป็นสมาชิกของ BIU ได้วางสถานีอวกาศอยู่ใกล้กับวงโคจรของดาวดังกล่าว เป้าหมายของสถานีอวกาศเหล่านี้คือการเก็บตัวอย่างสะเก็ดหินดาวตกที่วิ่งผ่าน ทาง BIU ได้แบ่งวงโคจรของดาวเคราะห์ออกเป็น m เซคเตอร์ โดยที่เซคเตอร์ 1 จะติดกับเซคเตอร์ m ในแต่ละเซคเตอร์จะมีสถานีอวกาศหนึ่งสถานี ซึ่งเป็นของรัฐที่เป็นสมาชิกหนึ่ง จากรัฐจำนวน n รัฐที่เป็นสมาชิกของ BIU
แต่ละรัฐได้ประกาศล่วงหน้าเกี่ยวกับจำนวนสะเก็ดดาวตกที่ต้องการเก็บ งานของคุณคือคำนวณเวลาที่แต่ละรัฐจะสามารถหยุดการเก็บสะเก็ดดาวเนื่องจากได้จำนวนสะเก็ดดาวตามเป้าหมายแล้ว
Input
บรรทัดแรกระบุจำนวนเต็ม n และ m (1 <= n,m <= 300000) แทนจำนวนรัฐที่เป็นสมาชิกของ BIU และจำนวนเซคเตอร์ของวงโคจร
บรรทัดที่สอง ระบุจำนวนเต็ม m จำนวน oi (1 <= oi <= n) แทนหมายเลขของรัฐที่เป็นเจ้าของสถานีอวกาศที่เซกเตอร์ i
บรรทัดที่สาม ระบุจำนวนเต็ม n จำนวน pi (1 <= pi <= 109) แทนจำนวนสะเก็ดดาวที่รัฐที่ i ตั้งเป้าจะเก็บ
บรรทัดที่สี่ระบุจำนวนเต็ม k (1 <= k <= 300,000) แทนจำนวนเหตุการณ์ฝนดาวตกที่ทำนายว่าจะเกิดขึ้น จากนั้นอีก k บรรทัด ระบุข้อมูลเกี่ยวกับฝนดาวตก บรรทัดที่ i ของข้อมูลชุดนี้ ระบุจำนวนเต็มสามจำนวน li, ri, ai เพื่อบอกว่า จะมีฝนดาวตกเกิดขึ้นในเซกเตอร์ li, li+1,..., ri (ถ้า li <= ri) หรือ li,li+1,...,m,1,...ri (ถ้า li > ri) ฝนดาวตกนี้จะทำให้สถานีอวกาศที่อยู่ในเซกเตอร์ดังกล่าวทุกสถานีเก็บตัวอย่างสะเก็ดดาวได้สถานีละ ai ชิ้น
ในข้อมูลชุดทดสอบที่มีคะแนนรวมไม่น้อยกว่า 20%: n,m,k <= 1 000