Informatica Online Judge

  암호체계 #3 [2226 / 08B2]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 10   Total Tried : 4


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[35th 유문현]
Writer ID : [gs17067]

Background

앵딱이는 자신만의 새로운 암호를 만들고 싶었다. 그래서 그는 다음과 같은 암호 체계를 만들었다.

길이가 M (>= 2)인 문자열 A와 N X N (1 <=N <= 26) 암호 테이블이 주어진다. 문자열 A와 암호 테이블은 사전 순으로 N번째 이하인 알파벳 대문자로만 이루어진다. 암호 테이블의 i행 j열 문자를 𝑇𝑎𝑏𝑙𝑒(𝑖, 𝑗)라 하자.

문자열 A를 암호화 한 문자열 B는 길이가 M-1이다. A = 𝑎_1 𝑎_2…𝑎_(𝑚−1) 𝑎_𝑚, B= 𝑏_1 𝑏_2…𝑏_(𝑚−2) 𝑏_(𝑚−1) 이라 할 때, 𝑏_𝑖 = 𝑇𝑎𝑏𝑙𝑒(𝑎_𝑖, 𝑎_(𝑖+1) )이다.

예로, 아래와 같은 N=6 암호 테이블이 주어졌을 때, "BADCAE"는 "CEEEA"로 암호화된다.



이러한 암호 체계를 만들고 신나 하던 앵딱이는 CrePusCule의 지적을 듣고 충격을 먹었다. 암호화된 문자열을 복호화 할 때 한 가지 이상의 가능한 문자열이 생길 수 있기 때문에, 제대로 복호화 할 수가 없다는 것이다.

CrePusCule은 한심한 앵딱이의 암호 체계를 수정하여 다음과 같은 암호 체계를 만들었다.

앵딱이의 체계대로 문자열 A를 암호화 한 문자열 B를 복호화 할 시 가능한 모든 문자열 중, 문자열 A가 사전순으로 k번째라 하면, 문자열 B 뒤에 수 k를 덧붙여 문자열 B’을 만든다.

예로, 위 암호 테이블이 주어졌을 때 A = "BADCAE"는 B = "CEEEA"로 암호화되고, 이를 복호화 하면 문자열 A는 가능한 모든 문자열 중에서 사전 순으로 "BADCAB" 다음인 두 번째이므로, CrePusCule의 체계대로 암호화하면 문자열 A는 B" = "CEEEA2"로 암호화된다.

N X N 암호 테이블과 문자열 A가 주어졌을 때, 이를 CrePusCule 의 체계대로 암호화한 문자열 B"을 출력하시오.

Input

첫 번째 줄에 N (1 <= N <= 26) 이 주어진다.

두 번째 줄부터 N+1번째 줄까지는 N X N 암호 테이블이 주어진다. 암호 테이블의 각 문자는 사전 순으로 N번째보다 크지 않음이 보장된다.

N+2번째 줄에는 M이 주어진다.

N+3번째 줄에는 문자열 A가 주어진다. A의 각 문자는 사전 순으로 N번째보다 크지 않음이 보장된다.

Sub Task #3
#3 : N <= 26, M <= 〖10〗^5, k는 〖10〗^12을 넘지 않는다.

Output

첫 번째 줄에 A를 CrePusCule의 체계대로 암호화한 문자열 B"를 출력한다.
단, 암호화할 수 없다면 -1을 출력한다.

IO Example

입력 1
6
BADEAF
CFAFAB
EBABBE
CCECDC
ABDEAF
EFAFBA
6
BADCAE

출력 1
CEEEA2

입력 2
5
AAAAA
AAAAA
AAAAA
AAAAA
AAAAA
4
BBDD

출력 2
AAA169

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]