CERC12

โจทย์อยู่ใน grader เรียบร้อยแล้วครับ ทุกข้อมีเวลา 5 วินาที เม็มโมรี่ 512mb

ภาคเช้า

Chemist's Vow (Problem C)

ต้นฉบับ:[1]

นิปุนบอกว่าพอกันทีกับเลขและคอม โดยจะขอเปลี่ยนสายเป็นเคมีแทน เพื่อให้คุ้นเคยกับเคมีอย่างรวดเร็ว นิปุนสาบานว่าจะพูดคำภาษาอังกฤษ เฉพาะคำที่เกิดจากการเอาสัญลักษณ์ของธาตุต่าง ๆ มาต่อเข้าด้วยกันเท่านั้น ตัวอย่างเช่น นิปุน สามารถพุดคำว่า "I Am NiPuN" ได้ เพราะ I คือสัญลักษณ์ของ Iodine ส่วน Am คือ Ammonia Ni คือ Nickle, Pu คือ Plutonium และ N คือ Nitrogen เป็นต้น แน่นอนว่ามีคำบางคำที่นิปุนไม่สามารถพูดได้

หน้าทีของคุณคือคำนวณว่านิปุนสามารถพูดคำที่กำหนดให้ได้หรือไม่ โดยไม่ต้องสนใจการเป็นตัวพิมพ์ใหญ่หรือพิมพ์เล็กของตัวอักษร

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบมีหนึ่งบรรทัดซึ่งประกอบด้วยสายอักขระความยาวไม่เกิน 50 000 ตัวอักษร ซึ่งประกอบด้วยตัวพิมพ์เล็กทั้งหมด (ไม่มีช่องว่าง)

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

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

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
4 international collegiate programming contest	YES NO NO NO

Kingdom (Problem A)

ต้นฉบับ:[2]

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

มีอาณาจักรอยู่ N แห่ง สำหรับคู่อาณาจักร (A,B) ใด ๆ จำนวนเงินที่ A เป็นลูกหนี้ B คือจำนวนเต็ม $D_{AB}$ โดยเราจะถือว่า $D_{AB}=-D_{BA}$ ถ้าอาณาจักรใดมีสถาณะการเงินสุทธิเป็นติดลบ (คือจำนวนเงินที่เป็นลูกหนี้ มากกว่า จำนวนเงินที่เป็นเจ้าหนี้) อาณาจักรนั้นอาจจะล้มละลายได้ ถ้าอาณาจักรล้มละลาย สถานะการเป็นหนี้ของอาณาจักรนั้น (ทั้งเจ้าหนี้และลูกหนี้) จะถือว่ายกเลิกไปทั้งหมด หลังจากอาณาจักรหนึ่งล้มละลายไป มันอาจจะทำให้อาณาจักรอื่น ๆ ล้มละลายตามกันไปด้วย จนกระทั่งเข้าสู่สถานะเสถียรซึ่งไม่มีอาณาจักรใดสามารถล้มละลายได้อีก

สถานะเสถียรนั้นอาจจะเป็นได้หลายกรณี ขึ้นอยู่กับอาณาจักรที่ล้มละลายเป็นที่แรก ในบางกรณีนั้นสถานะเสถียรนั้นอาจจะมีอาณาจักรเหลืออยู่เพียงแห่งเดียว หน้าที่ของคุณคือพิจารณาว่าอาณาจักรแต่ละแห่งนั้นมีโอกาสที่จะเป็นอาณาจักรสุดท้ายที่เหลืออยู่เพียงอาณาจักรเดียวในสถานะเสถียรได้หรือไม่

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 20) ซึ่งระบุจำนวนของอาณาจักร
• หลังจากนั้นอีก N บรรทัด แต่ละบรรทัดจะมีจำนวนเต็ม N ตัว จะระบุข้อมูลของหนี้ระหว่างแต่ละอาณาจักร จำนวนเต็มตัวที่ j ในบรรทัดที่ i คือค่า $d_{ij}$ จำนวนเงินที่อาณาจักร i เป็นลูกหนี้ของอาณาจักร j รับประกันว่า $d_{ii}=0$ และ $d_{ij}=-d_{ji}$ สำหรับ $1<=i,j<=N$และ $d_{ij}<=10^{6}$

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

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

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
1 3 0 -3 1 3 0 -2 -1 2 0	1 3

Non-boring Sequence (Problem D)

ต้นฉบับ:[3]

ลำดับ (Sequence) จะถูกเรียกกว่าลำดับไม่น่าเบื่อ (non-boring) ก็ต่อเมื่อทุก ๆ ลำดับย่อยของลำดับนั้นมีสมาชิกอย่างน้อยหนึ่งตัวที่่ไม่เหมือนใครเลย (กำหนดให้ลำดับ A คือ $<a_{1}a_{2}a_{3}...a_{n}>$ ลำดับย่อย (i,j) ของ A คือ $<a_{i}a_{i+1}a_{i+2}...a_{j}>$ เมื่อ i <= j)

