CERC12 - ประวัติรุ่นแก้ไข

Nattee เมื่อ 13:37, 15 พฤษภาคม 2556

2013-05-15T13:37:56Z

แสดงการเปลี่ยนแปลง

Nattee เมื่อ 02:14, 15 พฤษภาคม 2556

2013-05-15T02:14:31Z

101.109.182.207 เมื่อ 02:04, 15 พฤษภาคม 2556

2013-05-15T02:04:32Z

Nattee เมื่อ 15:22, 14 พฤษภาคม 2556

2013-05-14T15:22:09Z

Nattee เมื่อ 15:21, 14 พฤษภาคม 2556

2013-05-14T15:21:34Z

Nattee เมื่อ 15:21, 14 พฤษภาคม 2556

2013-05-14T15:21:22Z

Nattee เมื่อ 14:41, 14 พฤษภาคม 2556

2013-05-14T14:41:58Z

Nattee เมื่อ 12:20, 14 พฤษภาคม 2556

2013-05-14T12:20:50Z

Nattee: หน้าที่ถูกสร้างด้วย '== Kingdom (Problem A) == อาณาจักรต่าง ๆ กำลังเข้าสู่วิกฤติทาง...'

2013-05-14T12:02:24Z

หน้าที่ถูกสร้างด้วย '== Kingdom (Problem A) == อาณาจักรต่าง ๆ กำลังเข้าสู่วิกฤติทาง...'

หน้าใหม่

== Kingdom (Problem A) ==

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

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

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

=== ข้อมูลนำเข้า ===
บรรทัดแรกประกอบด้วยจำนวนเต็ม T ซึ่งระบุถึงจำนวนชุดข้อมูลทดสอบทั้งหมด โดยที่แต่ละชุดข้อมูลทดสอบเป็นดังต่อไปนี้
* บรรทัดแรกประกอบด้วยจำนวนเต็ม N (1 <= N <= 20) ซึ่งระบุจำนวนของอาณาจักร
* หลังจากนั้นอีก N บรรทัด แต่ละบรรทัดจะมีจำนวนเต็ม N ตัว จะระบุข้อมูลของหนี้ระหว่างแต่ละอาณาจักร จำนวนเต็มตัวที่ j ในบรรทัดที่ i คือค่า <math>d_{ij}</math> จำนวนเงินที่อาณาจักร i เป็นลูกหนี้ของอาณาจักร j รับประกันว่า <math>d_{ii}=0</math> และ <math>d_{ij}=-d_{ji}</math> สำหรับ <math>1<=i,j<=N</math>และ <math>d_{ij}<=10^6</math>
=== ข้อมูลส่งออก ===
สำหรับแต่ละชุดข้อมูลทดสอบ ให้พิมพ์ผลลัพธ์หนึ่งบรรทัด โดยให้พิมพ์หมายเลขของอาณาจักรที่สามารถเหลืออยู่เป็นอาณาจักรสุดท้ายได้ โดยให้แสดงตัวเลขจากน้อยไปมาก ในกรณีที่ไม่มีอาณาจักรใดสามารถเหลืออยู่เป็นอาณาจักรสุดท้ายได้เลยให้พิมพ์ 0

=== ตัวอย่าง ===
{| class="wikitable"
|-
|ข้อมูลนำเข้า
|ข้อมูลส่งออก
|-
| style="vertical-align:top;"|
1 
3 
0 -3 1 
3 0 -2 
-1 2 0 
| style="vertical-align:top;"|
1 3
|}

@@ แถว 1: / แถว 1: @@
 โจทย์อยู่ใน grader เรียบร้อยแล้วครับ ทุกข้อมีเวลา 5 วินาที เม็มโมรี่ 512mb
