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

Jittat เมื่อ 23:35, 9 กรกฎาคม 2558

2015-07-09T23:35:19Z

Jittat: /* Problem 1: Mowing the Lawn [Neal Wu, 2008] */

2015-07-09T23:33:28Z

Problem 1: Mowing the Lawn [Neal Wu, 2008]

Jittat: /* Problem 3: Soldering [Michael Cohen, 2011] */

2013-06-29T09:11:06Z

Problem 3: Soldering [Michael Cohen, 2011]

Jittat เมื่อ 08:13, 29 มิถุนายน 2556

2013-06-29T08:13:29Z

Jittat: /* Problem 1: Mowing the Lawn [Neal Wu, 2008] */

2013-06-29T08:05:32Z

Problem 1: Mowing the Lawn [Neal Wu, 2008]

Jittat: หน้าที่ถูกสร้างด้วย '== USACO OPEN 2011 == === Problem 1: Mowing the Lawn [Neal Wu, 2008] === === Problem 2: Odd degrees [Traditional, 2011] === === Prob...'

2013-06-29T07:59:29Z

หน้าที่ถูกสร้างด้วย '== USACO OPEN 2011 == === Problem 1: Mowing the Lawn [Neal Wu, 2008] === === Problem 2: Odd degrees [Traditional, 2011] === === Prob...'

หน้าใหม่

== USACO OPEN 2011 ==

=== Problem 1: Mowing the Lawn [Neal Wu, 2008] ===

=== Problem 2: Odd degrees [Traditional, 2011] ===

=== Problem 3: Soldering [Michael Cohen, 2011] ===

@@ แถว 92: / แถว 92: @@
    \ /
 ---4
 === Problem 3: Soldering [Michael Cohen, 2011] ===
@@ แถว 106: / แถว 174: @@
 มี partial feedback สำหรับการส่ง 50 ครั้งแรก

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 23:33, 9 กรกฎาคม 2558
แถว 8:		แถว 8:

	FJ สังเกตว่าวัวตัวที่อยู่ติดกันมักรู้จักวัวตัวอื่น เขายังทราบว่าถ้าเขาเลือกวัวมากกว่า K ตัวติดกัน (1 <= K <= N) วัวเหล่านั้นจะไม่ทำงานและเริ่มจัดงานเลี้ยงแทน ดังนั้น FJ จึงต้องการให้คุณช่วยเลือกวัว ให้ได้ผลรวมของประสิทธิภาพมากที่สุด โดยที่ไม่เลือกวัว K ตัวติดกันเลย		FJ สังเกตว่าวัวตัวที่อยู่ติดกันมักรู้จักวัวตัวอื่น เขายังทราบว่าถ้าเขาเลือกวัวมากกว่า K ตัวติดกัน (1 <= K <= N) วัวเหล่านั้นจะไม่ทำงานและเริ่มจัดงานเลี้ยงแทน ดังนั้น FJ จึงต้องการให้คุณช่วยเลือกวัว ให้ได้ผลรวมของประสิทธิภาพมากที่สุด โดยที่ไม่เลือกวัว K ตัวติดกันเลย
		+
		+	'''Full task description (mirrored from [http://tjsct.wikidot.com/usaco-open11-gold])'''
		+
		+	<pre>
		+	Problem 1: Mowing the Lawn [Neal Wu, 2008]
		+
		+	After winning the annual town competition for best lawn a year ago,
		+	Farmer John has grown lazy; he has not mowed the lawn since then
		+	and thus his lawn has become unruly. However, the competition is
		+	once again coming soon, and FJ would like to get his lawn into
		+	tiptop shape so that he can claim the title.
		+
		+	Unfortunately, FJ has realized that his lawn is so unkempt that he
		+	will need to get some of his N (1 <= N <= 100,000) cows, who are
		+	lined up in a row and conveniently numbered 1..N, to help him. Some
		+	cows are more efficient than others at mowing the lawn; cow i has
		+	efficiency E_i (0 <= E_i <= 1,000,000,000).
		+
		+	FJ has noticed that cows near each other in line often know each
		+	other well; he has also discovered that if he chooses more than K
		+	(1 <= K <= N) consecutive (adjacent) cows to help him, they will
		+	ignore the lawn and start a party instead. Thus, FJ needs you to
		+	assist him: determine the largest total cow efficiency FJ can obtain
		+	without choosing more than K consecutive cows.
		+
		+	PROBLEM NAME: mowlawn
		+
		+	INPUT FORMAT:
		+
		+	* Line 1: Two space-separated integers: N and K
		+
		+	* Lines 2..N+1: Line i+1 contains the single integer: E_i
		+
		+	SAMPLE INPUT (file mowlawn.in):
		+
		+	5 2
		+	1
		+	2
		+	3
		+	4
		+	5
		+
		+	INPUT DETAILS:
		+
		+	FJ has 5 cows whose efficiencies are 1, 2, 3, 4, and 5, in that
		+	order. He wants to choose some of the cows such that their total
		+	efficiency is maximized, but he cannot choose more than 2 consecutive
		+	cows.
		+
		+	OUTPUT FORMAT:
		+
		+	* Line 1: A single integer that is the best total efficiency FJ can
		+	obtain.
		+
		+	SAMPLE OUTPUT (file mowlawn.out):
		+
		+	12
		+
		+	OUTPUT DETAILS:
		+
		+	FJ chooses all cows but the third. The total efficiency of the cows is thus
		+	1 + 2 + 4 + 5 = 12.
		+	</pre>

	=== Problem 2: Odd degrees [Traditional, 2011] ===		=== Problem 2: Odd degrees [Traditional, 2011] ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:11, 29 มิถุนายน 2556
