2008 : เครื่องพิมพ์เรียงพิมพ์
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)

คุณต้องพิมพ์คำทั้งหมด N คำด้วยเครื่องพิมพ์แบบโบราณ โดยเครื่องพิมพ์ชนิดนี้ใช้เทคโนโลยีเรียงพิมพ์แบบเก่า ซึ่งต้องวางแผ่นโลหะตัวอักษร (แต่ละแผ่นมีหนึ่งตัวอักษร) หลายตัวเรียงต่อกันเป็นคำ แล้วจึงกดแผ่นโลหะตัวอักษรเหล่านั้นลงบนกระดาษเพื่อเป็นการพิมพ์ เครื่องพิมพ์ชนิดนี้รองรับการดำเนินการที่กำหนดให้สามแบบดังต่อไปนี้

-         เพิ่มตัวอักษรหนึ่งตัวอักษรต่อท้ายคำที่มีอยู่แล้วในเครื่องพิมพ์

-         ลบตัวอักษรตัวสุดท้ายจากคำที่มีอยู่แล้วในเครื่องพิมพ์ คุณสามารถทำอย่างนี้ได้ถ้ามีอย่างน้อยหนึ่งตัวอักษรอยู่ในเครื่องพิมพ์

-         พิมพ์คำที่มีอยู่แล้วในเครื่องพิมพ์

เมื่อเริ่มต้น เครื่องพิมพ์จะไม่มีแผ่นโลหะตัวอักษรใดๆอยู่เลย  และเมื่อจบการพิมพ์ คุณสามารถปล่อยตัวอักษรให้ค้างอยู่ในเครื่องพิมพ์ได้ นอกจากนี้คุณสามารถเลือกพิมพ์คำใดก่อนหรือหลังได้

เนื่องจากทุกการดำเนินการต้องใช้เวลาประมวลผล ดังนั้นคุณต้องการใช้จำนวนการดำเนินการให้น้อยที่สุด

โจทย์

คุณต้องเขียนโปรแกรมเพื่อรับคำทั้งหมด N คำที่คุณต้องพิมพ์ แล้วหาจำนวนการดำเนินการที่น้อยที่สุดที่จะพิมพ์คำได้ทั้งหมด และแสดงผลลัพธ์ในรูปของลำดับของการดำเนินการแบบหนึ่ง ถ้ามีหลายแบบสามารถตอบแบบใดก็ได้

เงื่อนไข

1 N 25,000            N  คือจำนวนคำทั้งหมดที่คุณต้องพิมพ์

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

โปรแกรมของคุณต้องอ่านข้อมูลเข้าต่อไปนี้จาก standard input

-         บรรทัดที่ ๑ เป็นจำนวนเต็ม N ซึ่ง N เป็นคำทั้งหมดที่คุณต้องพิมพ์

-     บรรทัดต่อจากนั้น  N บรรทัด โดยแต่ละบรรทัดจะมีคำหนึ่งคำ ซึ่งแต่ละคำประกอบด้วยตัวอักษรตัวพิมพ์เล็ก (‘a’—‘z’) เท่านั้น  และมีความยาวของคำตั้งแต่ 1 ถึง 20 ตัวอักษร  โดยคำทั้งหมดไม่ซ้ำกัน

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

โปรแกรมของคุณต้องแสดงผลลัพธ์เป็นข้อมูลต่อไปนี้ออกทาง standard output

-         บรรทัดที่ ๑ เป็นจำนวนเต็ม M ซึ่ง M เป็นจำนวนครั้งของการดำเนินการที่น้อยที่สุดในการพิมพ์คำที่เป็นข้อมูลนำเข้า N คำ

-     ต่อจากนั้น M บรรทัด โดยแต่ละบรรทัดจะแสดงตัวอักขระหนึ่งตัว โดยตัวอักขระเหล่านี้ แทนลำดับของการดำเนินการเพื่อพิมพ์นั่นเอง  ซึ่งแต่ละการดำเนินการสามารถแทนได้ดังนี้

            การเพิ่มตัวอักษรหนึ่งตัว แสดงโดยตัวอักษรที่ต้องการเพิ่มที่เป็นตัวพิมพ์เล็ก

            การลบตัวอักษรตัวสุดท้าย แสดงโดยเครื่องหมาย ‘-‘ (เครื่องหมายลบ, ASCII code 45)

            การพิมพ์คำล่าสุดที่เรียงค้างไว้ในเครื่องพิมพ์ แสดงโดยตัวอักษร ‘P’ (ตัวพิมพ์ใหญ่ P)

การให้คะแนน

มีคะแนนรวมให้ 40 คะแนน สำหรับชุดทดสอบที่ N ไม่เกิน 18

ที่มา: 20th International Olympiad in Informatics; Cairo, Egypt (Day 1)


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3
print
the
poem
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 18 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)