CERC12

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

Kingdom (Problem A)

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

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

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

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

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

  • บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 20) ซึ่งระบุจำนวนของอาณาจักร
  • หลังจากนั้นอีก N บรรทัด แต่ละบรรทัดจะมีจำนวนเต็ม N ตัว จะระบุข้อมูลของหนี้ระหว่างแต่ละอาณาจักร จำนวนเต็มตัวที่ j ในบรรทัดที่ i คือค่า จำนวนเงินที่อาณาจักร i เป็นลูกหนี้ของอาณาจักร j รับประกันว่า และ สำหรับ และ

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

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

ตัวอย่าง

ข้อมูลนำเข้า ข้อมูลส่งออก

1
3
0 -3 1
3 0 -2
-1 2 0

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
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