|
|
| แถว 1: |
แถว 1: |
| − | = ภาคค่ำ =
| |
| − |
| |
| − | == Conservation (Problem J) ==
| |
| − | มีภาพเขียนอยู่รูปหนึ่งที่เก่ามาก และเราต้องการที่จะซ่อมแซ่มมันให้กลับมาดีดังเดิม มีห้องปฏิบัติการสองแห่งที่ต้องช่วยกันทำการซ่อมแซมนี้ การซ่อมแซมนั้นมีหลายขั้นตอน และเรารู้ว่าขั้นตอนไหนต้องทำที่ห้องปฏิบัติการใด อย่างไรก็ตาม เราไม่อยากที่จะขนย้ายรูปภาพไปมา เพราะมันบอบบางมาก ดังนั้น เราต้องวางแผนการทำงานให้มีการเคลื่อนย้ายรูปน้อยที่สุด ถ้าเป็นไปได้ เราอยากที่จะทำทุก ๆ ขั้นตอนที่ต้องใช้ห้องปฏิบัติการแรกให้เสร็จให้หมดก่อน แล้วค่อยขนย้ายไปห้องปฏิบัติการอีกแห่งหนึ่งเพื่อทำขั้นตอนที่เหลือ โชคร้ายที่ขั้นตอนหลายขั้นตอนมีความเกี่ยวข้องกัน คือ เราต้องทำงานบางขั้นตอนให้เสร็จก่อน ถึงจะทำขั้นตอนที่เกี่ยวข้องได้
| |
| − |
| |
| − | หน้าที่ของคุณคือคำนวณจำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ เราจะถือว่าตอนเริ่มต้นนั้นรูปอยู่ที่ห้องปฏิบัติการใดก็ได้
| |
| − |
| |
| − | === ข้อมูลนำเข้า ===
| |
| − | บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
| |
| − | * บรรทัดแรกประกอบด้วยเลขจำนวนเต็มสองตัวคือ N (1 <= N <= 1 000 000) ซึ่งระบุจำนวนของขั้นตอนทั้งหมด และ M (0 <= M <= 1 000 000) ซึ่งระบุจำนวนคู่ของขั้นตอนที่เกี่ยวข้องกัน
| |
| − | * บรรทัดถัดมามีจำนวนเต็ม N ตัว โดยตัวที่ i จะมีค่า 1 ก็ต่อเมื่องานชิ้นที่ i นั้นต้องทำที่ห้องปฏิบัติการแรก และมีค่า 2 ถ้าต้องทำที่ห้องปฏิบัติการแห่งที่ 2
| |
| − | * หลังจากนั้นอีก M บรรทัดจะเป็นข้อมูลความเกี่ยวข้องกันของขั้นตอนต่าง ๆ โดยแต่ละบรรทัดมีจำนวนเต็มสองตัวคือ i,j (1 <= i,j <= N) ซึ่งระบุว่า งานขั้นที่ i ต้องทำเสร็จก่อนขั้นที่ j
| |
| − | รับประกันว่าความเกี่ยวข้องนั้นจะไม่ทำให้เราไม่สามารถทำงานให้เสร็จได้
| |
| − | === ข้อมูลส่งออก ===
| |
| − | สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์จำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ
| |
| − | === ตัวอย่าง ===
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | |ข้อมูลนำเข้า
| |
| − | |ข้อมูลส่งออก
| |
| − | |-
| |
| − | | style="vertical-align:top;"|
| |
| − | 1<br />
| |
| − | 5 6<br />
| |
| − | 1 2 1 2 1<br />
| |
| − | 1 2<br />
| |
| − | 1 3<br />
| |
| − | 2 4<br />
| |
| − | 3 4<br />
| |
| − | 2 5<br />
| |
| − | 3 5<br />
| |
| − | | style="vertical-align:top;"|
| |
| − | 2
| |
| − | |}
| |
| − |
| |
| − | == Word equations (Problem E) ==
| |
| − | คุณมีสายอักขระสองตัวคือ T และ P เราอยากจะรู้ว่าเราสามารถลบอักขระบางตำแหน่งออกจาก T เพื่อทำให้ T มีหน้าตาเหมือน P ได้หรือไม่ ยกตัวอย่างเช่น จากคำว่า programming เราสามารถลบอักขระบางตัวจนกลายเป็นคำว่า pong หรือ program หรือ roaming ได้ แต่ไม่สามารถกลายเป็นคำว่า map ได้ (เพราะว่าเราไม่สามารถสลับที่ตัวอักษรได้) ทั้ง T และ P นั้นมีเฉพาะตัวอักษรพิมพ์เล็กในภาษาอังกฤษเท่านั้น
| |
| − |
| |
| − | แน่นอนว่าแค่นี้มันง่ายเกินไป T ที่ให้มานั้นจะอยู๋ในรูปแบบของระบบสมการ สมการแต่ละอันจะใช้สัญลักษณ์พิเศษ (ซึ่งก็คือคำที่ประกอบด้วยตัวพิมพ์ใหญ่ในภาษาอังกฤษเท่านั้น) โดยสัญลักษณ์แต่ละอันนั้นจะหมายถึงคำซึ่งประกอบด้วยตัวพิมพ์เล็กเท่านั้น สมการแต่ละอันจะอยู่ในรูปแบบใดรูปแบบหนึ่งต่อไปนี้เท่านั้น
| |
| − | * A = สายอักขระตัวพิมพ์เล็ก
| |
| − | * A = B + C
| |
| − | โดยที่ A, B, C คือสัญลักษณ์พิเศษใด ๆ และ + หมายถึงการเอาสายอักขระมาต่อกัน
| |
| − | รับประกันว่าระบบสมการจะมีคุณสมบัติดังนี้
| |
| − | * Unambiguous กล่าวคือ สำหรับสัญลักษณ์พิเศษ A ใด ๆ จะมีไม่เกินหนึ่งสมการที่มี A อยู่ด้านซ้ายของเครื่องหมาย = เท่านั้น
| |
| − | * Acyclic กล่าวคือ ถ้าเราเริ่มจากสัญลักษณ์พิเศษ A ใด ๆ แล้วทำการแทนที่ค่าในสมการไปเรื่อย ๆ เราจะไม่เจอสมการที่มี A อยู่ภายในอีก
| |
| − | ตัวอย่างเช่น
| |
| − | * START = FIRST + SECND
| |
| − | * FIRST = D + E
| |
| − | * SECND = F + E
| |
| − | * D = good
| |
| − | * E = times
| |
| − | * F = bad
| |
| − | สัญลักษณ์ START นั้นจะหมายถึงคำว่า goodtimesbadtimes
| |
| − |
| |
| − | กำหนดให้มีสายอักขระ P และสัญลักษณ์เริ่มต้น S จากระบบสมการ จงพิจารณาว่าเราสามารถสร้าง P จาก S ได้หรือไม่
| |
| − |
| |
| − | === ข้อมูลนำเข้า ===
| |
| − | บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
| |
| − | * บรรทัดแรกประกอบด้วยจำนวนเต็ม K (1 <= K <= 500) ซึ่งระบุถึงจำนวนของสมการทั้งหมดในระบบสมการ
| |
| − | * หลังจากนั้นอีก K บรรทัดเป็น ระบบสมการต่าง ๆ ตามรูปแบบที่กำหนดไว้ข้างต้น โดยจะมีช่องว่างหนึ่งตัวคั่นระหว่างเครื่องหมาย +, = และคำต่าง ๆ โดยที่คำต่าง ๆ นั้นมีความยาวอยู่ระหว่าง 1 ถึง 5 ตัวอักษร (รวมทั้งคำที่เป็นสัญลักษณ์พิเศษด้วย)
| |
| − | * บรรทัดถัดมาจะมีคำหนึ่งคำซึ่งหมายถึงสัษลักษณ์พิเศษ S
| |
| − | * บรรทัดสุดท้ายจะมีสายอักขระไม่ว่าง ที่ยาวไม่เกิน 2000 ตัวอักษร ซึ่งระบุถึงสายอักขระ P
| |
| − |
| |
| − | === ข้อมูลส่งออก ===
| |
| − | สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์คำว่า YES ถ้าเราสามารถสร้าง P จาก S ได้ และให้พิมพ์คำว่า NO ในกรณีอื่น ๆ
| |
| − | === ตัวอย่าง ===
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | |ข้อมูลนำเข้า
| |
| − | |ข้อมูลส่งออก
| |
| − | |-
| |
| − | | style="vertical-align:top;"|
| |
| − | 1<br />
| |
| − | 6<br />
| |
| − | START = FIRST + SECND<br />
| |
| − | FIRST = D + E<br />
| |
| − | SECND = F + E<br />
| |
| − | D = good<br />
| |
| − | E = times<br />
| |
| − | F = bad<br />
| |
| − | START<br />
| |
| − | debate<br />
| |
| − | | style="vertical-align:top;"|
| |
| − | YES<br />
| |
| − | |}
| |
| − |
| |
| − | == Who Wants to Live Forever (Problem B) ==
| |
| − | ศาสตร์ Digital Physics เป็นวิชาที่มีแนวคิดว่าจักรวาลของเรานั้นเป็นคอมพิวเตอร์ขนาดใหญ่ โดยที่เราเป็นเพียงโปรแกรมที่รันอยู่ในเครื่องคอมพิวเตอร์นั้นเท่านั้น
| |
| − |
| |
| − | เราอยากจะช่วยพัฒนาศาสตร์ทางด้าน Digital Physics ให้ดียิ่งขึ้น โดยเราจะพิจารณาแบบจำลองของจักรวาลแบบหนึ่งว่าแบบจำลองนี้มีจุดจบหรือไม่ หรือว่ามีการเปลี่ยนแปลงไปเรื่อย ๆ ตลอดเวลา
| |
| − |
| |
| − | จักรวาลนี้ประกอบด้วยบิตสตริงขนาด n ตัวอักษร (ตัวอักษรประกอบด้วย 1 หรือ 0 เท่านั้น) จักรวาลนี้เกิดขึ้นมาเป็นสายอักขระแบบหนึ่งทันที และหลังจากนั้นจักรวาลนี้จะเปลี่ยนแปลงตัวเองไปเรื่อย ๆ เป็นขั้น ๆ ไป โดยกฎของการเปลี่ยนแปลงนั้นเป็นดังนี้ สถานะของบิต ณ ตำแหน่งที่ i ในขั้นถัดไปนั้นขึ้นอยู่กับ บิต ณ ตำแหน่ง i-1 และ i+1 (ในกรณีที่ไม่มีบิต i-1 หรือ i+1 ให้ถือว่าบิตที่ไม่มีนั้นมีค่าเป็น 0) โดย บิตที่ i จะมีค่าเป็น 1 ก็ต่อเมื่อมี 1 อยู่เพียงอันเดียวเท่านั้นในตำแหน่งที่ i-1 และ i+1 ค่าของบิตในขั้นถัดไปจะคำนวณพร้อมกัน กล่าวคือ ค่าในขั้นถัดไปจะขึ้นอยู่กับค่าในขั้นปัจจุบันเท่านั้น
| |
| − |
| |
| − | เราจะถือว่าจักรวาลนั้นตาย ถ้าบิตสตริงของจักรวาลนั้นมีแต่เลข 0
| |
| − |
| |
| − | กำหนดสถานะของจักรวาล ณ จุดเริ่มต้นให้ จงคำนวณว่าจักรวาลดังกล่าวตาย หรือว่ามีการเปลี่ยนแปลงไปเรื่อย ๆ ตลอดเวลา
| |
| − |
| |
| − |
| |
| − | บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบประกอบด้วยสายอักขระของตัวเลข 0 หรือ 1 โดยมีความยาวอย่างน้อย 1 และยาวไม่เกิน 200 000 อักขระ
| |
| − | === ข้อมูลส่งออก ===
| |
| − | สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์คำว่า LIVES ถ้าจักรวาลนั้นไม่ตาย และให้พิมพ์คำว่า DIES ถ้าจักรวาลนั้นมีสถานะสุดท้ายเป็นตาย
| |
| − | === ตัวอย่าง ===
| |
| − | {| class="wikitable"
| |
| − | |-
| |
| − | |ข้อมูลนำเข้า
| |
| − | |ข้อมูลส่งออก
| |
| − | |-
| |
| − | | style="vertical-align:top;"|
| |
| − | 3<br />
| |
| − | 01<br />
| |
| − | 0010100<br />
| |
| − | 11011<br />
| |
| − | | style="vertical-align:top;"|
| |
| − | LIVES<br />
| |
| − | DIES<br />
| |
| − | LIVES<br />
| |
| − | |}
| |
| | | | |
| | == Graphic Madness (Problem K) == | | == Graphic Madness (Problem K) == |
Graphic Madness (Problem K)
มีการ์ดจออยู่สองยี่ห้อซึ่งมีโครงสร้างของแผงวงจรคล้ายกัน โดยแต่ละการ์ดนั้นจะประกอบด้วย ปม และ เส้นเชื่อมระหว่างปม ปมนั้นมีอยู่สองประเภทคือ ปมแบบ processor และปมแบบ socket โดยที่มีกฎของการเชื่อมต่อดังนี้อ
- ปมแบบ socket นั้นจะมีเส้นเชื่อมเส้นเดียวเชื่อมไปยังปมที่เป็นปม processor เท่านั้น
- ปม processor นั้นจะต้องเชื่อมต่อกับปมอื่น ๆ อย่างน้อยสองปม
- สำหรับปมสองปมใด ๆ จะมี path เชื่อระหว่างปมทั้่งสองปมนี้เพียง path เดียว กล่าวคือ graph ของปมและเส้นเชื่อมนี้จะเป็นต้นไม้เสมอ
เบ็นซ์ได้ซื้อการ์ดจอทั้งสองยี่ห้อมา ซึ่งบังเอิญมาก ๆที่การ์ดทั้งสองมีจำนวนปมที่เป็น socket เท่ากัน และด้วยความเพ้อ ทำให้เบนซ์ได้เชื่อมต่อวงจรของการ์ดทั้งสองเข้าด้วยกันด้วยการหาสายสัญญาณมาเชื่อมต่อ socket ของแต่ละการ์ดเข้าด้วยกัน โดยการเชื่อมต่อนี้จะไม่เชื่อมต่อ socket ซ้ำกันเลย และเป็นการเชื่อมต่อระหว่างการ์ดหนึ่งไปยังอีกการ์ดหนึ่งเท่านั้น (ดูรูปประกอบ)
เบ็นซ์อยากจะเค้นพลังของการ์ดจอออมาให้มากที่สุด โดยเบ็นซ์จะต้องหา path ของการเดินทางของสัญญาณโดยที่ path นี้จะต้องเดินทางผ่นปมทั้งหมดของทั้งสองการ์ดปมละหนึ่งครั้งพอดี และกลับมาจบที่ปมเริ่มต้นเสมอ หน้าที่ของคุณคือช่วยเบ็นซ์คำนวณว่ามี path ดังกล่าวหรือไม่
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
- บรรทัดแรกประกอบด้วยจำนวนเต็มสามตัว k,n,m (2 <= k <= 1 000; 1 <= n,m <= 1 000) ซั่งระบุถึงจำนวนของ socket, จำนวนของ processor ในการ์ดแรก, จำนวนของ processor ในการ์ดสอง ตามลำดับ เรากำหนดให้ปมต่าง ๆ ของการ์ดทั้ง 2 มีสัญลักษณ์ดังต่อไปนี้
- AS1, AS2, ..., ASk คือปม socket ของการ์ดแรก
- AP1, AP2, ..., APn คือปม processor ของการ์ดแรก
- BS1, BS2, ..., BSk คือปม socket ของการ์ดสอง
- BP1, BP2, ..., BPm คือปม processor ของการ์ดสอง
- หลังจากนั้นอีก n - k + 1 บรรทัดจะเป็นการอธิบายการเชื่อมต่อของการ์ดแรก โดยที่แต่ละบรรทัดจะประกอบด้วยชื่อมของการ์ดใบแรกสองปม ซึ่งระบุว่ามีเส้นเชื่อมระหว่างปมทั้งสอง
- หลังจากนั้นจะคั่นด้วยบรรทัดว่างหนึ่งบรรทัด
- หลังจากนั้นอีก m - k + 1 บรรทัดจะเป็นการอธิบายการเชื่อมต่อของการ์ดสองในรูปแบบเดียวกัน
- หลังจากนั้นจะคั่นด้วยบรรทัดว่างหนึ่งบรรทัด
- k บรรทัดสุดท้ายอธิบายถึงสายสัญญาณที่เชื่อมต่อระหว่างการ์ด โดยที่แต่ละบรรทัดจะมีชื่อปม socket อยู่สองปม โดยทั้งสองปมเป็นของการ์ดคนละตัว และปม socket แต่ละปมนั้นจะปรากฎเพียงครั้งเดียว
- จะมีบรรทัดว่างตามท้ายอีกหนึ่งบรรทัด ยกเว้นข้อมูลทดสอบชุดสุดท้าย
ข้อมูลส่งออก
ตัวอย่าง
