พูดคุย: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