Poi20

Bytecomputer (Stage III day 1)

Source: [1]

Memory limit: 128 MB

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

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

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

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

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

• บรรทัดแรกระบุจำนวนเต็ม n (1 <= n <= 1 000 000) จำนวนข้อมูลในลำดับป้อนเข้า
• บรรทัดที่สองมีจำนวนเต็ม n จำนวน x₁, x₂, ..., x_n จากเซต {-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 (-10⁹ <= xi,yi <= 10⁹

ตัวอย่าง

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