레이팅 미적용August 16 – 23, Cairo
Contest Day 1 – Type Printer
English 1.1
활자 인쇄기 (TYPE PRINTER)
여러분은 활자 인쇄기로 N개의 단어를 인쇄해야 한다. 활자 인쇄기는 단어를 만들기 위해 (각각 글자 하나가 새겨진) 작은 금속 조각들을 배치해야 하는 옛날 인쇄기이다. 그 위에 종이를 눌러 단어를 인쇄한다. 여러분의 인쇄기는 다음 연산들을 할 수 있다:
• 현재 인쇄기에 있는 단어의 끝에 글자 하나를 추가한다.
• 현재 인쇄기에 있는 단어의 끝에서 마지막 글자를 제거한다. 이는 인쇄기에 글자가 적어도 하나 있을 때만 할 수 있다.
• 현재 인쇄기에 있는 단어를 인쇄한다.
처음에 인쇄기는 비어 있다. 즉, 글자가 새겨진 금속 조각이 하나도 없다. 인쇄가 끝났을 때 인쇄기에 글자를 남겨 두어도 된다. 또한 단어들을 원하는 어떤 순서로든 인쇄해도 된다.
모든 연산에는 시간이 걸리므로, 총 연산 수를 최소화하고 싶다.
TASK
인쇄하려는 N개의 단어가 주어졌을 때, 임의의 순서로 모든 단어를 인쇄하는 데 필요한 최소 연산 수를 구하고, 그러한 연산 순서 하나를 출력하는 프로그램을 작성하시오.
EXAMPLE
Sample input
Sample output
3
print
the
poem
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
1 <= N <= 25,000
인쇄해야 하는 단어의 수.
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 인쇄해야 하는 단어의 수인 정수 N이 주어진다.
• 다음 N개의 줄에는 각각 단어 하나가 주어진다. 각 단어는 소문자(‘a’ – ‘z’)로만 이루어져 있으며 길이는 1 이상 20 이하이다.
모든 단어는 서로 다르다.
프로그램은 표준 출력에 다음 데이터를 출력해야 한다:
• 첫 줄에는 N개의 단어를 인쇄하는 데 필요한 최소 연산 수를 나타내는 정수 M을 출력해야 한다.
• 다음 M개의 줄에는 각각 문자 하나씩을 출력해야 한다. 이 문자들은 수행한 연산의 순서를 나타낸다. 각 연산은 다음과 같이 나타내야 한다:
o 글자 추가는 그 글자 자체를 소문자로 나타낸다
o 마지막 글자 제거는 문자 ‘‐‘ (마이너스, ASCII 코드 45)로 나타낸다
o 현재 단어 인쇄는 문자 ‘P’ (대문자 P)로 나타낸다
GRADING
총 40점에 해당하는 여러 테스트에서 N은 18을 넘지 않는다.
August 16 – 23, Cairo
Contest Day 1 – Type Printer
English 1.1
DETAILED FEEDBACK
대회 중에는 이 문제에 대한 제출물이 공식 테스트 데이터의 일부로 평가되며, 결과 요약을 볼 수 있다.