พูดคุย:CERC12

ภาคค่ำ

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

รับประกันว่าความเกี่ยวข้องนั้นจะไม่ทำให้เราไม่สามารถทำงานให้เสร็จได้

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์จำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
1 5 6 1 2 1 2 1 1 2 1 3 2 4 3 4 2 5 3 5	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 ในกรณีอื่น ๆ

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
1 6 START = FIRST + SECND FIRST = D + E SECND = F + E D = good E = times F = bad START debate	YES

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 ถ้าจักรวาลนั้นมีสถานะสุดท้ายเป็นตาย

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
3 01 0010100 11011	LIVES DIES LIVES

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 แต่ละปมนั้นจะปรากฎเพียงครั้งเดียว
• จะมีบรรทัดว่างตามท้ายอีกหนึ่งบรรทัด ยกเว้นข้อมูลทดสอบชุดสุดท้าย