시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB5951366318.314%

문제

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

예제 입력 2

3
20 202 2020

예제 출력 2

202020202

예제 입력 3

6
3 4 5 3 44 555

예제 출력 3

334445555

예제 입력 4

3
0 00 007

예제 출력 4

INVALID
W3sicHJvYmxlbV9pZCI6IjIzODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJTZWNyZXQgU2hhcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzdjXHViYzE4XHVjODAxXHVjNzNjXHViODVjLCBcdWIzMDBcdWJkODBcdWJkODRcdWM3NTggJm5ic3A7XHVjNTU0XHVkNjM4XHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1YjJlOCBcdWQ1NThcdWIwOThcdWI5Y2NcdWM3NTggXHVjNTU0XHVkNjM4IFx1ZDBhNFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNTU0XHVkNjM4XHVkNjU0IFx1ZDMwY1x1Yzc3Y1x1Yzc0NCBcdWQ1NzRcdWIzYzVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjZjVcdWFjYTlcdWM3OTBcdWFjMDAgXHVkNTc0XHVkMGI5XHVjNzNjXHViODVjIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHVjZGU4XHViNGRkXHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHVjODE1XHViY2Y0XHVhYzAwIFx1YzBkMCBcdWM3MDRcdWQ1ZDhcdWM3NzQgXHVjNzg4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNzc0XHViOTdjIFx1YjljOVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhY2UwXHVjNTQ4XHViNDFjIFx1YWM4M1x1Yzc3NCAmbGRxdW87U2VjcmV0IHNoYXJpbmcmcmRxdW87XHVjNzc0XHViNzgwIFx1YWUzMFx1YzIyMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JmxkcXVvO1NlY3JldCBTaGFyaW5nJmxkcXVvO1x1Yzc0MCBcdWM1NTRcdWQ2MzggXHVkMGE0XHViOTdjIFx1YWRmOFx1YjhmOVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjNWVjXHViN2VjIFx1YzBhY1x1Yjc4Y1x1YzVkMFx1YWM4YyBcdWQwYTRcdWI5N2MgXHViMDk4XHViMjIwXHVjMTFjIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzRcdWIyZTQuJnJkcXVvO1NlY3JldCBzaGFyaW5nJmxkcXVvOyBcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjNTU0XHVkNjM4IFx1ZDBhNFx1Yjk3YyBOXHVhYzFjXHVjNzU4IFx1Yzg3MFx1YWMwMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWQ1NThcdWFjZTAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1Yzg3MFx1YWMwMVx1YjRlNFx1Yzc0MCBzaGFyZVx1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjMWNcdWM3NTggXHViYWE4XHViNGUwIFx1Yzg3MFx1YWMwMVx1Yzc0NCBcdWM1YmJcdWM5YzAgXHViYWJiXHVkNTU4XHViYTc0IFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHViY2Y1XHVjNmQwXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuICZuYnNwO1x1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgJiMzOTtwYXNzd29yZCYjMzk7XHViNzgwIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgNFx1YWMxY1x1Yzc1OCBzaGFyZVx1YjRlNChwYSwgc3MsIHdvLCByZClcdWI4NWMgXHViMDk4XHViMjBjIFx1YjU0YywgXHViYWE4XHViNGUwIHNoYXJlXHViNGU0XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzU3Y1x1YjljYyAmbHNxdW87cGFzc3dvcmQmcnNxdW87XHViNzgwIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHViY2Y1XHVjNmQwXHVkNTc0IFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzU1NFx1ZDYzOFx1Yjk3YyBcdWJjZjVcdWM2ZDBcdWQ1NjAgXHViNTRjXHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBzaGFyZVx1YmZkMCBcdWM1NDRcdWIyYzhcdWI3N2Mgc2hhcmVcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzU0Y1x1YzU0NFx1YzU3Y1x1YjljYyBcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWMyMWNcdWMxMWNcdWI5N2MgXHViYWE4XHViOTc4XHViMmU0XHViYTc0ICZsc3F1bzt3b3NzcGFyZCYjMzk7IFx1YjA5OCAmcnNxdW87cGF3b3Jkc3MmIzM5OyBcdWFjMTlcdWM3NDAgXHVjNzk4XHViYWJiXHViNDFjIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI5N2MgXHViY2Y1XHVjNmQwIFx1ZDU3NFx1YjBiYyBcdWMyMThcdWIzYzQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHVhZGZjLCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjNTU0XHVkNjM4IFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YzVkMFx1YzExY1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVhZTM0IDEwXHVjOWM0XHVjMjE4XHViOTdjIFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWI4NWMgXHVjNGY0XHViMmU0LiBcdWM1NTRcdWQ2MzggXHVkMGE0XHViMjk0IDBcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWMyZGNcdWM3OTEgXHViNDE4XHViYTcwLCBcdWFkZjggXHVjNTU0XHVkNjM4IFx1ZDBhNFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IHNoYXJlXHViNGU0XHViODVjIFx1YmQ4NFx1ZDU2MFx1YjQxY1x1YjJlNC4gXHVjNzc0IHNoYXJlXHViNGU0XHVjNzU4IFx1YzIxY1x1YzExY1x1YjI5NCBcdWI5ZTRcdWM2YjAgXHVhYzA0XHViMmU4XHVkNTVjIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWI0MThcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YmFhOFx1YjRlMCBzaGFyZVx1Yjk3YyBcdWMzNjhcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1ZDBhNFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWMxMlx1Yzc3NCBcdWM1NTRcdWQ2MzggXHVkMGE0XHVhYzAwIFx1YjQxOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQgMiwgNCwgMTEsIDMzLCAwMCBcdWM3NzRcdWI3N2NcdWIyOTQgNVx1YWMxY1x1Yzc1OCBzaGFyZVx1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVjNTU0XHVkNjM4IFx1ZDBhNFx1YjI5NCAxMTAwMjMzNCBcdWFjMDAgXHViNDFjXHViMmU0LiAoMDAxMTIzMzQgXHViMjk0IDBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1NTRcdWQ2MzggXHVkMGE0XHVhYzAwIFx1YjQyMCBcdWMyMTggXHVjNWM2XHViMmU0KS48XC9wPlxyXG5cclxuPHA+Tlx1YWMxY1x1Yzc1OCBzaGFyZVx1YjRlNFx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM1NTRcdWQ2MzggXHVkMGE0XHViOTdjIFx1YmNmNVx1YzZkMFx1ZDU3NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjIFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IHNoYXJlXHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgNVx1Yzc5MFx1YjlhYyBcdWM3NzRcdWQ1NThcdWM3NzggTlx1YWMxY1x1Yzc1OCBcdWM4NzBcdWFjMDFcdWI0ZTRcdWM3NzQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM1NTRcdWQ2MzggXHVkMGE0XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTgsIFx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YzU1NFx1ZDYzOCBcdWQwYTRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCAmbGRxdW87SU5WQUxJRCZyZHF1bztcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0Llx1ZmVmZjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjIzODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZWNyZXQgU2hhcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gZ2VuZXJhbCwgbWFueSBjcnlwdG9zeXN0ZW1zIHVzZSBvbmUgc2VjcmV0IGtleSB0byBhY2Nlc3MgZW5jcnlwdGVkIGZpbGVzLiBJZiBhbiBhdHRhY2tlciBoYWNrcyBpbiBhbmQgc3RlYWxzIHRoZSBzZWNyZXQga2V5LCB0aGUgaW5mb3JtYXRpb24gY2FuIGJlIGxlYWtlZCBvdXQuIFNlY3JldCBzaGFyaW5nIGlzIGEgdGVjaG5pcXVlIHRvIGRpc3RyaWJ1dGUgYSBzZWNyZXQga2V5IGFtb25nIGEgZ3JvdXAgb2YgcGFydGljaXBhbnRzLiBBIHNlY3JldCBzaGFyaW5nIHNjaGVtZSBkaXZpZGVzIGEgc2VjcmV0IGtleSBpbnRvIE4gcGllY2VzLCB3aGljaCBhcmUgY2FsbGVkIHNoYXJlcy4gQW55b25lIHdpdGggZmV3ZXIgdGhhbiBOIHNoYXJlcyBjYW5ub3QgcmVnZW5lcmF0ZSB0aGUgc2VjcmV0IGtleSBhbmQgYWNjZXNzIHRoZSBzZWNyZXQgaW5mb3JtYXRpb24uIEZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgc2VjcmV0IGtleSBwYXNzd29yZCBpcyBkaXZpZGVkIGludG8gZm91ciBzaGFyZXMgcGEsIHNzLCB3bywgYW5kIHJkLiBBbGwgb2Ygd2hpY2ggYXJlIHJlcXVpcmVkIHRvIHJlY292ZXIgdGhlIG9yaWdpbmFsIHNlY3JldCBrZXkuIEhvd2V2ZXIgdG8gcmVjb3ZlciB0aGUga2V5LCB5b3UgbmVlZCBub3Qgb25seSB0aGUgc2hhcmVzIGJ1dCBhbHNvIHRoZSBvcmRlciBvZiBzaGFyZXMuIElmIHRoZSBvcmRlciBpcyBub3QgYWNxdWlyZWQsIHlvdSBjb3VsZCBwcm9kdWNlIGEgd3Jvbmcga2V5LCBzdWNoIGFzIHdvc3NwYXJkIG9yIHBhd29yZHNzLjxcL3A+XHJcblxyXG48cD5SZWNlbnRseSwgYSBuZXcgY3J5cHRvZ3JhcGhpYyBhbGdvcml0aG0sIHdoaWNoIHVzZXMgYSBzZWNyZXQgc2hhcmluZyB0ZWNobmlxdWUgdG8gZ2VuZXJhdGUgYSBzZWNyZXQga2V5LCBpcyBkZXZlbG9wZWQgaW4geW91ciByZXNlYXJjaCBncm91cC4gVGhlIGFsZ29yaXRobSB1c2VzIGEgdmVyeSBsb25nIGRlY2ltYWwgbnVtYmVyIGFzIGEgc2VjcmV0IGtleS4gVGhlIGtleSBzdGFydHMgd2l0aCBhIG5vbi16ZXJvIGRpZ2l0LiBUaGUga2V5IGlzIGRpdmlkZWQgaW50byBtdWx0aXBsZSBzaGFyZXMuIFRvIHNldHRsZSB0aGUgb3JkZXJpbmcgcHJvYmxlbSBmcm9tIHRoZSBzaGFyZXMsIGEgc2ltcGxlIHJ1bGUgaXMgYWRvcHRlZDsgdGhlIHNlY3JldCBrZXkgaXMgdGhlIHNtYWxsZXN0IG51bWJlciB0aGF0IGNhbiBiZSBvYnRhaW5lZCBmcm9tIHRoZSBzaGFyZXMuIEZvciBpbnN0YW5jZSwgc3VwcG9zZSB0aGF0IGEgc2VjcmV0IGtleSBpcyBkaXZpZGVkIGludG8gZml2ZSBzaGFyZXMgMiwgNCwgMTEsIDMzLCBhbmQgMDAuIDI0MTEzMzAwIGFuZCAxMTIzMzQwMCBhcmUgbm90IHRoZSBzbWFsbGVzdCBudW1iZXJzLiAwMDExMjMzNCBpcyBpbnZhbGlkIHNpbmNlIHRoZSBzZWNyZXQga2V5IGNhbiBub3Qgc3RhcnQgd2l0aCAwLiBUaGUgc2F0aXNmeWluZyBrZXkgaXMgMTEwMDIzMzQuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBzZWNyZXQga2V5IGZyb20gdGhlIHNoYXJlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBmaWxlLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2Ygc2hhcmVzLCAxICZsZTsgTiAmbGU7IDUwLiBPbiBuZXh0IGxpbmUsIE4gc2hhcmVzIGFyZSBnaXZlbiwgd2hlcmUgZWFjaCBzaGFyZSBjb25zaXN0cyBvZiBhdCBtb3N0IDUgZGlnaXRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBGb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgc2VjcmV0IGtleS4gSWYgeW91IGNhbiBub3QgZmluZCBhIGtleSB0aGF0IHNhdGlzZmllcyB0aGUgY29uZGl0aW9uLCBwcmludCBJTlZBTElELjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

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