CERC12
เนื้อหา
Kingdom (Problem A)
อาณาจักรต่าง ๆ กำลังเข้าสู่วิกฤติทางการเงิน เนื่องมาจากอาณาจักรแต่ละแห่งแอบกู้หนี้ยืมสินกันไปมาระหว่างกันโดยไม่ให้คนอื่นรู้ อยู่มาวันหนึ่ง หนี้สินทั้งหลายก็เปิดเผยออกมา ทำให้ทุกคนรู้ว่าสุดท้ายแล้วคงหลีกเลี่ยงวิกฤติไม่พ้น
มีอาณาจักรอยู่ N แห่ง สำหรับคู่อาณาจักร (A,B) ใด ๆ จำนวนเงินที่ A เป็นลูกหนี้ B คือจำนวนเต็ม โดยเราจะถือว่า ถ้าอาณาจักรใดมีสถาณะการเงินสุทธิเป็นติดลบ (คือจำนวนเงินที่เป็นลูกหนี้ มากกว่า จำนวนเงินที่เป็นเจ้าหนี้) อาณาจักรนั้นอาจจะล้มละลายได้ ถ้าอาณาจักรล้มละลาย สถานะการเป็นหนี้ของอาณาจักรนั้น (ทั้งเจ้าหนี้และลูกหนี้) จะถือว่ายกเลิกไปทั้งหมด หลังจากอาณาจักรหนึ่งล้มละลายไป มันอาจจะทำให้อาณาจักรอื่น ๆ ล้มละลายตามกันไปด้วย จนกระทั่งเข้าสู่สถานะเสถียรซึ่งไม่มีอาณาจักรใดสามารถล้มละลายได้อีก
สถานะเสถียรนั้นอาจจะเป็นได้หลายกรณี ขึ้นอยู่กับอาณาจักรที่ล้มละลายเป็นที่แรก ในบางกรณีนั้นสถานะเสถียรนั้นอาจจะมีอาณาจักรเหลืออยู่เพียงแห่งเดียว หน้าที่ของคุณคือพิจารณาว่าอาณาจักรแต่ละแห่งนั้นมีโอกาสที่จะเป็นอาณาจักรสุดท้ายที่เหลืออยู่เพียงอาณาจักรเดียวในสถานะเสถียรได้หรือไม่
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
- บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 20) ซึ่งระบุจำนวนของอาณาจักร
- หลังจากนั้นอีก N บรรทัด แต่ละบรรทัดจะมีจำนวนเต็ม N ตัว จะระบุข้อมูลของหนี้ระหว่างแต่ละอาณาจักร จำนวนเต็มตัวที่ j ในบรรทัดที่ i คือค่า จำนวนเงินที่อาณาจักร i เป็นลูกหนี้ของอาณาจักร j รับประกันว่า และ สำหรับ และ
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์หมายเลขของอาณาจักรที่สามารถเหลืออยู่เป็นอาณาจักรสุดท้ายได้ โดยให้แสดงตัวเลขจากน้อยไปมาก ในกรณีที่ไม่มีอาณาจักรใดสามารถเหลืออยู่เป็นอาณาจักรสุดท้ายได้เลยให้พิมพ์ 0
ตัวอย่าง
ข้อมูลนำเข้า | ข้อมูลส่งออก |
1 |
1 3 |
Non-boring Sequence (Problem D)
ลำดับ (Sequence) จะถูกเรียกกว่าลำดับไม่น่าเบื่อ (non-boring) ก็ต่อเมื่อทุก ๆ ลำดับย่อยของลำดับนั้นมีสมาชิกอย่างน้อยหนึ่งตัวที่่ไม่เหมือนใครเลย (กำหนดให้ลำดับ A คือ ลำดับย่อย (i,j) ของ A คือ เมื่อ i <= j)
จากลำดับที่กำหนดให้ ให้พิจารณาว่าลำดับดังกล่าวเป็นลำดับไม่น่าเบื่อหรือไม่
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
- บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 2 000 000) ซึ่งระบุความยาวของลำดับ
- บรรทัดถัดมาประกอบด้วยจำนวนเต็ม N ตัวซึ่งอธิบายลำดับที่ต้องการตรวจสอบ ตัวเลขแต่ละตัวเป็นจำนวนเต็มบวก มีค่าน้อยกว่า
ข้อมูลส่งออก
สำหรับข้อมูลทดสอบแต่ละชุด ให้พิมพ์ข้อความหนึ่งบรรทัดว่า non-boring ถ้าข้อมูลทดสอบชุดนั้นเป็นลำดับไม่น่าเบื่อ และให้พิมพ์คำว่า boring ในกรณีอื่น ๆ
ตัวอย่าง
ข้อมูลนำเข้า | ข้อมูลส่งออก |
4 |
non-boring |