ผลต่างระหว่างรุ่นของ "Poi18"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 13: | แถว 13: | ||
Source: [http://main.edu.pl/en/archive/oi/18/ins] | Source: [http://main.edu.pl/en/archive/oi/18/ins] | ||
| + | โจทย์โดย Wojciech Rytter และ Bartosz Szreder. | ||
| + | |||
| + | ระบบรางรถไฟของ Byteotian Railways (BR) ประกอบด้วยส่วนของรางเชื่อมระหว่างสถานีที่สามารถเดินทางได้สองทาง แต่ละคู่ของสถานีจะเชื่อมกันด้วยส่วนของรามเชื่อมไม่เกินหนึ่งเส้น นอกจากนี้ ระหว่างคู่ของสถานีใด ๆ จะมีเส้นทางเชื่อมถึงกันแค่เส้นเดียว (เส้นทางนั้นอาจจะใช้ส่วนของรางหลายส่วน แต่จะต้องไม่ผ่านสถานีใด ๆ มากกว่าหนึ่งครั้ง) | ||
| + | |||
| + | Byteasar เป็นผู้ตรวจสอบนอกเครื่องแบบ หน้าที่ของเขาคือจะเลือกสถานีหนึ่ง (เรียกว่า '''S''' เป็นศูนย์กลางของงานของเขา และจากสถานีนั้น จะเดินทางไปยังทุก ๆ สถานี สถานีละหนึ่งครั้ง การเดินทางของเขาจะมีเงื่อนไขดังนี้ | ||
| + | |||
| + | * Byteasar เริ่มที่สถานี '''S''' | ||
| + | * เขาจะเลือกสถานีที่ยังไม่ได้ไปตรวจสอบ และเดินทางไปยังสถานีนั้น, ตรวจสอบ, และเดินทางกลับไปยัง '''S''' | ||
| + | * พนักงานที่โดนตรวจสอบจะแจ้งเพื่อน ๆ ถึงการมาถึงของ Byteasar ทำให้เขาต้องหาทางหลอกพนักงานเหล่านั้น โดยในรอบถัดไปเขาจะต้องเลือกสถานีที่ในการเดินทางออกจาก '''S''' จะต้องไม่ใช่ทิศทางเดิมที่เพิ่งออกไปเมื่อรอบที่แล้ว (นั่นคือ ใช้ส่วนของรางอื่นที่ออกจาก '''S''') | ||
| + | * ทุกสถานี (ยกเว้น '''S''') จะถูกตรวจสอบหนึ่งครั้งพอดี | ||
| + | * เมื่อตรวจสอบสถานีสุดท้ายเสร็จ Byteasar จะไม่กลับไป '''S''' อีก | ||
| + | |||
| + | เวลาที่ใช้ในการเดินทางแต่ละส่วนของรางนั้นเท่ากัน กล่าวคือ หนึ่งชั่วโมงพอดี | ||
| + | |||
| + | Byteasar ต้องการจะพิจารณาสถานีเริ่มต้น '''S''' ที่เป็นไปได้ทุก ๆ สถานี นั่นคือ ในแต่ละสถานี เขาต้องการทราบว่า ถ้าเขาใช้สถานีนั้นเป็นสถานี '''S''' เวลาที่ใช้ในเดินทางเพื่อการตรวจสอบทุก ๆ สถานีอื่นจะเป็นเท่าใด (ถ้าเป็นไปได้) | ||
=== Periodicity (day1) === | === Periodicity (day1) === | ||
Source: [http://main.edu.pl/en/archive/oi/18/okr] | Source: [http://main.edu.pl/en/archive/oi/18/okr] | ||
รุ่นแก้ไขเมื่อ 08:58, 17 พฤษภาคม 2556
Stage III
Party (day1)
Source: [1]
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]
