¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#10448

충돌하는 인코딩 20s 2048MB

Problemas

앨런은 오늘 학교에서 처음으로 암호학 수업을 들었다. 그는 배운 내용을 적용해 자신만의 암호를 만들기로 했다. 그는 영어 알파벳 A부터 Z까지의 각 글자를 10진수 숫자 0부터 9까지에 대응시킨다. 그런 다음 단어의 각 글자를 대응된 숫자로 바꾸어, 10진수 숫자들로만 이루어진 문자열로 단어를 인코딩하려고 한다.

하지만 들뜬 나머지, 앨런은 영어 알파벳이 26자이고 10진수 숫자는 10개뿐이라는 사실을 놓쳤다. 그 결과, 서로 다른 두 단어의 인코딩이 같아지는 충돌이 발생할 수 있다.

앨런이 인코딩하려는 \mathbf{N}개의 단어 목록과 그가 사용하는 대응이 주어졌을 때, 목록 안의 단어들 사이에 충돌이 있는지 알아내라.


Entrada

입력의 첫 줄에는 테스트 케이스 개수 \mathbf{T}가 주어진다. 이어서 \mathbf{T}개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 26개의 10진수 숫자(정수 0 이상 9 이하) \mathbf{D_A}, \mathbf{D_B}, \dots, \mathbf{D_Z}가 주어지며, 이는 앨런이 사용하는 대응을 나타낸다. 글자 \alpha는 숫자 \mathbf{D_\alpha}에 대응된다.
각 테스트 케이스의 둘째 줄에는 앨런이 인코딩할 단어의 개수 \mathbf{N}이 주어진다.
이어지는 \mathbf{N}개의 줄 중 i-번째 줄에는 문자열 \mathbf{S_i}가 주어지며, 이는 앨런이 인코딩할 i-번째 단어를 나타낸다.


Salida

각 테스트 케이스마다 한 줄을 출력하라. 형식은 Case #x: y이며, 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 인코딩이 같은 서로 다른 두 단어가 하나라도 있으면 YES, 그렇지 않으면 NO이다.


Ejemplo 

2
0 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
4
ABC
BC
BCD
CDE
0 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
3
CDE
DEF
EFG
Case #1: NO
Case #2: YES
샘플 케이스 #1에서 A의 매핑은 0, B는 1, C는 2, D는 3, E는 3이다. 이 매핑으로 ABC는 012, BC는 12, BCD는 123, CDE는 233으로 인코딩된다. 이 인코딩들이 모두 서로 다르므로 충돌이 없다. 샘플 케이스 #2에서 C의 매핑은 2, D는 3, E는 3, F는 3, G는 3이다. 이 매핑으로 CDE는 233, DEF는 333, EFG는 333으로 인코딩된다. DEF와 EFG의 인코딩이 같으므로 충돌이 발생한다.

Fuente

GCJ 2023a A

Debes iniciar sesión para escribir código.