+= ภาคเช้า =
 == Chemist's  Vow  (Problem C) ==
 ต้นฉบับ:[http://cerc.tcs.uj.edu.pl/2012/data/c.pdf]

@@ แถว 3: / แถว 3: @@
 == Chemist's  Vow  (Problem C) ==
-ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/c.pdf]]
+ต้นฉบับ:[http://cerc.tcs.uj.edu.pl/2012/data/c.pdf]
 นิปุนบอกว่าพอกันทีกับเลขและคอม โดยจะขอเปลี่ยนสายเป็นเคมีแทน เพื่อให้คุ้นเคยกับเคมีอย่างรวดเร็ว นิปุนสาบานว่าจะพูดคำภาษาอังกฤษ เฉพาะคำที่เกิดจากการเอาสัญลักษณ์ของธาตุต่าง ๆ มาต่อเข้าด้วยกันเท่านั้น ตัวอย่างเช่น นิปุน สามารถพุดคำว่า "I Am NiPuN" ได้ เพราะ I คือสัญลักษณ์ของ Iodine ส่วน Am คือ Ammonia Ni คือ Nickle, Pu คือ Plutonium และ N คือ Nitrogen เป็นต้น แน่นอนว่ามีคำบางคำที่นิปุนไม่สามารถพูดได้
@@ แถว 33: / แถว 33: @@
 == Kingdom  (Problem A) ==
-ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/a.pdf]]
+ต้นฉบับ:[http://cerc.tcs.uj.edu.pl/2012/data/a.pdf]
 อาณาจักรต่าง ๆ กำลังเข้าสู่วิกฤติทางการเงิน เนื่องมาจากอาณาจักรแต่ละแห่งแอบกู้หนี้ยืมสินกันไปมาระหว่างกันโดยไม่ให้คนอื่นรู้ อยู่มาวันหนึ่ง หนี้สินทั้งหลายก็เปิดเผยออกมา ทำให้ทุกคนรู้ว่าสุดท้ายแล้วคงหลีกเลี่ยงวิกฤติไม่พ้น
@@ แถว 65: / แถว 65: @@
 == Non-boring Sequence (Problem D) ==
-ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/d.pdf]]
+ต้นฉบับ:[http://cerc.tcs.uj.edu.pl/2012/data/d.pdf]
 ลำดับ (Sequence) จะถูกเรียกกว่าลำดับไม่น่าเบื่อ (non-boring) ก็ต่อเมื่อทุก ๆ ลำดับย่อยของลำดับนั้นมีสมาชิกอย่างน้อยหนึ่งตัวที่่ไม่เหมือนใครเลย (กำหนดให้ลำดับ A คือ <math><a_1a_2a_3...a_n></math> ลำดับย่อย (i,j) ของ  A คือ <math><a_ia_{i+1}a_{i+2}...a_j></math> เมื่อ i <= j)
@@ แถว 102: / แถว 102: @@
 == The Dragon and the knights (Problem I) ==
-ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/i.pdf]]
+ต้นฉบับ:[http://cerc.tcs.uj.edu.pl/2012/data/i.pdf]
 มังกรกำลังจะมาหากินที่เมืองกำแพงแสน เมืองกำแพงแสนนั้นเป็นแผ่นดินกว้างยาวเป็นอนันต์ โดยมีแม่น้ำซึ่งเป็นเส้นตรงยาวเป็นอนันต์เช่นกันไหลผ่าน และไม่มีแม่น้ำสามสายใด  ๆ ตัดกันที่จุดเดียวกัน (แต่อาจจะมีแม่น้ำสองสายที่ตัดกันก็ได้) แม่น้ำนี้แบ่งแผ่นดินออกเป็นเขตต่าง ๆ โดยมีแม่น้ำเป็นเส้นแบ่งเขต

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:22, 14 พฤษภาคม 2556
แถว 1:		แถว 1:
		+	โจทย์อยู่ใน grader เรียบร้อยแล้วครับ ทุกข้อมีเวลา 5 วินาที เม็มโมรี่ 512mb
		+
		+
	== Chemist's Vow (Problem C) ==		== Chemist's Vow (Problem C) ==
	ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/c.pdf]]		ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/c.pdf]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:21, 14 พฤษภาคม 2556
แถว 1:		แถว 1:
−	== Chemist's Vow (Problem C) ===	+	== Chemist's Vow (Problem C) ==
	ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/c.pdf]]		ต้นฉบับ: [[http://cerc.tcs.uj.edu.pl/2012/data/c.pdf]]

@@ แถว 1: / แถว 1: @@
 == Kingdom  (Problem A) ==
 อาณาจักรต่าง ๆ กำลังเข้าสู่วิกฤติทางการเงิน เนื่องมาจากอาณาจักรแต่ละแห่งแอบกู้หนี้ยืมสินกันไปมาระหว่างกันโดยไม่ให้คนอื่นรู้ อยู่มาวันหนึ่ง หนี้สินทั้งหลายก็เปิดเผยออกมา ทำให้ทุกคนรู้ว่าสุดท้ายแล้วคงหลีกเลี่ยงวิกฤติไม่พ้น
@@ แถว 31: / แถว 62: @@
 == Non-boring Sequence (Problem D) ==
 ลำดับ (Sequence) จะถูกเรียกกว่าลำดับไม่น่าเบื่อ (non-boring) ก็ต่อเมื่อทุก ๆ ลำดับย่อยของลำดับนั้นมีสมาชิกอย่างน้อยหนึ่งตัวที่่ไม่เหมือนใครเลย (กำหนดให้ลำดับ A คือ <math><a_1a_2a_3...a_n></math> ลำดับย่อย (i,j) ของ  A คือ <math><a_ia_{i+1}a_{i+2}...a_j></math> เมื่อ i <= j)
@@ แถว 67: / แถว 99: @@
 == The Dragon and the knights (Problem I) ==
 มังกรกำลังจะมาหากินที่เมืองกำแพงแสน เมืองกำแพงแสนนั้นเป็นแผ่นดินกว้างยาวเป็นอนันต์ โดยมีแม่น้ำซึ่งเป็นเส้นตรงยาวเป็นอนันต์เช่นกันไหลผ่าน และไม่มีแม่น้ำสามสายใด  ๆ ตัดกันที่จุดเดียวกัน (แต่อาจจะมีแม่น้ำสองสายที่ตัดกันก็ได้) แม่น้ำนี้แบ่งแผ่นดินออกเป็นเขตต่าง ๆ โดยมีแม่น้ำเป็นเส้นแบ่งเขต

@@ แถว 64: / แถว 64: @@
 non-boring<br />
 boring<br />
 |}

@@ แถว 28: / แถว 28: @@
 | style="vertical-align:top;"|
 3
 |}