34135번 - [U] Unraveling the History 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 17 | 11 | 10 | 62.500% |
문제
고려 시대의 학자 하의비는 최근 들어온 제자 바의히에게 활자의 역사를 가르치기로 했다. 이를 위해 목판 활자를 사용한 신라 시대의 기록을 연구하던 하의비는 놀라운 사실을 알아냈다. 바로 신라 시대의 사람들은 목판 활자를 사용하여 영어 알파벳 대문자로 구성된 문자열을 찍어냈다는 점과, 이를 숨기기 위해 이와 관련된 모든 기록을 암호화했다는 점이다!
하의비의 연구에 따르면 신라 시대의 학자들은 $T+26$개의 활자 문자열을 가지고 있으며, 알파벳 대문자 하나로 이루어진 기초 활자 문자열 $26$개와 학자들이 만든 $T$개의 복합 활자 문자열로 이루어져 있다. 기초 활자 문자열에는 A부터 Z까지 각각 $1$부터 $26$까지의 번호가 붙어있으며, 복합 활자 문자열에는 만든 순서대로 $1$부터 $T$까지의 번호가 매겨져 있다.
$t$번 복합 활자 문자열은 기초 활자 문자열과 이전에 만든 복합 활자 문자열을 총 $N_t$개 이어 붙여서 만들어지며, 이를 만드는 과정을 암호화한 수 $C_t$는 다음과 같이 만들어진다.
- 수열 $A$를 만든다. 초기에 이 수열은 비어 있다.
- $t$번 복합 활자 문자열의 끝에 활자 문자열을 하나씩 추가한다. 이때 수열 $A$에는 다음과 같이 원소를 추가한다.
- 만약 추가한 활자 문자열이 $i$번 기초 활자 문자열이라면, $A$의 끝에 $i$를 추가한다. $(1 \le i \le 26)$
- 만약 추가한 활자 문자열이 $i$번 복합 활자 문자열이라면, $A$의 끝에 $-i$를 추가한다. $(1 \le i < t)$
- $A$를 $26+t$진법으로 읽어서 $C_t$를 만든다. 정확히는, $C_t = \sum_{k=1}^{N_t}(26+t)^{N_t-k}A_{k}$이다.
$T$개의 암호화된 복합 활자 문자열이 주어질 때, 하의비의 연구에 따라 $T$개의 복합 활자 문자열을 모두 해독해 보자.
입력
첫째 줄에는 알아내야 하는 복합 활자 문자열의 수 $T$가 주어진다. $(1\le T\le 1\, 000\, 000)$
둘째 줄부터 $T$개의 줄에 걸쳐, $t+1$번째 줄에는 주어진 방법대로 암호화된 $t$번 복합 활자 문자열을 의미하는 정수 $C_t$가 주어진다. $(1\le |C_t|\le 10^{18})$
출력
첫째 줄부터 $T$개의 줄에 걸쳐, $t$번째 줄에는 $t$번 복합 활자 문자열을 출력한다.
$T$개의 활자 문자열의 길이의 합이 $1\,000\,000$을 넘지 않음이 보장된다.
예제 입력 1
3 225 2273 -31
예제 출력 1
HI BYE HIBYE
각 정수는 다음과 같이 해독할 수 있다.
- $225=8\cdot 27^1+9\cdot 27^0$이므로, $A=[8,9]$이다. 따라서 $1$번 복합 활자 문자열은
HI가 된다. - $2273=2\cdot 28^2+25\cdot 28^1+5\cdot 28^0$이므로, $A=[2,25,5]$이다. 따라서 $2$번 복합 활자 문자열은
BYE가 된다. - $-31=(-1)\cdot 29^1+(-2)\cdot 29^0$이므로, $A=[-1,-2]$이다. 따라서 $3$번 복합 활자 문자열은
HIBYE가 된다.
예제 입력 2
2 11318 -2704855681094
예제 출력 2
ONE ONETWOONESEVEN
출처
- 문제를 만든 사람: hibye1217
- 문제를 검수한 사람: iktk, mujigae, pyb1031, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호