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

Jittat: /* Problem 3: Cows in a Skyscraper [Mark Gordon, Neal Wu, Fatih Gelgi, 2012] */

2014-06-17T23:30:10Z

Problem 3: Cows in a Skyscraper [Mark Gordon, Neal Wu, Fatih Gelgi, 2012]

Jittat: /* Problem 2: Haybale Restacking [Brian Dean, 2012] */

2014-06-16T15:54:19Z

Problem 2: Haybale Restacking [Brian Dean, 2012]

Jittat: /* Problem 1: Large Banner [Nathan Pinsker, 2010] */

2014-06-16T15:24:34Z

Problem 1: Large Banner [Nathan Pinsker, 2010]

Jittat: /* Problem 1: Large Banner [Nathan Pinsker, 2010] */

2014-06-16T15:17:52Z

Problem 1: Large Banner [Nathan Pinsker, 2010]

Jittat: /* USACO 2012 Mar, Gold */

2014-06-16T15:12:22Z

USACO 2012 Mar, Gold

Jittat: /* USACO 2012 Feb, Gold */

2014-06-16T13:32:32Z

USACO 2012 Feb, Gold

Jittat: /* USACO 2012 Jan, Gold */

2014-06-16T13:30:57Z

USACO 2012 Jan, Gold

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

2014-06-16T13:29:25Z

Jittat: /* USACO Open 2012: Gold */

2014-06-16T13:28:53Z

USACO Open 2012: Gold

Jittat: /* USACO 2011 December, Gold */

2014-06-16T13:27:21Z

USACO 2011 December, Gold