จากลำดับที่กำหนดให้ ให้พิจารณาว่าลำดับดังกล่าวเป็นลำดับไม่น่าเบื่อหรือไม่

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 2 000 000) ซึ่งระบุความยาวของลำดับ
• บรรทัดถัดมาประกอบด้วยจำนวนเต็ม N ตัวซึ่งอธิบายลำดับที่ต้องการตรวจสอบ ตัวเลขแต่ละตัวเป็นจำนวนเต็มบวก มีค่าน้อยกว่า $10^{9}$

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

สำหรับข้อมูลทดสอบแต่ละชุด ให้พิมพ์ข้อความหนึ่งบรรทัดว่า non-boring ถ้าข้อมูลทดสอบชุดนั้นเป็นลำดับไม่น่าเบื่อ และให้พิมพ์คำว่า boring ในกรณีอื่น ๆ

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
4 5 1 2 3 4 5 5 1 1 1 1 1 5 1 2 3 2 1 5 1 1 2 1 1	non-boring boring non-boring boring

The Dragon and the knights (Problem I)

ต้นฉบับ:[4]

มังกรกำลังจะมาหากินที่เมืองกำแพงแสน เมืองกำแพงแสนนั้นเป็นแผ่นดินกว้างยาวเป็นอนันต์ โดยมีแม่น้ำซึ่งเป็นเส้นตรงยาวเป็นอนันต์เช่นกันไหลผ่าน และไม่มีแม่น้ำสามสายใด ๆ ตัดกันที่จุดเดียวกัน (แต่อาจจะมีแม่น้ำสองสายที่ตัดกันก็ได้) แม่น้ำนี้แบ่งแผ่นดินออกเป็นเขตต่าง ๆ โดยมีแม่น้ำเป็นเส้นแบ่งเขต

โชคดีที่มีอัศวิน คอยป้องกันดินแดนกำแพงแสนอยู่ มังกรจะไม่เข้ามาหากินในเขตที่มีอัศวินอย่างน้อยหนึ่งคน อย่างไรก็ตาม อัศวินนั้นถึงแม้จะรบเก่ง แต่ก็ int ต่ำ บางทีอัศวินอาจจะไปอยู่ในเขตเดียวกันหลายคน โดยที่บางเขตอาจจะไม่มีอัศวินเลยก็ได้

ให้ข้อมูลของแม่น้ำ และตำแหน่งของอัศวินแต่ละคน จงพิจารณาว่าทุก ๆ เขตในเมืองกำแพงแสนนั้นมีอัศวินอยู่หรือไม่

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้

• บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 100) ซึ่งระบุจำนวนของแม่น้ำ และ M (1 <= M <= 50 000) ซึ่งระบุจำนวนของอัศวิน
• อีก N บรรทัดถัดมาเป็นข้อมูลของแม่น้ำ บรรทัดละหนึ่งแม่น้ำ โดยแต่ละบรรทัดประกอบด้วยตัวเลขจำนวนเต็มสามตัว A B C (-10 000 <= A,B,C <= 10 000) ซึ่งระบุสัมประสิทธิ์ของสมการเส้นตรง Ax + By = C ซึ่งอธิบายถึงแม่น้ำหนึ่งเส้น
• อีก M บรรทัดถัดมาเป็นข้อมูลของอัศวิน บรรทัดละหนึ่งคน โดยแต่ละบรรทัดประกอบดว้ยตัวเลขจำนวนเต็มสองตัว X Y $(-10^{9}<=X,Y<=10^{9})$
• รับประกันว่า อัศวินไม่เคยยืนอยู่ในแม่น้ำ แต่อัศวินสองคนอาจจะยืนอยู่ตำแหน่งเดียวกันก็ได้ ไม่มีแม่น้ำสองสายใด ๆ ไหลทับกันทั้งเส้น และไม่มีแม่น้ำสามสายใด ๆ ที่ตัดกัน ณ จุดเดียวกัน

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

สำหรับข้อมูลทดสอบแต่ละชุด ให้พิมพ์ข้อความหนึ่งบรรทัดว่า PROTECTED ถ้าทุกเขตนั้นมีอัศวินอยู่อย่างน้อยหนึ่งคน และให้พิมพ์คำว่า VULNERABLE ในกรณีอื่น ๆ

ตัวอย่าง

ข้อมูลนำเข้า	ข้อมูลส่งออก
2 3 7 0 1 0 1 0 0 1 1 -3 1 1 5 -1 3 2 2 -2 -2 6 -1 -2 -8 4 1 1 0 1 0 0 1	PROTECTED VULNERABLE

ภาคค่ำ

Conservation (Problem J)

ต้นฉบับ:[5]

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

หน้าที่ของคุณคือคำนวณจำนวนครั้งน้อยสุดที่ต้องเคลื่อนย้ายรูปภาพไปมาระหว่างห้องปฏิบัติการ เราจะถือว่าตอนเริ่มต้นนั้นรูปอยู่ที่ห้องปฏิบัติการใดก็ได้

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม 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)

ต้นฉบับ:[6]

คุณมีสายอักขระสองตัวคือ 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)

ต้นฉบับ:[7] ศาสตร์ 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