만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

JS 최소화

시간 제한2초메모리 제한512 MB

요약
예약 토큰 목록과 소스 줄이 주어졌을 때, 단어를 첫 등장 순서대로 a, b, ... 로 바꾸고 공백을 가장 적게 쓴 한 줄을 출력합니다.
난이도

보통10점 중 5점

유형
문자열, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

International Coding Procedures Company(ICPC)는 모든 코드를 Jedi Script(JS)로 작성한다. JS는 컴파일하지 않고 소스 형태 그대로 실행을 위해 전달한다. 소스에는 주석, 앞뒤 공백을 포함한 여분의 공백처럼 의미에는 영향을 주지 않으면서 크기만 키우는 요소가 있다. ICPC는 전달하기 전에 소스 파일을 최소화해서 의미는 그대로 두고 크기를 줄인다.

ICPC는 엄격한 관행을 따르므로 JS 문법도 제한되어 있다. 정수 알고리즘만 다루며 부동소수점과 문자열은 쓰지 않는다.

소스는 여러 줄로 이루어진다. 각 줄에는 공백으로 구분된 토큰이 0개 이상 있다. 한 줄에서 # 문자(ASCII 35)부터 줄 끝까지는 주석이며 무시한다.

각 줄은 왼쪽에서 오른쪽으로 파싱한다. 현재 위치에서 공백을 건너뛴 뒤, 그 자리에서 시작하는 가장 긴 토큰을 취한다. 토큰의 종류는 다음과 같다.

  • 예약 토큰: 최소화 과정에서 그대로 보존해야 하는 연산자, 구분자, 리터럴, 예약어, 라이브러리 함수 이름이다. 공백이 없는 ASCII 문자로 이루어진 고정된 문자열이며 #을 포함하지 않는다. 예약 토큰은 모두 입력으로 주어진다.
  • 숫자 토큰: 0부터 9까지의 숫자가 연속된 문자열이다.
  • 단어 토큰: 영문 소문자, 영문 대문자, 숫자, 밑줄(_, ASCII 95), 달러 기호($, ASCII 36)로 이루어진다. 숫자로 시작하지 않는다.

숫자 또는 단어의 정의에 맞는 가장 긴 문자열이 예약 토큰 목록에 있으면 그것은 예약 토큰으로 본다.

단어는 다음 순서로 이름을 바꾼다.

  1. 대상 단어 목록은 소문자로만 이루어진 단어를 길이순, 그다음 사전순으로 정렬한 것이다. a, b, ..., z, aa, ab, ... 순서이며 예약 토큰은 제외한다.
  2. 입력 토큰 열에서 처음 나온 단어를 대상 목록의 첫 단어로 바꾸고, 같은 단어의 이후 등장도 모두 바꾼다. 새로 나온 두 번째 단어에는 목록의 두 번째 단어를 쓰며, 이후도 같은 방식으로 진행한다.

목표는 바뀐 단어로 같은 토큰 열에 파싱되는 한 줄 중에서 공백 수가 가장 적은 줄을 만드는 것이다.

입력

첫 줄에 예약 토큰의 개수 nn(0≤n≤400 \le n \le 40)이 주어진다.

둘째 줄에 예약 토큰이 공백으로 구분되어 주어진다. 중복은 없다. 각 토큰은 1자 이상 20자 이하이며, ASCII 33부터 126까지의 문자만 쓰고 # 문자는 쓰지 않는다.

셋째 줄에 소스의 줄 수 mm(1≤m≤401 \le m \le 40)이 주어진다.

다음 mm개 줄에 소스가 주어진다. 각 줄은 앞뒤 공백을 포함해 최대 80자이며, ASCII 32부터 126까지의 문자만 쓴다. 소스는 유효하며 토큰 열로 완전히 파싱된다.

출력

최소화된 소스를 한 줄로 출력한다. 출력은 입력과 같은 토큰 열로 파싱되어야 하며, 단어는 위에서 설명한 규칙대로 이름이 바뀌어 있어야 한다. 공백 수는 가능한 한 적어야 한다. 최소 공백 수를 만족하는 배치가 여럿이면 어느 것을 출력해도 된다.

예제2

  1. 예제 1

    입력
    16
fun while return var { } ( ) , ; > = + ++ - --
9
fun fib(num) { # compute fibs
  var return_value = 1, prev = 0, temp;
  while (num > 0) {
    temp = return_value; return_value = return_value + prev;
    prev = temp;
    num--;
  }
  return return_value;
}
    예상 출력
    fun a(b){var c=1,d=0,e;while(b>0){e=c;c=c+d;d=e;b--;}return c;}

  2. 예제 2

    입력
    10
( ) + ++ : -> >> >>: b c)
2
($val1++ + +4 kb) >> :out
b-> + 10 >>: t # using >>:
    예상 출력
    (a+++ +4c )>> :d b->+10>>:e