@@ แถว 168: / แถว 168: @@
 === Problem 3: Cows in a Skyscraper [Mark Gordon, Neal Wu, Fatih Gelgi, 2012] ===
 Source: [http://usaco.org/index.php?page=viewproblem2&cpid=129 USACO]
 == USACO Open 2012: Gold ==

@@ แถว 161: / แถว 161: @@
 === Problem 2: Haybale Restacking [Brian Dean, 2012]  ===
 Source: [http://usaco.org/index.php?page=viewproblem2&cpid=128 USACO]
 === Problem 3: Cows in a Skyscraper [Mark Gordon, Neal Wu, Fatih Gelgi, 2012] ===

@@ แถว 157: / แถว 157: @@
 เบซซี่กลับมาจากการท่องเที่ยวอันยาวนานที่ Isle of Guernsey  ชาวนาจอห์นต้องการจะขึ้นป้าย "ยินดีต้อนรับกลับบ้าน" ให้กับเธอ  สนามของชาวนาจอห์นมีขนาดเป็นจำนวนเต็ม M x N (1 <= M, N <= 100,000) และเขาได้ปักเสาไว้ที่ทุก ๆ จุดในสนามที่มีพิกัดเป็นจำนวนเต็ม  (ถ้าเรากำหนดพิกัดให้กับสนามโดยที่มุมล่างขวาคือจุด (0,0) และ มุมบนซ้ายคือจุด (M,N))  จากบรรดาจุด (M+1)*(N+1) จุดเหล่านี้ ชาวนาจอห์นต้องเลือกจุดสองจุดเพื่อให้เป็นจุดปลายของป้ายประกาศ
+เนื่องจากชาวนาจอห์นนั้นเป็นเพอร์เฟ็คชันนิสต์ เขาจึงยืนยันว่าป้ายที่จะขึ้นนั้นจะต้องเป็นเส้นตรงสมบูรณ์  นั่นคือ ระหว่างเสาสองต้นที่เขาเลือก จะต้องไม่มีเสาอีกต้นบนส่วนของเส้นตรงที่เชื่อมระหว่างเสาสองต้นนั้น  นอกจากนี้ ชาวนาจอห์นยังต้องการให้ป้ายนั้นมีความยาวอย่างน้อย L และไม่เกิน H (1 <= L <= H <= 150,000)  ชาวนาจอห์นต้องการให้คุณช่วยว่ามีกี่วิธีที่เขาจะสามารถวางป้ายได้  ป้ายนี้กลับด้านได้ ดังนั้นการสลับจุดปลายนั้นจะนับว่าเป็นวิธีการวางเพียงวิธีเดียว  เนื่องจากคำตอบอาจจะมีค่ามาก ชาวนาจอห์นต้องการคำตอบ modulo B (1 <= B <= 1,000,000,000)
 === Problem 2: Haybale Restacking [Brian Dean, 2012]  ===

@@ แถว 154: / แถว 154: @@
 === Problem 1: Large Banner [Nathan Pinsker, 2010] ===
 Source: [http://usaco.org/index.php?page=viewproblem2&cpid=127 USACO]
 === Problem 2: Haybale Restacking [Brian Dean, 2012]  ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 15:12, 16 มิถุนายน 2557
แถว 152:		แถว 152:

	== USACO 2012 Mar, Gold ==		== USACO 2012 Mar, Gold ==
		+	=== Problem 1: Large Banner [Nathan Pinsker, 2010] ===
		+	Source: [http://usaco.org/index.php?page=viewproblem2&cpid=127 USACO]
		+
		+	=== Problem 2: Haybale Restacking [Brian Dean, 2012] ===
		+	Source: [http://usaco.org/index.php?page=viewproblem2&cpid=128 USACO]
		+
		+	=== Problem 3: Cows in a Skyscraper [Mark Gordon, Neal Wu, Fatih Gelgi, 2012] ===
		+	Source: [http://usaco.org/index.php?page=viewproblem2&cpid=129 USACO]
		+
	== USACO Open 2012: Gold ==		== USACO Open 2012: Gold ==

@@ แถว 128: / แถว 128: @@
 == USACO 2012 Feb, Gold ==
 == USACO 2012 Mar, Gold ==
 == USACO Open 2012: Gold ==

@@ แถว 99: / แถว 99: @@
 ชาวนาจอห์นความจำไม่ค่อยจะดี — ช่วยเขาตอบคำถามของเบซซี่ด้วย!
-== USACO 2012 Jan ==
+== USACO 2012 Jan, Gold ==
-== USACO 2012 Feb ==
+== USACO 2012 Feb, Gold ==
-== USACO 2012 Mar ==
+== USACO 2012 Mar, Gold ==
 == USACO Open 2012: Gold ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:28, 16 มิถุนายน 2557
แถว 99:		แถว 99:
	ชาวนาจอห์นความจำไม่ค่อยจะดี — ช่วยเขาตอบคำถามของเบซซี่ด้วย!		ชาวนาจอห์นความจำไม่ค่อยจะดี — ช่วยเขาตอบคำถามของเบซซี่ด้วย!

		+	== USACO 2012 Jan ==
		+	== USACO 2012 Feb ==
		+	== USACO 2012 Mar ==
	== USACO Open 2012: Gold ==		== USACO Open 2012: Gold ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:27, 16 มิถุนายน 2557
แถว 68:		แถว 68:

	== USACO 2011 December, Gold ==		== USACO 2011 December, Gold ==
		+	=== Problem 1: Cow Photography [Brian Dean, 2011] ===
		+	Source: [http://usaco.org/index.php?page=viewproblem2&cpid=100 usaco]
		+
		+	วันนี้เหล่าวัวอยู่ในอารมณ์ซุกซน! ชาวนาจอห์นเพียงแค่ต้องการจะถ่ายรูปเหล่าวัวที่ยืนเป็นแถว แต่พวกวัวก็จะขยับก่อนที่เขาจะได้มีโอกาสกดถ่ายรูป
		+
		+	กล่าวคือ ชจ. มีวัวทั้งสิ้น N ตัว (1 <= N <= 20,000) วัวแต่ละตัวของ ชจ. จะมีหมายเลขประจำตัวเป็นจำนวนเต็มที่ไม่ซ้ำกัน ชจ. ต้องการจะถ่ายรูปวัวยืนเป็นแถวในลำดับที่ต้องการ ซึ่งลำดับนี้จะระบุด้วยข้อมูลที่อยู่ในอาร์เรย์ A[1...N] โดยที่ A[j] ระบุหมายเลขประจำตัวของวัวลำดับที่ j ในแถว ชจ.ได้จัดแถววัวตามลำดับนี้ แต่ก่อนที่เขาจะมีโอกาสได้กดถ่ายรูป กลุ่มของวัว (0 ตัวหรือมากว่านั้น, ไม่จำเป็นต้องยืนติดกัน) ก็จะย้ายตำแหน่งไปยังตำแหน่งใหม่ในแถว กล่าวโดยละเอียดก็คือ กลุ่มของวัวกลุ่มหนึ่งจะเดินออกมาจากแถว วัวที่เหลือในแถวจะขยับไปติดกัน จากนั้นวัวที่ยืนออกมาจากแถวจะเดินเข้าไปแทรกในตำแหน่งต่าง ๆ ในแถว (ไม่จำเป็นต้องเป็นตำแหน่งเดิม) ถึงแม้จะสับสน แต่ ชจ. ก็ไม่ย่อท้อ เขาจัดแถววัวใหม่ตามลำดับ A แต่ก็เช่นเคย ก่อนที่เขาจะได้ถ่ายรูป กลุ่มของวัวกลุ่มใหม่ก็จะย้ายตำแหน่งในแถวอีก
		+
		+	กระบวนการดังกล่าวเกิดขึ้นทั้งสิ้น 5 รอบ (และ ชจ. พลาดกดถ่ายรูปไปทุกครั้ง) ก่อนที่ ชจ. จะถอดใจ ให้ข้อมูลของแต่ละรูปภาพ ให้คุณหาว่าคุณจะสามารถสร้างลำดับ A ที่ชจ.ต้องการได้หรือไม่ รูปภาพแต่ละรูปแสดงลำดับของวัวที่แตกต่างจาก A เนื่องจากกลุ่มของวัว (0 ตัวหรือมากกว่านั้น) ได้ย้ายที่ อย่างไรก็ตาม วัวหนึ่งตัวจะสามารถย้ายที่ได้แค่ในรูปเพียงรูปเดียวเท่านั้น: ถ้าวัวตัวใดอยู่ในกลุ่มที่มีการย้ายที่ในรูปภาพรูปหนึ่งแล้ว เธอจะไม่ย้ายที่อีกในรูปอื่น ๆ (แต่เธออาจจะอยู่ตำแหน่งที่ไม่ตรงกับตำแหน่งใน A ได้ ซึ่งเป็นผลจากที่วัวตัวอื่น ๆ ขยับ)
		+
		+	=== Problem 2: Simplifying the Farm [Nathan Pinsker, 2011] ===
		+	Source: [http://usaco.org/index.php?page=viewproblem2&cpid=101 usaco]
		+
		+	ชาวนาจอห์นได้ไปเรียนวิชาอัลกอริทึมภาคค่ำที่มหาวิทยาลัยแถวฟาร์มของเขา เขาเพิ่งได้เรียนเกี่ยวกับ minimum spanning tree ซึ่งทำให้เขาได้ตระหนักว่า การออกแบบฟาร์มของเขานั้นมันไม่มีประสิทธิภาพอย่างที่ควรจะเป็น เขาต้องการจะทำให้แผนผัง (layout) ของฟาร์มง่ายขึ้น
		+
		+	ฟาร์มปัจจุบันนั้นมีลักษณะเป็นกราฟ ที่มีจุดยอดแทนสนาม และเส้นเชื่อม แทนทางเดินระหว่างสนามเหล่านี้ ทางเดินทุกเส้นมีความยาวระบุอยู่ ชาวนาจอห์นสังเกตว่าสำหรับความยาวค่าใด ๆ จะมีทางเดินไม่เกินสามทางที่มีค่าความยาวนี้ ชจ.ต้องการลบทางเดินในฟาร์มทิ้งเพื่อให้แผนผังกลายเป็นต้นไม้ (tree) นั่นคือ สำหรับสนามคู่ใด ๆ จะมีเส้นทางเดินเพียงเส้นทางเดียวเท่านั้น กล่าวคือ ชาวนาจอห์นต้องการให้ฟาร์มของเขาเป็น minimum spanning tree (ต้นไม้ที่มีผลรวมของความยาวเส้นเชื่อมน้อยที่สุด)
		+
		+	ช่วยชาวนาจอห์นหาความยาวของ minimum spanning tree พร้อมกับคำนวณว่าจำนวนของ minimum spanning tree ที่เป็นไปได้ทั้งหมด มีกี่แบบ
		+
		+	=== Problem 3: Grass Planting [Travis Hance, 2011] ===
		+	Source: [http://usaco.org/index.php?page=viewproblem2&cpid=102 usaco]
		+
		+	ชาวนาจอห์นมีทุ่งหญ้าเลี้ยงสัตว์ที่แห้งแร้งอยู่ N ทุ่ง (2 <= N <= 100,000) เชื่อมต่อกันด้วยถนนสองทางจำนวน N-1 เส้น ในรูปแบบที่ทำให้มีเส้นทางเชื่อมระหว่างทุ่งหญ้าสองทุ่งใดๆ หนึ่งทาง เบซซี่เป็นวัวที่ชอบกินหญ้ามาก ๆ มักจะชอบบ่นว่าไม่มีหญ้าให้กินบนเส้นทางเชื่อมระหว่างทุ่งหญ้าเลย ชาวนาจอห์นรักเบซซี่มาก และวันนี้ล่ะ จะเป็นวันที่เขาจะเริ่มปลูกหญ้าบนถนน เขาจะดำเนินการดังกล่าวเป็นขั้น ๆ จำนวน M ขั้น (1 <= M <= 100,000)
		+
		+	แต่ละขั้น มีเหตุการณ์เกิดขึ้นได้สองแบบ:
		+
		+	* ชจ. จะเลือกทุ่งหญ้าสองแห่ง จากนั้นจะปลูกหญ้าหนึ่งผืนในถนนทุก ๆ เส้นระหว่างทุ่งหญ้าทั้งสองนั้น
		+
		+	* เบซซีจะเลือกถนนมาหนึ่งเส้น และถาม ชจ. ว่ามีหญ้ากี่ผืนในถนนเส้นนั้น
		+
		+	ชาวนาจอห์นความจำไม่ค่อยจะดี — ช่วยเขาตอบคำถามของเบซซี่ด้วย!

	== USACO Open 2012: Gold ==		== USACO Open 2012: Gold ==