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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(หน้าที่ถูกสร้างด้วย '== Bytecomputer (Stage III day 1) == Source: [http://main.edu.pl/en/archive/oi/20/baj] '''Memory limit: 128 MB''' คุณได้...')
 
แถว 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

รุ่นแก้ไขเมื่อ 08:49, 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 ใด ๆ มา จะมีเขาวงกตที่ทำให้การเดินสอดคล้องกับข้อความที่จดมานั้นหรือไม่?

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

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

ตัวอย่าง


ดูรูปประกอบได้จากต้นทาง: [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