시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 140 35 8 13.793%

문제

일반적으로, 대부분의  암호알고리즘은 단 하나만의 암호 키를 사용해서 암호화 파일을 해독한다. 만약 공격자가 해킹으로 암호 키를 취득하게 되면, 정보가 샐 위험이 있게 된다. 이를 막기 위해 고안된 것이 “Secret sharing”이란 기술이다.

“Secret Sharing“은 암호 키를 그룹에 있는 여러 사람에게 키를 나눠서 저장하는 방법이다.”Secret sharing“ 에서는 암호 키를 N개의 조각으로 분리하고 각각의 조각들은 share라고 부른다.

N개의 모든 조각을 얻지 못하면 암호 키를 복원할 수 없다.  예를 들면 'password'란 암호 키를 4개의 share들(pa, ss, wo, rd)로 나눌 때, 모든 share들이 있어야만 ‘password’란 암호 키를 복원해 낼 수 있다. 그리고, 암호를 복원할 때에는 모든 share뿐 아니라 share의 순서를 알아야만 한다. 만약 순서를 모른다면 ‘wosspard' 나 ’pawordss' 같은 잘못된 암호 키를 복원 해낼 수도 있기 때문이다.

최근, 새로운 암호 알고리즘에서는 매우 긴 10진수를 암호 키로 쓴다. 암호 키는 0이 아닌 숫자로 시작 되며, 그 암호 키는 여러 개의 share들로 분할된다. 이 share들의 순서는 매우 간단한 방법으로 되어있다. 모든 share를 써서 만들 수 있는 모든 기중 가장 작은 값이 암호 키가 되는 것이다. 예를 들면 2, 4, 11, 33, 00 이라는 5개의 share가 있다면 암호 키는 11002334 가 된다. (00112334 는 0으로 시작하기 때문에 암호 키가 될 수 없다).

N개의 share들로부터 암호 키를 복원해내는 프로그램을 작성하여 보자.

입력

첫 번째 줄에는 share들의 개수 N(1≤N≤100)이 주어지고, 다음 줄에는 5자리 이하인 N개의 조각들이 입력으로 주어진다.

출력

암호 키를 한 줄에 출력한다. 단, 위의 조건을 만족하는 암호 키가 존재하지 않는다면 “INVALID”를 출력한다.

예제 입력

5
2 4 11 33 00

예제 출력

11002334

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Seoul 2004 D번

  • 잘못된 데이터를 찾은 사람: ntopia