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

158.108.202.34: /* Colorful Chain (Stage III day 1) */

2014-04-19T13:42:58Z

Colorful Chain (Stage III day 1)

Jittat: /* Colorful Chain (Stage III day 1) */

2014-04-19T11:19:21Z

Colorful Chain (Stage III day 1)

Jittat: /* Maze (Stage III day 1) */

2014-04-19T09:51:16Z

Maze (Stage III day 1)

Jittat เมื่อ 09:49, 19 เมษายน 2557

2014-04-19T09:49:59Z

Jittat: /* Maze (Stage III day 1) */

2014-04-19T09:49:27Z

Maze (Stage III day 1)

Jittat: /* Maze (Stage III day 1) */

2014-04-19T08:49:45Z

Maze (Stage III day 1)

Jittat: หน้าที่ถูกสร้างด้วย '== Bytecomputer (Stage III day 1) == Source: [http://main.edu.pl/en/archive/oi/20/baj] '''Memory limit: 128 MB''' คุณได้...'

2014-04-19T08:37:26Z

หน้าที่ถูกสร้างด้วย '== Bytecomputer (Stage III day 1) == Source: [http://main.edu.pl/en/archive/oi/20/baj] '''Memory limit: 128 MB''' คุณได้...'

หน้าใหม่

== Bytecomputer (Stage III day 1) ==

Source: [http://main.edu.pl/en/archive/oi/20/baj]

'''Memory limit: 128 MB'''

คุณได้รับลำดับของจำนวนเต็ม n จำนวน x1, x2, ..., xn จากเซต {-1,0,1} ''bytecomputer'' เป็นเครื่องมือสำหรับประมวลผลกับลำดับดังกล่าว ได้ดังนี้

* เพิ่มค่า xi+1 ขึ้น xi สำหรับ i ใด ๆ ที่ 1 <= i <= n

ไม่มีขีดจำกัดของขอบเขตของจำนวนเต็มที่เครื่อง bytecomputer จะสามารถจัดเก็บได้ นั่นคือแต่ละ xi จะสามารถเก็บจำนวนมาก ๆ เท่าใดก็ได้ และน้อย ๆ เท่าใดก็ได้

โปรแกรมเครื่อง bytecomputer เพื่อแปลงลำดับป้อนเข้าให้เป็นลำดับที่ไม่ลดลง (non-decreasing sequence) นั่นคือลำดับที่ x1 <= x2 <= ... <= xn โดยใช้จำนวนครั้งของการประมวลผลให้น้อยที่สุด

'''ข้อมูลป้อนเข้า'''

* บรรทัดแรกระบุจำนวนเต็ม n (1 <= n <= 1 000 000) จำนวนข้อมูลในลำดับป้อนเข้า
* บรรทัดที่สองมีจำนวนเต็ม n จำนวน x1, x2, ..., xn จากเซต {-1,0,1}

มีข้อมูลชุดทดสอบ 24% ที่ n <= 500 และ 48% ที่ n <= 10 000

'''ข้อมูลส่งออก'''

บรรทัดแรกและบรรทัดเดียวจะมีจำนวนเต็มหนึ่งจำนวน แทนจำนวนครั้งของการดำเนินการที่น้อยที่สุดที่ bytecomputer จะต้องใช้ในการแปลงลำดับข้อมูลนำเข้า หรือคำว่า BRAK (แปลว่าไม่ในภาษาโปแลนด์) ถ้าไม่สามารถดำเนินการได้

'''ตัวอย่าง'''

สำหรับข้อมูลนำเข้า:

6
-1 1 0 -1 0 1

ผลลัพธ์ที่ถูกต้องคือ:

3

คำอธิบาย: ใช้การดำเนินการ 3 ครั้ง ทำให้ได้ลำดับ -1, -1, -1, -1, 0, 1

ตัวอย่างข้อมูลทดสอบ: (ดูจากโทย์ภาษาอังกฤษ)

Task author: Jacek Tomasiewicz.

== Maze (Stage III day 1) ==

@@ แถว 93: / แถว 93: @@
 Source: [http://main.edu.pl/en/archive/oi/20/lan]
-Little Bytie ชอบที่จะเล่นกับโซ่สีสวย เขาได้มีโซ่เก็บไว้ชุดหนึ่ง บางเส้นเขาก็ชอบมากกว่าเส้นอื่น ๆ  โซ่แต่ละเส้นประกอบไปด้วยห่วงสีสรรสวยงาม  Byteasar สังเกตว่าสัญชาตญาณเกี่ยวกับความงามของ Bytie นั้นแม่นยำมาก  ทั้งนี้เนื่องจาก Bytie จะพิจารณาว่าส่วนของโซ่ที่ติดกันนั้น "ดูสวย" (nice) ถ้าโซ่นั้นมีห่วงสี c<sub>1</sub> จำนวน l</sub>1</sub> ห่วง, ห่วงสี c<sub>2</sub> จำนวน l</sub>2</sub> ห่วง, ..., ห่วงสี c<sub>m</sub> จำนวน l</sub>m</sub> ห่วงพอดี และไม่มีห่วงสีอื่น ๆ อีกเลย  ความน่าสนใจของโซ่นั้นมีค่าเท่ากับจำนวนส่วนย่อยที่ติดกันของโซ่นั้นที่ดูสวย (nice)   Byteasar ได้พยายามทดลองเพื่อหาค่า c<sub>1</sub>,...,c<sub>m</sub> และ l<sub>1</sub>,...,l<sub>m</sub>   ตอนนี้เขาต้องการให้คุณเขียนโปรแกรมช่วยในการซื้อของ
+Little Bytie ชอบที่จะเล่นกับโซ่สีสวย เขาได้มีโซ่เก็บไว้ชุดหนึ่ง บางเส้นเขาก็ชอบมากกว่าเส้นอื่น ๆ  โซ่แต่ละเส้นประกอบไปด้วยห่วงสีสรรสวยงาม  Byteasar สังเกตว่าสัญชาตญาณเกี่ยวกับความงามของ Bytie นั้นแม่นยำมาก  ทั้งนี้เนื่องจาก Bytie จะพิจารณาว่าส่วนของโซ่ที่ติดกันนั้น "ดูสวย" (nice) ถ้าโซ่นั้นมีห่วงสี c<sub>1</sub> จำนวน l<sub>1</sub> ห่วง, ห่วงสี c<sub>2</sub> จำนวน l<sub>2</sub> ห่วง, ..., ห่วงสี c<sub>m</sub> จำนวน l<sub>m</sub> ห่วงพอดี และไม่มีห่วงสีอื่น ๆ อีกเลย  ความน่าสนใจของโซ่นั้นมีค่าเท่ากับจำนวนส่วนย่อยที่ติดกันของโซ่นั้นที่ดูสวย (nice)   Byteasar ได้พยายามทดลองเพื่อหาค่า c<sub>1</sub>,...,c<sub>m</sub> และ l<sub>1</sub>,...,l<sub>m</sub>   ตอนนี้เขาต้องการให้คุณเขียนโปรแกรมช่วยในการซื้อของ
 '''ข้อมูลป้อนเข้า'''

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 11:19, 19 เมษายน 2557
แถว 92:		แถว 92:

	Source: [http://main.edu.pl/en/archive/oi/20/lan]		Source: [http://main.edu.pl/en/archive/oi/20/lan]
		+
		+	Little Bytie ชอบที่จะเล่นกับโซ่สีสวย เขาได้มีโซ่เก็บไว้ชุดหนึ่ง บางเส้นเขาก็ชอบมากกว่าเส้นอื่น ๆ โซ่แต่ละเส้นประกอบไปด้วยห่วงสีสรรสวยงาม Byteasar สังเกตว่าสัญชาตญาณเกี่ยวกับความงามของ Bytie นั้นแม่นยำมาก ทั้งนี้เนื่องจาก Bytie จะพิจารณาว่าส่วนของโซ่ที่ติดกันนั้น "ดูสวย" (nice) ถ้าโซ่นั้นมีห่วงสี c<sub>1</sub> จำนวน l</sub>1</sub> ห่วง, ห่วงสี c<sub>2</sub> จำนวน l</sub>2</sub> ห่วง, ..., ห่วงสี c<sub>m</sub> จำนวน l</sub>m</sub> ห่วงพอดี และไม่มีห่วงสีอื่น ๆ อีกเลย ความน่าสนใจของโซ่นั้นมีค่าเท่ากับจำนวนส่วนย่อยที่ติดกันของโซ่นั้นที่ดูสวย (nice) Byteasar ได้พยายามทดลองเพื่อหาค่า c<sub>1</sub>,...,c<sub>m</sub> และ l<sub>1</sub>,...,l<sub>m</sub> ตอนนี้เขาต้องการให้คุณเขียนโปรแกรมช่วยในการซื้อของ
		+
		+	'''ข้อมูลป้อนเข้า'''
		+
		+	* บรรทัดแรกระบุจำนวนเต็ม n และ m (1 <= m <= n <= 1 000 000) โดยที่ n แทนความยาวของโซ่และ m แทนความยาวของรายละเอียดของส่วนย่อยที่ดูสวย
		+	* บรรทัดที่สองระบุจำนวนเต็ม m จำนวน l<sub>1</sub>, l<sub>2</sub>,...,l<sub>m</sub> (1 <= l<sub>i</sub> <= n) คั่นด้วยช่องว่าง
		+	* บรรทัดที่สามระบุจำนวนเต็ม m จำนวน c<sub>1</sub>,c<sub>2</sub>,...,c<sub>m</sub> (1 <= c<sub>i</sub> <= n; c<sub>i</sub> ไม่เท่ากับ c<sub>j</sub> ถ้า i ไม่เท่ากับ j) คั่นด้วยช่องว่าง ลำดับ c<sub>1</sub>,...,c<sub>m</sub> และ l<sub>1</sub>,...,l<sub>m</sub> จะระบุข้อมูลของโซ่ที่ดูสวย
		+	* บรรทัดที่สี่ระบุจำนวนเต็ม n จำนวน a<sub>1</sub>,...,a<sub>n</sub> (1 <= a<sub>i</sub> <= n) แทนสีของห่วงในโซ่เรียงลำดับกัน
		+
		+	'''ข้อมูลส่งออก'''
		+
		+	มีหนึ่งบรรทัด แทนจำนวนส่วนย่อยของโซ่ที่ต่อเนื่องกันที่ดูสวย (nice)
		+
		+	'''ตัวอย่าง'''
		+
		+	For the input data:
		+
		+	7 3
		+	2 1 1
		+	1 2 3
		+	4 2 1 3 1 2 5
		+
		+	the correct result is:
		+
		+	2
		+
		+	คำอธิบายตัวอย่าง: ส่วนของโซ่ที่สวยในลำดับนี้คือ 2, 1, 3, 1 และ 1, 3, 1, 2.
		+
		+	ข้อมูลทดสอบตัวอย่าง:
		+
		+	* 1ocen n=9, m=3, two nice fragments with the second one following the first one immediately, with neither overlap nor additional links in between;
		+	* 2ocen n=10, m=5, the length of the nice fragment exceeds the length of the whole chain (the result is 0);
		+	* 3ocen n=19, m=7, three overlapping nice fragments;
		+	* 4ocen n=1000, m=500, the nice fragment contains a single link of the colors {1,...,500}, and the chain is a sequence of links of colors 1, 2, ..., 499, 500, 500, 499, ..., 2, 1 (the result is 2);
		+	* 5ocen n=1 000 000, m=2, the nice fragment contains a single link of color 1 and two links of color 2; the chain consists of links of colors 1, 2, 2, 1, 2, 2, ... (the result is 999 998).
		+
		+	'''Task author:''' Tomasz Walen.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:51, 19 เมษายน 2557
แถว 88:		แถว 88:

	'''Task author:''' Tomasz Idziaszek		'''Task author:''' Tomasz Idziaszek
		+
		+	== Colorful Chain (Stage III day 1) ==
		+
		+	Source: [http://main.edu.pl/en/archive/oi/20/lan]

@@ แถว 39: / แถว 39: @@
 ตัวอย่างข้อมูลทดสอบ: (ดูจากโทย์ภาษาอังกฤษ)
-Task author: Jacek Tomasiewicz.
+'''Task author:''' Jacek Tomasiewicz.
 == Maze (Stage III day 1) ==
@@ แถว 87: / แถว 87: @@
 * 3ocen: n = 100 000, a staircase.
-Task author: Tomasz Idziaszek
+'''Task author:''' Tomasz Idziaszek

@@ แถว 54: / แถว 54: @@
 '''ข้อมูลนำเข้า'''
 '''ข้อมูลส่งออก'''
 '''ตัวอย่าง'''
 ดูรูปประกอบได้จากต้นทาง: [http://main.edu.pl/en/archive/oi/20/lab]
@@ แถว 64: / แถว 83: @@
 ตัวอย่างข้อมูลทดสอบ
-ocen: n=12 , the word LLLLLLLLLLLL, answer NIE;
+* 1ocen: n=12 , the word LLLLLLLLLLLL, answer NIE;
-ocen: n = 100, a left-handed spiral;
+* 2ocen: n = 100, a left-handed spiral;
-ocen: n = 100 000, a staircase.
+* 3ocen: n = 100 000, a staircase.
 Task author: Tomasz Idziaszek

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 08:49, 19 เมษายน 2557
แถว 42:		แถว 42:

	== Maze (Stage III day 1) ==		== Maze (Stage III day 1) ==
		+
		+	Source: [http://main.edu.pl/en/archive/oi/20/lab]
		+
		+	'''Memory limit: 128MB'''
		+
		+	เมื่อเร็ว ๆ นี้ Byteasar ได้อ่านเรื่องเล่าที่น่าสนใจเรื่องหนึ่ง ตัวละครเอกเป็นเจ้าชายชาวกรีกที่ปราบสัตว์ร้ายลงได้ แต่มีเรื่องอื่นที่ทำให้ Byteasar ติดใจ นั่นคือฉากสุดท้ายนั้นเกิดขึ้นภายในเขาวงกต หลังจากนั้นมา Byteasar ก็บ้าคลั่งเกี่ยวกับเขาวงกต
		+
		+	Byteasar ได้ร่างแผนที่เขาวงกตลงในกระดาษสี่เหลี่ยมจัตุรัส ในแต่ละรูปร่างนั้นจะมี polygon ที่มีด้าน (แทนกำแพงของเขาวงกต) โดยด้านต่าง ๆ นั้นจะขนานกับขอบด้านใดด้านหนึ่งของกระดาษ (นั่นคือจะขนานกับแกนของพิกัดคาร์ทีเซียน) และทุก ๆ ด้านจะตั้งฉากกัน Byteasar สังเกตว่าถ้าประตูทางเข้าถูกกำหนดขึ้นที่ด้านหนึ่งของเขาวงกต เราจะสามารถเดินรอบเขาวงกตแล้วกลับมาที่ประตูทางเข้าได้ โดยที่ในระหว่างเดินนั้นให้หันหน้าให้แขนขวาอยู่ข้างผนังระหว่างเดิน
		+
		+	ยิ่งไปกว่านั้น ระหว่างที่เดินไปในเขาวงกต เราสามารถจดลงไปได้ว่าเราเลี้ยวทางใดบ้าง เราจะเขียนตัวอักษร L ถ้าเราเลี้ยวซ้ายเมื่อเราเดินไปตามขอบกำแพง และเขียน P ถ้าเราเลี้ยวขวา Byteasar สงสัยว่าถ้าให้ลำดับของตัวอักษร L และ P ใด ๆ มา จะมีเขาวงกตที่ทำให้การเดินสอดคล้องกับข้อความที่จดมานั้นหรือไม่?
		+
		+	'''ข้อมูลนำเข้า'''
		+
		+	'''ข้อมูลส่งออก'''
		+
		+	'''ตัวอย่าง'''
		+
		+
		+	ดูรูปประกอบได้จากต้นทาง: [http://main.edu.pl/en/archive/oi/20/lab]
		+
		+	ตัวอย่างข้อมูลทดสอบ
		+
		+	1ocen: n=12 , the word LLLLLLLLLLLL, answer NIE;
		+	2ocen: n = 100, a left-handed spiral;
		+	3ocen: n = 100 000, a staircase.
		+
		+
		+	Task author: Tomasz Idziaszek