ผลต่างระหว่างรุ่นของ "Poi20"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้ 1 คน)
แถว 39: แถว 39:
 
ตัวอย่างข้อมูลทดสอบ: (ดูจากโทย์ภาษาอังกฤษ)
 
ตัวอย่างข้อมูลทดสอบ: (ดูจากโทย์ภาษาอังกฤษ)
  
Task author: Jacek Tomasiewicz.
+
'''Task author:''' Jacek Tomasiewicz.
  
 
== Maze (Stage III day 1) ==
 
== Maze (Stage III day 1) ==
แถว 87: แถว 87:
 
* 3ocen: n = 100 000, a staircase.
 
* 3ocen: n = 100 000, a staircase.
  
Task author: Tomasz Idziaszek
+
'''Task author:''' Tomasz Idziaszek
 +
 
 +
== Colorful Chain (Stage III day 1) ==
 +
 
 +
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.

รุ่นแก้ไขปัจจุบันเมื่อ 13:42, 19 เมษายน 2557

Bytecomputer (Stage III day 1)

Source: [1]

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)

Source: [2]

Memory limit: 128MB

เมื่อเร็ว ๆ นี้ Byteasar ได้อ่านเรื่องเล่าที่น่าสนใจเรื่องหนึ่ง ตัวละครเอกเป็นเจ้าชายชาวกรีกที่ปราบสัตว์ร้ายลงได้ แต่มีเรื่องอื่นที่ทำให้ Byteasar ติดใจ นั่นคือฉากสุดท้ายนั้นเกิดขึ้นภายในเขาวงกต หลังจากนั้นมา Byteasar ก็บ้าคลั่งเกี่ยวกับเขาวงกต

Byteasar ได้ร่างแผนที่เขาวงกตลงในกระดาษสี่เหลี่ยมจัตุรัส ในแต่ละรูปร่างนั้นจะมี polygon ที่มีด้าน (แทนกำแพงของเขาวงกต) โดยด้านต่าง ๆ นั้นจะขนานกับขอบด้านใดด้านหนึ่งของกระดาษ (นั่นคือจะขนานกับแกนของพิกัดคาร์ทีเซียน) และทุก ๆ ด้านจะตั้งฉากกัน Byteasar สังเกตว่าถ้าประตูทางเข้าถูกกำหนดขึ้นที่ด้านหนึ่งของเขาวงกต เราจะสามารถเดินรอบเขาวงกตแล้วกลับมาที่ประตูทางเข้าได้ โดยที่ในระหว่างเดินนั้นให้หันหน้าให้แขนขวาอยู่ข้างผนังระหว่างเดิน

ยิ่งไปกว่านั้น ระหว่างที่เดินไปในเขาวงกต เราสามารถจดลงไปได้ว่าเราเลี้ยวทางใดบ้าง เราจะเขียนตัวอักษร L ถ้าเราเลี้ยวซ้ายเมื่อเราเดินไปตามขอบกำแพง และเขียน P ถ้าเราเลี้ยวขวา Byteasar สงสัยว่าถ้าให้ลำดับของตัวอักษร L และ P ใด ๆ มา จะมีเขาวงกตที่ทำให้การเดินสอดคล้องกับข้อความที่จดมานั้นหรือไม่?

ข้อมูลนำเข้า บรรทัดแรกระบุสตริงความยาว n ตัวอักษร (1 <= n <= 100 000) ประกอบด้วยตัวอักษร L และ P

มีข้อมูลทดสอบ 50% ที่ n <= 2500

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

ถ้าไม่มีเขาวงกตสอดคล้องกับสตริงดังกล่าว ให้ตอบ NIE ไม่เช่นนั้นให้พิมพ์คำตอบ n บรรทัดที่ระบุเขาวงกต บรรทัดที่ i ให้ระบุจำนวนเต็มสองจำนวน xi และ yi (-109 <= xi,yi <= 109

ตัวอย่าง

For the input data:

LLLLPPLL

the correct result is:

0 0
2 0
2 2
-1 2
-1 -2
1 -2
1 -1
0 -1

ดูรูปประกอบได้จากต้นทาง: [3]

ตัวอย่างข้อมูลทดสอบ

  • 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

Colorful Chain (Stage III day 1)

Source: [4]

Little Bytie ชอบที่จะเล่นกับโซ่สีสวย เขาได้มีโซ่เก็บไว้ชุดหนึ่ง บางเส้นเขาก็ชอบมากกว่าเส้นอื่น ๆ โซ่แต่ละเส้นประกอบไปด้วยห่วงสีสรรสวยงาม Byteasar สังเกตว่าสัญชาตญาณเกี่ยวกับความงามของ Bytie นั้นแม่นยำมาก ทั้งนี้เนื่องจาก Bytie จะพิจารณาว่าส่วนของโซ่ที่ติดกันนั้น "ดูสวย" (nice) ถ้าโซ่นั้นมีห่วงสี c1 จำนวน l1 ห่วง, ห่วงสี c2 จำนวน l2 ห่วง, ..., ห่วงสี cm จำนวน lm ห่วงพอดี และไม่มีห่วงสีอื่น ๆ อีกเลย ความน่าสนใจของโซ่นั้นมีค่าเท่ากับจำนวนส่วนย่อยที่ติดกันของโซ่นั้นที่ดูสวย (nice) Byteasar ได้พยายามทดลองเพื่อหาค่า c1,...,cm และ l1,...,lm ตอนนี้เขาต้องการให้คุณเขียนโปรแกรมช่วยในการซื้อของ

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

  • บรรทัดแรกระบุจำนวนเต็ม n และ m (1 <= m <= n <= 1 000 000) โดยที่ n แทนความยาวของโซ่และ m แทนความยาวของรายละเอียดของส่วนย่อยที่ดูสวย
  • บรรทัดที่สองระบุจำนวนเต็ม m จำนวน l1, l2,...,lm (1 <= li <= n) คั่นด้วยช่องว่าง
  • บรรทัดที่สามระบุจำนวนเต็ม m จำนวน c1,c2,...,cm (1 <= ci <= n; ci ไม่เท่ากับ cj ถ้า i ไม่เท่ากับ j) คั่นด้วยช่องว่าง ลำดับ c1,...,cm และ l1,...,lm จะระบุข้อมูลของโซ่ที่ดูสวย
  • บรรทัดที่สี่ระบุจำนวนเต็ม n จำนวน a1,...,an (1 <= ai <= 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.