CERC12

Kingdom (Problem A)

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

มีอาณาจักรอยู่ 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)

ลำดับ (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)

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

โชคดีที่มีอัศวิน คอยป้องกันดินแดนกำแพงแสนอยู่ มังกรจะไม่เข้ามาหากินในเขตที่มีอัศวินอย่างน้อยหนึ่งคน อย่างไรก็ตาม อัศวินนั้นถึงแม้จะรบเก่ง แต่ก็ 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