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

Jittat: /* Problem F – Fair coin toss */

2013-06-02T05:22:16Z

Problem F – Fair coin toss

Jittat เมื่อ 05:12, 2 มิถุนายน 2556

2013-06-02T05:12:26Z

Jittat: /* Problem H – Harvesting potatoes */

2013-06-02T04:59:44Z

Problem H – Harvesting potatoes

Jittat เมื่อ 04:39, 2 มิถุนายน 2556

2013-06-02T04:39:58Z

Jittat: /* Problem G – Gems in the maze */

2013-06-02T04:32:58Z

Problem G – Gems in the maze

Jittat เมื่อ 04:30, 2 มิถุนายน 2556

2013-06-02T04:30:26Z

Jittat: /* Problem G – Gems in the maze */

2013-06-02T04:29:55Z

Problem G – Gems in the maze

Jittat เมื่อ 04:25, 2 มิถุนายน 2556

2013-06-02T04:25:17Z

Jittat เมื่อ 04:25, 2 มิถุนายน 2556

2013-06-02T04:25:09Z

Jittat เมื่อ 04:11, 2 มิถุนายน 2556

2013-06-02T04:11:33Z

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:22, 2 มิถุนายน 2556
แถว 36:		แถว 36:
	: หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]		: หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]

		+	Lolek and Bolek กำลังฝึกหัดที่จะเป็นนักมายากล ในชั่วโมงที่ผ่านมา พวกเขามัวแต่เถียงกันว่าใครจะออกไปเอาขยะไปทิ้ง ทางออกของปัญหานี้ก็คือการโยนเหรียญที่เที่ยงตรง แต่แน่นอนว่าเราไม่ควรจะเชื่อนักมายากลเวลาที่ต้องโยนเหรียญใช่มั้ย?
		+
		+	หลังจากที่ค้นดูในกระเป๋า พวกเขาพบเหรียญ n เหรียญ ทุก ๆ เหรียญมีหน้าหนึ่งเขียนว่า 1 อีกหน้าเขียนว่า 0 สำหรับเหรียญที่ i พวกเขาทราบความน่าจะเป็น p<sub>i</sub> ที่เหรียญจะแสดงด้าน 1 เมื่อโยน
		+
		+	แน่นอนว่าการมีเหรียญอย่างเดียวไม่ช่วยให้แก้ปัญหาได้ พวกเขายังต้องหาวิธีการที่เที่ยงตรงในการตัดสินปัญหา Lolek ได้แนะนำดังนี้ ให้เอาเหรียญทุกเหรียญที่มีมาโยนแล้วให้ xor ผลลัพธ์เข้าด้วยกัน กล่าวคือ พวกเขาจะพิจารณาเฉพาะ parity ของ 1 ในผลลัพธ์เท่านั้น ถ้ามีจำนวน 1 เป็นเลขคู่จะเป็นตาของ Bolek ที่จะไปทิ้งขยะ ถ้าไม่ใช่ ก็จะเป็นตาของ Lolek
		+
		+	และพวกเขาก็มาทะเลาะกันอีกรอบ ว่าวิธีนี้มันเที่ยงตรงอย่างไร
		+
		+	=== โจทย์ ===
		+
		+	เซตของเหรียบจะเรียกว่าเที่ยงตรง ถ้าวิธีการของ Lolek นั้นเที่ยงตรง นั้นคือ ความน่าจะเป็นที่ Bolek จะต้องออกไปทิ้งขยะมีค่าเท่ากับ 50% พอดี
		+
		+	คุณจะได้รับข้อมูลของเหรียญที่ Lolek และ Bolek มี
		+
		+	* สำหรับปัญหาง่าย F1, ให้คุณหาว่าเหรียญเหล่านี้มีสับเซตที่เที่ยงตรงหรือไม่
		+	* สำหรับปัญหายาก F2, ให้หาว่ามีสับเซตกี่สับเซตที่เที่ยงตรง

	== Problem G – Gems in the maze ==		== Problem G – Gems in the maze ==

