시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 227 50 15 14.286%

문제

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

예제 입력 1

5
2 4 11 33 00

예제 출력 1

11002334
W3sicHJvYmxlbV9pZCI6IjIzODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJTZWNyZXQgU2hhcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzdjXHViYzE4XHVjODAxXHVjNzNjXHViODVjLCBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggJm5ic3A7XHVjNTU0XHVkNjM4XHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1YjJlOCBcdWQ1NThcdWIwOThcdWI5Y2NcdWM3NTggXHVjNTU0XHVkNjM4IFx1ZDBhNFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNTU0XHVkNjM4XHVkNjU0IFx1ZDMwY1x1Yzc3Y1x1Yzc0NCBcdWQ1NzRcdWIzYzVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjZjVcdWFjYTlcdWM3OTBcdWFjMDAgXHVkNTc0XHVkMGI5XHVjNzNjXHViODVjIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHVjZGU4XHViNGRkXHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzBkMCBcdWM3MDRcdWQ1ZDhcdWM3NzQgXHVjNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNzc0XHViOTdjIFx1YjljOVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhY2UwXHVjNTQ4XHViNDFjIFx1YWM4M1x1Yzc3NCAmbGRxdW87U2VjcmV0IHNoYXJpbmcmcmRxdW87XHVjNzc0XHViNzgwIFx1YWUzMFx1YzIyMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JmxkcXVvO1NlY3JldCBTaGFyaW5nJmxkcXVvO1x1Yzc0MCBcdWM1NTRcdWQ2MzggXHVkMGE0XHViOTdjIFx1YWRmOFx1YjhmOVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNWVjXHViN2VjIFx1YzBhY1x1Yjc4Y1x1YzVkMFx1YWM4YyBcdWQwYTRcdWI5N2MgXHViMDk4XHViMjIwXHVjMTFjIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzRcdWIyZTQuJnJkcXVvO1NlY3JldCBzaGFyaW5nJmxkcXVvOyBcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNTU0XHVkNjM4IFx1ZDBhNFx1Yjk3YyBOXHVhYzFjXHVjNzU4IFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWQ1NThcdWFjZTAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Yzg3MFx1YWMwMVx1YjRlNFx1Yzc0MCBzaGFyZVx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViYWE4XHViNGUwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM1YmJcdWM5YzAgXHViYWJiXHVkNTU4XHViYTc0IFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHViY2Y1XHVjNmQwXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuICZuYnNwO1x1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgJiMzOTtwYXNzd29yZCYjMzk7XHViNzgwIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgNFx1YWMxY1x1Yzc1OCBzaGFyZVx1YjRlNChwYSwgc3MsIHdvLCByZClcdWI4NWMgXHViMDk4XHViMjBjIFx1YjU0YywgXHViYWE4XHViNGUwIHNoYXJlXHViNGU0XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzU3Y1x1YjljYyAmbHNxdW87cGFzc3dvcmQmcnNxdW87XHViNzgwIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHViY2Y1XHVjNmQwXHVkNTc0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzU1NFx1ZDYzOFx1Yjk3YyBcdWJjZjVcdWM2ZDBcdWQ1NjAgXHViNTRjXHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBzaGFyZVx1YmZkMCBcdWM1NDRcdWIyYzhcdWI3N2Mgc2hhcmVcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzU0Y1x1YzU0NFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMyMWNcdWMxMWNcdWI5N2MgXHViYWE4XHViOTc4XHViMmU0XHViYTc0ICZsc3F1bzt3b3NzcGFyZCYjMzk7IFx1YjA5OCAmcnNxdW87cGF3b3Jkc3MmIzM5OyBcdWFjMTlcdWM3NDAgXHVjNzk4XHViYWJiXHViNDFjIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHViY2Y1XHVjNmQwIFx1ZDU3NFx1YjBiYyBcdWMyMThcdWIzYzQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVhZGZjLCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNTU0XHVkNjM4IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YzVkMFx1YzExY1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVhZTM0IDEwXHVjOWM0XHVjMjE4XHViOTdjIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI4NWMgXHVjNGY0XHViMmU0LiBcdWM1NTRcdWQ2MzggXHVkMGE0XHViMjk0IDBcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWMyZGNcdWM3OTEgXHViNDE4XHViYTcwLCBcdWFkZjggXHVjNTU0XHVkNjM4IFx1ZDBhNFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IHNoYXJlXHViNGU0XHViODVjIFx1YmQ4NFx1ZDU2MFx1YjQxY1x1YjJlNC4gXHVjNzc0IHNoYXJlXHViNGU0XHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVhYzA0XHViMmU4XHVkNTVjIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBzaGFyZVx1Yjk3YyBcdWMzNjhcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDBhNFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWMxMlx1Yzc3NCBcdWM1NTRcdWQ2MzggXHVkMGE0XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgMiwgNCwgMTEsIDMzLCAwMCBcdWM3NzRcdWI3N2NcdWIyOTQgNVx1YWMxY1x1Yzc1OCBzaGFyZVx1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVjNTU0XHVkNjM4IFx1ZDBhNFx1YjI5NCAxMTAwMjMzNCBcdWFjMDAgXHViNDFjXHViMmU0LiAoMDAxMTIzMzQgXHViMjk0IDBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1NTRcdWQ2MzggXHVkMGE0XHVhYzAwIFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0KS48XC9wPlxyXG5cclxuPHA+Tlx1YWMxY1x1Yzc1OCBzaGFyZVx1YjRlNFx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM1NTRcdWQ2MzggXHVkMGE0XHViOTdjIFx1YmNmNVx1YzZkMFx1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjIFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IHNoYXJlXHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEmbGU7TiZsZTsxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCA1XHVjNzkwXHViOWFjIFx1Yzc3NFx1ZDU1OFx1Yzc3OCBOXHVhYzFjXHVjNzU4IFx1Yzg3MFx1YWMwMVx1YjRlNFx1Yzc3NCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjNTU0XHVkNjM4IFx1ZDBhNFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0ICZsZHF1bztJTlZBTElEJnJkcXVvO1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuXHVmZWZmPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjM4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlY3JldCBTaGFyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBnZW5lcmFsLCBtYW55IGNyeXB0b3N5c3RlbXMgdXNlIG9uZSBzZWNyZXQga2V5IHRvIGFjY2VzcyBlbmNyeXB0ZWQgZmlsZXMuIElmIGFuIGF0dGFja2VyIGhhY2tzIGluIGFuZCBzdGVhbHMgdGhlIHNlY3JldCBrZXksIHRoZSBpbmZvcm1hdGlvbiBjYW4gYmUgbGVha2VkIG91dC4gU2VjcmV0IHNoYXJpbmcgaXMgYSB0ZWNobmlxdWUgdG8gZGlzdHJpYnV0ZSBhIHNlY3JldCBrZXkgYW1vbmcgYSBncm91cCBvZiBwYXJ0aWNpcGFudHMuIEEgc2VjcmV0IHNoYXJpbmcgc2NoZW1lIGRpdmlkZXMgYSBzZWNyZXQga2V5IGludG8gTiBwaWVjZXMsIHdoaWNoIGFyZSBjYWxsZWQgc2hhcmVzLiBBbnlvbmUgd2l0aCBmZXdlciB0aGFuIE4gc2hhcmVzIGNhbm5vdCByZWdlbmVyYXRlIHRoZSBzZWNyZXQga2V5IGFuZCBhY2Nlc3MgdGhlIHNlY3JldCBpbmZvcm1hdGlvbi4gRm9yIGV4YW1wbGUsIGNvbnNpZGVyIHRoZSBzZWNyZXQga2V5IHBhc3N3b3JkIGlzIGRpdmlkZWQgaW50byBmb3VyIHNoYXJlcyBwYSwgc3MsIHdvLCBhbmQgcmQuIEFsbCBvZiB3aGljaCBhcmUgcmVxdWlyZWQgdG8gcmVjb3ZlciB0aGUgb3JpZ2luYWwgc2VjcmV0IGtleS4gSG93ZXZlciB0byByZWNvdmVyIHRoZSBrZXksIHlvdSBuZWVkIG5vdCBvbmx5IHRoZSBzaGFyZXMgYnV0IGFsc28gdGhlIG9yZGVyIG9mIHNoYXJlcy4gSWYgdGhlIG9yZGVyIGlzIG5vdCBhY3F1aXJlZCwgeW91IGNvdWxkIHByb2R1Y2UgYSB3cm9uZyBrZXksIHN1Y2ggYXMgd29zc3BhcmQgb3IgcGF3b3Jkc3MuPFwvcD5cclxuXHJcbjxwPlJlY2VudGx5LCBhIG5ldyBjcnlwdG9ncmFwaGljIGFsZ29yaXRobSwgd2hpY2ggdXNlcyBhIHNlY3JldCBzaGFyaW5nIHRlY2huaXF1ZSB0byBnZW5lcmF0ZSBhIHNlY3JldCBrZXksIGlzIGRldmVsb3BlZCBpbiB5b3VyIHJlc2VhcmNoIGdyb3VwLiBUaGUgYWxnb3JpdGhtIHVzZXMgYSB2ZXJ5IGxvbmcgZGVjaW1hbCBudW1iZXIgYXMgYSBzZWNyZXQga2V5LiBUaGUga2V5IHN0YXJ0cyB3aXRoIGEgbm9uLXplcm8gZGlnaXQuIFRoZSBrZXkgaXMgZGl2aWRlZCBpbnRvIG11bHRpcGxlIHNoYXJlcy4gVG8gc2V0dGxlIHRoZSBvcmRlcmluZyBwcm9ibGVtIGZyb20gdGhlIHNoYXJlcywgYSBzaW1wbGUgcnVsZSBpcyBhZG9wdGVkOyB0aGUgc2VjcmV0IGtleSBpcyB0aGUgc21hbGxlc3QgbnVtYmVyIHRoYXQgY2FuIGJlIG9idGFpbmVkIGZyb20gdGhlIHNoYXJlcy4gRm9yIGluc3RhbmNlLCBzdXBwb3NlIHRoYXQgYSBzZWNyZXQga2V5IGlzIGRpdmlkZWQgaW50byBmaXZlIHNoYXJlcyAyLCA0LCAxMSwgMzMsIGFuZCAwMC4gMjQxMTMzMDAgYW5kIDExMjMzNDAwIGFyZSBub3QgdGhlIHNtYWxsZXN0IG51bWJlcnMuIDAwMTEyMzM0IGlzIGludmFsaWQgc2luY2UgdGhlIHNlY3JldCBrZXkgY2FuIG5vdCBzdGFydCB3aXRoIDAuIFRoZSBzYXRpc2Z5aW5nIGtleSBpcyAxMTAwMjMzNC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgdGhlIHNlY3JldCBrZXkgZnJvbSB0aGUgc2hhcmVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgTiwgdGhlIG51bWJlciBvZiBzaGFyZXMsIDEgJmxlOyBOICZsZTsgNTAuIE9uIG5leHQgbGluZSwgTiBzaGFyZXMgYXJlIGdpdmVuLCB3aGVyZSBlYWNoIHNoYXJlIGNvbnNpc3RzIG9mIGF0IG1vc3QgNSBkaWdpdHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIEZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgYSBzZWNyZXQga2V5LiBJZiB5b3UgY2FuIG5vdCBmaW5kIGEga2V5IHRoYXQgc2F0aXNmaWVzIHRoZSBjb25kaXRpb24sIHByaW50IElOVkFMSUQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 문제의 오타를 찾은 사람: bachjs
  • 잘못된 데이터를 찾은 사람: ntopia