Over the Hill, Part 2

시간 제한1초메모리 제한1024 MB

요약

행렬 크기 n과 평문, 암호문 한 쌍이 주어질 때 법 36에서 n×n 힐 암호 행렬을 구합니다. 해가 없거나 여러 개이면 그 사실을 출력합니다.

난이도: 보통10점 중 7점
유형: 행렬, 수학, 정수론
정답자: 아직 제출이 없습니다

문제

Bob Roberts는 CIA(Chocolate Institute of Alabama) 소속 첩보 팀에서 일한다. 그는 적국 기관인 NSA(Nougat Society of Arkansas)의 암호 통신문을 해독하려 한다. NSA는 이전 문제에서 설명한 Hill 암호 방식을 쓰는데, 이 방식은 평문과 암호문 쌍이 있으면 뚫리는 known-plaintext 공격에 취약하다. Bob은 평문과 암호문 쌍 하나를 가로챘고, NSA가 쓰는 암호 행렬의 크기도 알고 있다. 이 정보로 암호 행렬을 구할 수 있는 방법이 있다고 Bob은 믿지만, 팀원 중 누구도 그 방법을 모른다. Bob은 당신에게 이 문제를 풀어 달라고 부탁한다. 가로챈 데이터만으로는 행렬이 하나로 정해지지 않을 수도 있고, 데이터가 손상되어 조건을 만족하는 행렬이 없을 수도 있다.

입력

첫 줄에는 암호 행렬과 벡터의 크기를 나타내는 양의 정수 $n \leq 10$ 이 주어진다. 둘째 줄에는 평문, 셋째 줄에는 암호문이 주어진다. 두 줄은 모두 $A$ , $\ldots$ , $Z$ , $0$ , $\ldots$ , $9$ 문자와 공백 문자로만 이루어진다. 두 문자열의 길이는 같고 $n$ 의 배수이다. 두 문자열 모두 끝에 공백이 있을 수 있다.

출력

입력과 맞는 암호 행렬이 없으면 No solution을 출력한다. 입력과 맞지만 행렬이 하나로 정해지지 않으면 Too many solutions를 출력한다. 그 밖의 경우에는 암호 행렬을 한 줄에 한 행씩 출력하며, 한 행의 값 사이는 공백 한 칸으로 구분한다.

예제3

예제 1

입력

3
ATTACK AT DAWN 
FPLSFA4SUK2W9K3

예상 출력

30 1 9
4 23 7
5 9 13

예제 2
입력
```
3
ATTACK
FPLSFA
```
예상 출력
```
Too many solutions
```

예제 3

입력

3
ATTACK AT DAWN 
EPLSFA4SUK2W9K3

예상 출력

No solution