@@ แถว 28: / แถว 28: @@
 * จำนวนเต็มบวก n ที่น้อบที่สุดที่ทำให้ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 มีค่ามากที่สุด (เมื่อเครื่องหมาย ⋅ แทนการต่อกันของลำดับ)
 * ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 สำหรับค่า n นั้น
 == Problem G – Gems in the maze ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:59, 2 มิถุนายน 2556
แถว 46:		แถว 46:

	: หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]		: หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]
		+
		+	มีไร่ที่แบ่งเป็นตารางจัสตุรัส r × c ช่อง
		+
		+	มีมันขึ้นอยู่ในทุกช่องของไร่นี้ คุณมีเครื่องเก็บมันและคุณต้องการเก็บมันทั้งหมด เครื่องเก็บมันเป็นรถขนาดใหญ่ที่ติดเครื่องตักและอุปกรณ์ที่จำเป็นในการขุดมันออกมาจากดิน คนขับมีปุ่มกดที่ใช้เปิดหรือปิดที่ขุดดินนี้
		+
		+	เครื่องเก็บมันทำงานเป็นรอบ แต่ละรอบจะเดินทางในแถวเดียวหรือคอลัมน์เดียว โดยเริ่มจากขอบด้านหนึ่งและขับตรงไปจนทะลุขอบอีกด้านหนึ่ง ความจุของเครื่องเก็บมันนั้นมีจำกัด ในแต่ละรอบจะสามารถเก็บมันได้ไม่เกิน d ช่อง ซึ่งจะเป็นมันจากช่องใดก็ได้ที่คุณขับรถผ่าน ในข้อนี้เป้าหมายคือการออกแบบวิธีการเก็บมันที่ทำให้มีรอบการเก็บน้อยที่สุด
		+
		+	ในทางปฏิบัตินอกจากรอบของการเก็บมันแล้ว ยังมีปัจจัยอีกอย่างหนึ่ง กล่าวคือ คนขับรถเก็บมันนั้นไม่ถนัดที่จะดำเนินการตามขั้นตอนที่ยาก การเก็บมันในช่วงที่ต่อเนื่องกันนั้นง่ายกว่าการเก็บโดยการเปิดที่ขุดแล้วก็ปิดและเปิดที่ขุดใหม่ไปมาในตำแหน่งที่ถูกต้อง '''ความยาก'''ของการเก็บแต่ละรอบจะมีค่าเท่ากับสองเท่าของจำนวนช่องที่ติดกันที่ต้องเก็บเกี่ยวในรอบนั้น (หมายเหตุ คนขับรถจะต้องเก็บเกี่ยวในแต่ละช่องแค่ครั้งเดียวเท่านั้น และไม่อนุญาตให้เปิดที่ขุดไว้ตลอดเวลา หรือเปิดไว้ในช่องที่เก็บเกี่ยวไปแล้วเนื่องจากจะเป็นการทำลายดินในช่องนั้น)
		+
		+	ความยากของแผนการเก็บจะเท่ากับความยากของรอบที่มีค่าความยากมากที่สุด (นั้นคือค่ามากที่สุดของค่าความยากของแต่ละรอบ)
		+
		+	=== โจทย์ ===
		+	คุณจะได้รับขนาด r และ c และความจุ d สำหรับข้อมูลชุดทดสอบง่าย H1 เป้าหมายคือการสร้างแผนการเก็บเกี่ยวที่มีจำนวนรอบน้อยที่สุด สำหรับชุดข้อมูลทดสอบยาก H2 งานของคุณคือหาแผนการเก็บเกี่ยวที่ใช้จำนวนรอบน้อยที่สุดและมีค่าความยากน้อยที่สุดเท่าที่จะทำได้

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:39, 2 มิถุนายน 2556
แถว 40:		แถว 40:

	Scrooge ต้องการทราบจำนวนอัญมนีที่มากที่สุดที่เขาเอาออกมาจากถ้ำมหาสมบัติได้		Scrooge ต้องการทราบจำนวนอัญมนีที่มากที่สุดที่เขาเอาออกมาจากถ้ำมหาสมบัติได้
		+
		+	== Problem H – Harvesting potatoes ==
		+
		+	: ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/h.html]
		+
		+	: หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]