แถว 31:		แถว 31:

	=== Problem 3: Soldering [Michael Cohen, 2011] ===		=== Problem 3: Soldering [Michael Cohen, 2011] ===
		+
		+	เหล่าวัวกำลังเล่นกับสายไฟ พวกเขาเริ่มรู้จักเทคนิคที่เรียกว่าการบัคกรี (soldering) ซึ่งเป็นการเชื่อมสายสองเส้นเข้าด้วยกัน โดยการนำจุดปลายของสายหนึ่ง เชื่อมเข้ากับบางจุดในสายอีกเส้นหนึ่ง (การบัคกรีจุดปลายสองจุดเชื่อมกันนั้นทำไม่ได้) อาจจะมีการบัคกรีเชื่อมสายหลายสายเข้าที่จุดเดียวกัน
		+
		+	เหล่าวัวมีแผนการที่จะสร้างโครงสร้างมหัศจรรย์ (Amazing Structure) โครงสร้างดังกล่าวมีลักษณะเป็นกราฟที่มี N โหนด (1 <= N <= 50,000) และมีเส้นเชื่อม N-1 เส้นที่แต่ละเส้นมีความยาว 1 หน่วย โดยรับประกันว่าทุก ๆ คู่ของโหนดนั้นจะสามารถเชื่อมถึงกันได้ แต่ละเส้นจะอธิบายโดยใช้คู่ของจำนวนเต็ม A และ B (1 <= A <= N; 1 <= B <= N; A != B)
		+
		+	เหล่าวัวสามารถซื้อสายไฟจากร้านค้า แต่สายไฟยิ่งยาวยิ่งแพง กล่าวคือ วัวสามารถซื้อสายไฟที่ความยาว L โดยจ่ายเงิน L*L หน่วย แต่วัวไม่สามารถตัดหรือเชื่อมสายเข้าด้วยกันได้
		+
		+	ด้วยแผนการดังกล่าว วัวต้องการจะบัคกรีสายเข้าด้วยกัน เพื่อที่จะสร้างโครงสร้างมหัศจรรย์ ช่วยหาวิธีการที่ประหยัดเงินมากที่สุด
		+
		+	ข้อมูลทดสอบ 50% จะมี N <= 2,000
		+
		+	มี partial feedback สำหรับการส่ง 50 ครั้งแรก

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:13, 29 มิถุนายน 2556
แถว 10:		แถว 10:

	=== Problem 2: Odd degrees [Traditional, 2011] ===		=== Problem 2: Odd degrees [Traditional, 2011] ===
		+
		+	เหล่าวัวถูกบุกรุก! อาณาจักรของพวกเขาประกอบไปด้วยเมือง N เมือง (1 <= N <= 50,000) ที่เชื่อมต่อกันด้วยเส้นทาง M เส้น (1 <= M <= 100,000) ที่ไม่มีทิศทาง โดยสำหรับเส้นทางเส้นที่ i จะเชื่อมระหว่างเมือง A_i และ B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i; และไม่มีเส้นทางที่ซ้ำกัน) อย่างไรก็ตามอาณาจักรไม่จำเป็นต้องเชื่อมต่อกันทั้งหมด อาจจะมีเมืองบางกลุ่มที่ไม่สามารถเดินทางไปถึงเมืองอีกบางกลุ่มได้ผ่านทางเส้นทาง
		+
		+	เหล่าวัวทราบว่าผู้บุกรุกต้องการเก็บข้อมูลของเส้นทางทุกเส้นในอาณาจักร พวกวัวจึงต้องการจะปิดเส้นทางบางเส้นเพื่อทำให้ผู้บุกรุกทำงานได้ลำบาก
		+
		+	ช่วยเหล่าวัวหาวิธีในการปิดสับเซตของเส้นทางเพื่อที่จะรับประกันว่าในทุก ๆ เมือง จะมีเส้นทางที่เหลือที่ติดกับเมืองนั้นเป็นจำนวนคี่ หรือรายงานว่าสับเซตดังกล่าวไม่มี
		+
		+
		+	พิจารณาตัวอย่าง
		+
		+	1---2
		+	\ /
		+	3---4
		+
		+	ถ้าเราเก็บเส้นทาง 1-3, 2-3, และ 3-4, และลบเส้นทาง 1-2, เมือง 1, 2, 4 เป็นเป็นจุดปลายของเส้นทางแค่หนึ่งเส้น และเมืองที่ 3 จะมีจุดปลายของถนนสามเส้น ดังรูป
		+
		+	1 2
		+	\ /
		+	3---4

	=== Problem 3: Soldering [Michael Cohen, 2011] ===		=== Problem 3: Soldering [Michael Cohen, 2011] ===

@@ แถว 2: / แถว 2: @@
 === Problem 1: Mowing the Lawn [Neal Wu, 2008] ===
 === Problem 2: Odd degrees [Traditional, 2011] ===
 === Problem 3: Soldering [Michael Cohen, 2011] ===