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

Jittat: /* Warehouse Store */

2013-05-14T09:27:11Z

Warehouse Store

Jittat: /* Prefixuffix */

2013-05-14T09:09:35Z

Prefixuffix

Jittat: /* Prefixuffix */

2013-05-14T09:07:16Z

Prefixuffix

Jittat: /* Warehouse Store */

2013-05-14T09:07:00Z

Warehouse Store

Jittat: /* Warehouse Store */

2013-05-14T09:06:48Z

Warehouse Store

Jittat: /* Minimalist Security */

2013-05-14T09:02:17Z

Minimalist Security

Jittat: /* Minimalist Security */

2013-05-14T08:53:06Z

Minimalist Security

Jittat เมื่อ 08:48, 14 พฤษภาคม 2556

2013-05-14T08:48:23Z

Jittat: /* Leveling Ground (Stage III day 1) */

2013-05-13T12:22:37Z

Leveling Ground (Stage III day 1)

Jittat: /* Leveling Ground (Stage III day 1) */

2013-05-13T12:22:12Z

Leveling Ground (Stage III day 1)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:27, 14 พฤษภาคม 2556
แถว 49:		แถว 49:

	source: [http://main.edu.pl/en/archive/oi/19/hur]		source: [http://main.edu.pl/en/archive/oi/19/hur]
		+
		+	Byteasar มีโกดังสำหรับขายส่งสินค้าก่อสร้าง ฤดูกาลนี้ของขายดีที่สุด (ที่คิดเป็นรายได้ส่วนใหญ่ของร้าน) คือพื้นลามิเนต แต่โชคไม่ดีเสียเลย ที่ลูกค้ามักสั่งซื้อสินค้าที่ทางร้านไม่สามารถจัดส่งหรือขายให้ได้ ทั้งนี้เนื่องจากไม้ในโกดังมีไม่พอ เพื่อป้องกันการสูญเสียลูกค้า Byteasar ได้ตัดสินใจว่าจะลดจำนวนเหตุการณ์น่าผิดหวังดังกล่าว
		+
		+	เพื่อเป้าหมายนี้ เขาจึงได้เตรียมเขียนแผนการทำงานสำหรับอีก '''n''' วันถัดไป
		+
		+	เขาได้วิเคราะห์สัญญาที่ทำกับผู้ผลิตพื้น และคำนวณลำดับ '''a1''', '''a2''',..., '''an''' โดยที่จำนวน '''ai''' จะระบุว่ามีแท่งไม้จำนวน '''ai''' แท่งส่งถึงโรงงานในเช้าของวันที่ '''i'''
		+
		+	Byteasar ยังได้ทำรายการใบสั่งซื้อจากลูกค้า จากข้อมูลเหล่านั้น เขาสามารถระบุลำดับ '''b1,b2,...,bn''' โดยที่จำนวน '''bi''' ระบุว่า ตอนเที่ยงของวันที่ '''i''' ลูกค้าจะซื้อแท่งไม้จำนวน '''bi''' แท่ง ถ้า Byteasar ตกลงว่าจะขายของให้กับลูกค้าในวันนั้น เขาจะต้องส่งมอบแท่งไม้ตามจำนวนนั้นให้กับลูกค้า ถ้ามีแท่งไม้ในโกดังไม่พอเมื่อมีการสั่งซื้อ Byteasar จะต้องปฏิเสธการซื้อนั้นไป แต่ถ้ามีแท่งไม้พอ Byteasar จะสามารถเลือกที่จะขายแท่งไม้ให้ หรือจะปฏิเสธก็ได้
		+
		+	อาศัยข้อมูลเหล่านี้ Byteasar ต้องการทราบว่าการสั่งซื้อใดที่เขาควรจะขายให้ เพื่อทำให้จำนวนครั้งที่เขาตอบปฏิเสธ (ไม่ว่าจะเป็นเพราะเขาเลือกปฏิเสธหรือเพราะว่าของไม่พอจริง ๆ) นั้นมีค่าน้อยที่สุด เราสมมติว่าในวันแรกตอนเช้าก่อนเริ่ม โกดังนั้นว่างเปล่า

	== Prefixuffix ==		== Prefixuffix ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:09, 14 พฤษภาคม 2556
แถว 55:		แถว 55:

	ในข้อนี้เราพิจารณาสตริงที่ประกอบไปด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น เราจะเรียกส่วนเริ่มต้นของสตริงว่า prefix ในขณะที่จะเรียกส่วนท้ายของสตริงว่า suffix นอกจากนี้ สตริงว่าง จะถูกนับว่าเป็นทั้ง prefix และ suffix ของสตริงใด ๆ สตริงสองสตริงจะเรียกว่า'''เหมือนกันเชิงวงรอบ''' (cyclically equivalent) ถ้าสตริงหนึ่งสามารถสร้างได้จากอีกสตริงหนึ่ง โดยการย้าย suffix ของสตริงนั้นไปไว้ตอนหน้าของสตริงดังกล่าว ยกตัวอย่างเช่น สตริง ''ababba'' และ ''abbaab'' นั่นเหมือนกันเชิงวงรอบ ในขณะที่ ''ababba'' กับ ''ababab'' นั้นไม่ใช่ นอกจากนี้ ทุก ๆ สตริงยังเหมือนกันเชิงวงรอบกับตัวเอง		ในข้อนี้เราพิจารณาสตริงที่ประกอบไปด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น เราจะเรียกส่วนเริ่มต้นของสตริงว่า prefix ในขณะที่จะเรียกส่วนท้ายของสตริงว่า suffix นอกจากนี้ สตริงว่าง จะถูกนับว่าเป็นทั้ง prefix และ suffix ของสตริงใด ๆ สตริงสองสตริงจะเรียกว่า'''เหมือนกันเชิงวงรอบ''' (cyclically equivalent) ถ้าสตริงหนึ่งสามารถสร้างได้จากอีกสตริงหนึ่ง โดยการย้าย suffix ของสตริงนั้นไปไว้ตอนหน้าของสตริงดังกล่าว ยกตัวอย่างเช่น สตริง ''ababba'' และ ''abbaab'' นั่นเหมือนกันเชิงวงรอบ ในขณะที่ ''ababba'' กับ ''ababab'' นั้นไม่ใช่ นอกจากนี้ ทุก ๆ สตริงยังเหมือนกันเชิงวงรอบกับตัวเอง
		+
		+	คุณได้รับสตริง '''t''' ที่ประกอบด้วยตัวอักษร '''n''' ตัว เราต้องการหา prefix '''p''' และ suffix '''s''' ที่มีความยาวเท่ากันที่:
		+
		+	* '''p''' และ '''s''' นั้นเหมือนกันเชิงวงรอบ (cyclically equivalent)
		+	* ความยาวของทั้ง '''p''' และ '''s''' จะต้องไม่มากกว่า '''n/2''' (นั่นคือ '''p''' และ '''s''' จะต้องไม่ทับกันใน '''t''')
		+	* ความยาวของทั้ง '''p''' และ '''s''' จะต้องมีค่ามากที่สุด

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:07, 14 พฤษภาคม 2556
แถว 53:		แถว 53:

	source: [http://main.edu.pl/en/archive/oi/19/pre]		source: [http://main.edu.pl/en/archive/oi/19/pre]
		+
		+	ในข้อนี้เราพิจารณาสตริงที่ประกอบไปด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น เราจะเรียกส่วนเริ่มต้นของสตริงว่า prefix ในขณะที่จะเรียกส่วนท้ายของสตริงว่า suffix นอกจากนี้ สตริงว่าง จะถูกนับว่าเป็นทั้ง prefix และ suffix ของสตริงใด ๆ สตริงสองสตริงจะเรียกว่า'''เหมือนกันเชิงวงรอบ''' (cyclically equivalent) ถ้าสตริงหนึ่งสามารถสร้างได้จากอีกสตริงหนึ่ง โดยการย้าย suffix ของสตริงนั้นไปไว้ตอนหน้าของสตริงดังกล่าว ยกตัวอย่างเช่น สตริง ''ababba'' และ ''abbaab'' นั่นเหมือนกันเชิงวงรอบ ในขณะที่ ''ababba'' กับ ''ababab'' นั้นไม่ใช่ นอกจากนี้ ทุก ๆ สตริงยังเหมือนกันเชิงวงรอบกับตัวเอง

@@ แถว 49: / แถว 49: @@
 source: [http://main.edu.pl/en/archive/oi/19/hur]
 == Prefixuffix ==
 source: [http://main.edu.pl/en/archive/oi/19/pre]

@@ แถว 49: / แถว 49: @@
 source: [http://main.edu.pl/en/archive/oi/19/hur]
 == Prefixuffix ==
 source: [http://main.edu.pl/en/archive/oi/19/pre]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:02, 14 พฤษภาคม 2556
แถว 37:		แถว 37:

	คุณได้รับแผนที่ของระบบเครือข่ายถนนของเมือง Mafiatown เครือข่ายประกอบด้วยแยกและถนนสองทิศทางที่เชื่อมระหว่างแยกต่าง ๆ ถนนจะตัดกันเฉพาะที่แยกเท่านั้น แต่ถนนสามารถข้ามกันหรือลอดกันได้ แต่ละคู่ของแยกจะเชื่อมกันด้วยถนนอย่างมากหนึ่งเส้น ที่ทุก ๆ แยก '''v''' จะมีสถานีตำรวจที่มีตำรวจดูแล '''p(v)''' คน ถนนเชื่อมระหว่างแยก '''u''' และ '''v''' จะปลอดภัยถ้ามีตำรวจรวมอย่างน้อย '''b(u,v)''' คนจากสองสถานีที่เป็นแยกปลายถนนดังกล่าว เมื่อเริ่มต้น '''p(u)+p(v) >= b(u,v)''' สำหรับทุก ๆ ถนน		คุณได้รับแผนที่ของระบบเครือข่ายถนนของเมือง Mafiatown เครือข่ายประกอบด้วยแยกและถนนสองทิศทางที่เชื่อมระหว่างแยกต่าง ๆ ถนนจะตัดกันเฉพาะที่แยกเท่านั้น แต่ถนนสามารถข้ามกันหรือลอดกันได้ แต่ละคู่ของแยกจะเชื่อมกันด้วยถนนอย่างมากหนึ่งเส้น ที่ทุก ๆ แยก '''v''' จะมีสถานีตำรวจที่มีตำรวจดูแล '''p(v)''' คน ถนนเชื่อมระหว่างแยก '''u''' และ '''v''' จะปลอดภัยถ้ามีตำรวจรวมอย่างน้อย '''b(u,v)''' คนจากสองสถานีที่เป็นแยกปลายถนนดังกล่าว เมื่อเริ่มต้น '''p(u)+p(v) >= b(u,v)''' สำหรับทุก ๆ ถนน
		+
		+	อย่างไรก็ตาม เนื่องจากวิกฤตการณ์ Byteasar ผู้ว่าของเมืองจึงได้สั่งกฎ Minimalist Security Act (MSA) ที่ระบุว่า
		+
		+	* ตำรวจจำนวนหนึ่ง (ซึ่งอาจจะเป็น 0) จะถูกปลดประจำการจากแต่ละสถานีประจำแยก เราจะให้ '''z(v)''' แทนจำนวนดังกล่าวสำหรับแยก '''v'''
		+
		+	* หลังจากการปลดประจำการ จำนวนตำรวจรวมของแต่ละแยกที่เป็นจุดปลายของถนนเส้นใด (สมมติว่าเป็นแยก '''u''' และ '''v''') จะต้องมีจำนวนเท่ากับ '''b(u,v)''' พอดี นั่นคือ '''p(u)-z(u) + p(v)-z(v)=b(u,v)'''
		+
		+	กฎนี้ไม่จำเป็นต้องระบุรูปแบบการปลดประจำการที่ได้ผลรวมของจำนวนตำรวจที่ปลดประจำการได้แบบเดียว ดังนั้น Byteasar สงสัยว่าจำนวนตำรวจที่จะปลดประจำการที่น้อยที่สุด และจำนวนที่มากที่สุดที่เป็นไปได้ ที่ยังสอดคล้องกับเงื่อนไขดังกล่าวด้านบน จะเป็นเท่าใด

	== Warehouse Store ==		== Warehouse Store ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:53, 14 พฤษภาคม 2556
แถว 35:		แถว 35:

	source: [http://main.edu.pl/en/archive/oi/19/bez]		source: [http://main.edu.pl/en/archive/oi/19/bez]
		+
		+	คุณได้รับแผนที่ของระบบเครือข่ายถนนของเมือง Mafiatown เครือข่ายประกอบด้วยแยกและถนนสองทิศทางที่เชื่อมระหว่างแยกต่าง ๆ ถนนจะตัดกันเฉพาะที่แยกเท่านั้น แต่ถนนสามารถข้ามกันหรือลอดกันได้ แต่ละคู่ของแยกจะเชื่อมกันด้วยถนนอย่างมากหนึ่งเส้น ที่ทุก ๆ แยก '''v''' จะมีสถานีตำรวจที่มีตำรวจดูแล '''p(v)''' คน ถนนเชื่อมระหว่างแยก '''u''' และ '''v''' จะปลอดภัยถ้ามีตำรวจรวมอย่างน้อย '''b(u,v)''' คนจากสองสถานีที่เป็นแยกปลายถนนดังกล่าว เมื่อเริ่มต้น '''p(u)+p(v) >= b(u,v)''' สำหรับทุก ๆ ถนน

	== Warehouse Store ==		== Warehouse Store ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:48, 14 พฤษภาคม 2556
แถว 30:		แถว 30:

	ให้แผนที่ของพื้นที่ ให้หาจำนวนครั้งที่น้อยที่สุดที่จะทำให้พื้นดินนั้นมีความสูงเท่ากับระดับพื้น นั่นคือ ทุก ๆ ช่องมีความสูงเท่ากับ '''0''' ระหว่างการดำเนินการ ความสูงของช่องต่าง ๆ อาจจะมีค่าเป็นอย่างไรก็ได้ นั่นคือ อาจจะมีค่าเป็นลบก็ได้		ให้แผนที่ของพื้นที่ ให้หาจำนวนครั้งที่น้อยที่สุดที่จะทำให้พื้นดินนั้นมีความสูงเท่ากับระดับพื้น นั่นคือ ทุก ๆ ช่องมีความสูงเท่ากับ '''0''' ระหว่างการดำเนินการ ความสูงของช่องต่าง ๆ อาจจะมีค่าเป็นอย่างไรก็ได้ นั่นคือ อาจจะมีค่าเป็นลบก็ได้
		+
		+
		+	== Minimalist Security ==
		+
		+	source: [http://main.edu.pl/en/archive/oi/19/bez]
		+
		+	== Warehouse Store ==
		+
		+	source: [http://main.edu.pl/en/archive/oi/19/hur]
		+
		+	== Prefixuffix ==
		+
		+	source: [http://main.edu.pl/en/archive/oi/19/pre]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:22, 13 พฤษภาคม 2556
แถว 29:		แถว 29:
	Byteasar ตั้งใจจะสร้างบ้าน เขาได้เลือกพื้นที่ที่แคบเป็นเส้นเพื่อสร้างบ้านนั้น ก่อนที่เขาจะสร้างบ้านได้ เขาจะต้องทำพื้นที่ให้เรียบเสียก่อน เขามีเครื่องปรับหน้าดินอยู่สองเครื่อง เครื่องแรกสามารถเพิ่มหรือลดความสูงของที่ดินที่ติดกันเป็นระดับ '''a''' เมตรพอดี อีกเครื่องก็ทำได้ลักษณะเดียวกัน กล่าวคือสามารถเพิ่มหรือลดระดับความสูงของที่ดินที่ติดกัน แต่เป็นระดับเท่ากับ '''b''' เมตรพอดี สังเกตว่าก่อนหรือหลังการปรับระดับ ไม่จำเป็นที่ที่ดินในส่วนที่ปรับระดับจะต้องมีระดับที่เท่ากัน		Byteasar ตั้งใจจะสร้างบ้าน เขาได้เลือกพื้นที่ที่แคบเป็นเส้นเพื่อสร้างบ้านนั้น ก่อนที่เขาจะสร้างบ้านได้ เขาจะต้องทำพื้นที่ให้เรียบเสียก่อน เขามีเครื่องปรับหน้าดินอยู่สองเครื่อง เครื่องแรกสามารถเพิ่มหรือลดความสูงของที่ดินที่ติดกันเป็นระดับ '''a''' เมตรพอดี อีกเครื่องก็ทำได้ลักษณะเดียวกัน กล่าวคือสามารถเพิ่มหรือลดระดับความสูงของที่ดินที่ติดกัน แต่เป็นระดับเท่ากับ '''b''' เมตรพอดี สังเกตว่าก่อนหรือหลังการปรับระดับ ไม่จำเป็นที่ที่ดินในส่วนที่ปรับระดับจะต้องมีระดับที่เท่ากัน

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 12:22, 13 พฤษภาคม 2556
แถว 26:		แถว 26:

	Source: [http://main.edu.pl/en/archive/oi/19/wyr]		Source: [http://main.edu.pl/en/archive/oi/19/wyr]
		+
		+	Byteasar ตั้งใจจะสร้างบ้าน เขาได้เลือกพื้นที่ที่แคบเป็นเส้นเพื่อสร้างบ้านนั้น ก่อนที่เขาจะสร้างบ้านได้ เขาจะต้องทำพื้นที่ให้เรียบเสียก่อน เขามีเครื่องปรับหน้าดินอยู่สองเครื่อง เครื่องแรกสามารถเพิ่มหรือลดความสูงของที่ดินที่ติดกันเป็นระดับ '''a''' เมตรพอดี อีกเครื่องก็ทำได้ลักษณะเดียวกัน กล่าวคือสามารถเพิ่มหรือลดระดับความสูงของที่ดินที่ติดกัน แต่เป็นระดับเท่ากับ '''b''' เมตรพอดี สังเกตว่าก่อนหรือหลังการปรับระดับ ไม่จำเป็นที่ที่ดินในส่วนที่ปรับระดับจะต้องมีระดับที่เท่ากัน
		+
		+	ให้แผนที่ของพื้นที่ ให้หาจำนวนครั้งที่น้อยที่สุดที่จะทำให้พื้นดินนั้นมีความสูงเท่ากับระดับพื้น นั่นคือ ทุก ๆ ช่องมีความสูงเท่ากับ 0 ระหว่างการดำเนินการ ความสูงของช่องต่าง ๆ อาจจะมีค่าเป็นอย่างไรก็ได้ นั่นคือ อาจจะมีค่าเป็นลบก็ได้