@@ แถว 35: / แถว 35: @@
 : หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]
-Scrooge McDuck มีแผนที่จะเพิ่มความมั่งคั่งให้กับตนเอง  เขาค้นพบถ้ำมหาสมบัติที่ประกอบด้วยห้องในนั้น n ห้อง  ห้องมีหมายเลข 0 ถึง n-1 แต่ละห้องมีอัญมนีหนึ่งชิ้น  ห้องเชื่อมต่อกันด้วยทางเดิดที่เดินได้ทางเดียว แต่ละห้องจะมีทางเดินออกจากห้องสองทาง  ทางหนึ่งพาไปยังห้องหมายเลข (a ⋅ v<sup>2</sup> + b ⋅ v + c) mod n สำหรับห้องหมายเลข v และอีกทางจะพาคุณออกไปนอกถ้ำมหาสมบัตินี้
+Scrooge McDuck มีแผนที่จะเพิ่มความมั่งคั่งให้กับตนเอง  เขาค้นพบถ้ำมหาสมบัติที่ประกอบด้วยห้องในนั้น n ห้อง  ห้องมีหมายเลข 0 ถึง n-1 แต่ละห้องมีอัญมนีหนึ่งชิ้น  ห้องเชื่อมต่อกันด้วยทางเดิดที่เดินได้ทางเดียว แต่ละห้องจะมีทางเดินออกจากห้องสองทาง  ทางหนึ่งพาไปยังห้องหมายเลข (a ⋅ v<sup>2</sup> + b ⋅ v + c) mod n สำหรับห้องหมายเลข v (ค่าของ a,b, และ c จะระบุในข้อมูลป้อนเข้า) และอีกทางจะพาคุณออกไปนอกถ้ำมหาสมบัตินี้
 คุณสามารถเริ่มในถ้ำที่ตำแหน่งใดก็ได้ จากนั้นจะสามารถเดินไปมาตามทางเดินเพื่อเก็บอัญมนี แต่เมื่อคุณออกจากถ้ำแล้ว คุณจะไปทำให้ถ้ำระเบิดและทุกอย่างที่คุณยังไม่ได้เก็บไปก็จะหายไปหมด
 Scrooge ต้องการทราบจำนวนอัญมนีที่มากที่สุดที่เขาเอาออกมาจากถ้ำมหาสมบัติได้

@@ แถว 3: / แถว 3: @@
 == Problem E – Evil matching ==
-ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/e.html]
+: ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/e.html]
-หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]
+: หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]
 ให้ลำดับของจำนวนเต็มบวก T = t<sub>1</sub>,t<sub>2</sub>,…,t<sub>n</sub> (text) และ P = p<sub>1</sub>,p<sub>2</sub>,…,p<sub>m</sub> (pattern).  นิยามคลาสสิกของการจับคู่ก็คือ เราจะบอกว่า P นั้น match กับ T ที่ตำแหน่ง k ถ้า p<sub>1</sub> = t<sub>k</sub>, p<sub>2</sub> = t<sub>k+1</sub>, …, และ p<sub>m</sub> = t<sub>k+m−1</sub>.  เราสามารถหาตำแหน่งที่ P match กับ T ได้ โดยอาจจะใช้อัลกอริทึมเช่น Knuth-Morris-Pratt algorithm.
@@ แถว 31: / แถว 31: @@
 == Problem G – Gems in the maze ==
-ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/g.html]
+: ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/g.html]
 Scrooge McDuck มีแผนที่จะเพิ่มความมั่งคั่งให้กับตนเอง  เขาค้นพบถ้ำมหาสมบัติที่ประกอบด้วยห้องในนั้น n ห้อง  ห้องมีหมายเลข 0 ถึง n-1 แต่ละห้องมีอัญมนีหนึ่งชิ้น  ห้องเชื่อมต่อกันด้วยทางเดิดที่เดินได้ทางเดียว แต่ละห้องจะมีทางเดินออกจากห้องสองทาง  ทางหนึ่งพาไปยังห้องหมายเลข (a ⋅ v<sup>2</sup> + b ⋅ v + c) mod n สำหรับห้องหมายเลข v และอีกทางจะพาคุณออกไปนอกถ้ำมหาสมบัตินี้

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

	== Problem G – Gems in the maze ==		== Problem G – Gems in the maze ==
		+
		+	ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/g.html]
		+
		+	Scrooge McDuck มีแผนที่จะเพิ่มความมั่งคั่งให้กับตนเอง เขาค้นพบถ้ำมหาสมบัติที่ประกอบด้วยห้องในนั้น n ห้อง ห้องมีหมายเลข 0 ถึง n-1 แต่ละห้องมีอัญมนีหนึ่งชิ้น ห้องเชื่อมต่อกันด้วยทางเดิดที่เดินได้ทางเดียว แต่ละห้องจะมีทางเดินออกจากห้องสองทาง ทางหนึ่งพาไปยังห้องหมายเลข (a ⋅ v<sup>2</sup> + b ⋅ v + c) mod n สำหรับห้องหมายเลข v และอีกทางจะพาคุณออกไปนอกถ้ำมหาสมบัตินี้
		+
		+	คุณสามารถเริ่มในถ้ำที่ตำแหน่งใดก็ได้ จากนั้นจะสามารถเดินไปมาตามทางเดินเพื่อเก็บอัญมนี แต่เมื่อคุณออกจากถ้ำแล้ว คุณจะไปทำให้ถ้ำระเบิดและทุกอย่างที่คุณยังไม่ได้เก็บไปก็จะหายไปหมด
		+
		+	Scrooge ต้องการทราบจำนวนอัญมนีที่มากที่สุดที่เขาเอาออกมาจากถ้ำมหาสมบัติได้

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:25, 2 มิถุนายน 2556
แถว 4:		แถว 4:

	ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/e.html]		ต้นฉบับและข้อมูลนำเข้า: [http://ipsc.ksp.sk/contests/ipsc2012/real/problems/e.html]
		+
	หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]		หน้ารวมโจทย์ทั้งหมด: [http://ipsc.ksp.sk/archive]

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

	นั่นคือ เราสามารถที่จะรวมข้อมูลใน text เป็นกลุ่ม ๆ เข้าด้วยกันก่อนที่จะไปจับคู่กับ pattern ยกตัวอย่างเช่น ถ้าเรามี T = 1,2,1,1,3,2 และ P = 3,2, เราจะมีสอง evil-matches: อันแรกที่ตำแหน่ง k = 1 (with a1 = 3,a2 = 5), อันที่สองที่ k = 5 (with a1 = 6,a2 = 7).		นั่นคือ เราสามารถที่จะรวมข้อมูลใน text เป็นกลุ่ม ๆ เข้าด้วยกันก่อนที่จะไปจับคู่กับ pattern ยกตัวอย่างเช่น ถ้าเรามี T = 1,2,1,1,3,2 และ P = 3,2, เราจะมีสอง evil-matches: อันแรกที่ตำแหน่ง k = 1 (with a1 = 3,a2 = 5), อันที่สองที่ k = 5 (with a1 = 6,a2 = 7).
		+
		+	ค่า '''evil compatibility''' ของ text T กับ pattern P คือจำนวนของตำแหน่ง k ที่แตกต่างกันที่ P evil-match กัย T ที่ตำแหน่ง k
		+
		+	=== โจทย์ ===
		+
		+	ให้ text T และ pattern สองลำดับ P1, P2 คำนวณ
		+
		+	* ค่า evil compatibility ของ T กับ P1
		+	* ค่า evil compatibility ของ T กับ P2
		+	* จำนวนเต็มบวก n ที่น้อบที่สุดที่ทำให้ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 มีค่ามากที่สุด (เมื่อเครื่องหมาย ⋅ แทนการต่อกันของลำดับ)
		+	* ค่า evil compatibility ของ T กับ P1 ⋅ n ⋅ P2 สำหรับค่า n นั้น