시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 42 6 6 37.500%

문제

팰린드롬은 앞으로 읽으나 뒤로 읽으나 똑같은 숫자다. 그런데 꿍은 Nested 팰린드롬이라고 불리는 특별한 팰린드롬에 관심을 갖게 되었다. Nested 팰린드롬은 다음의 세가지 조건을 만족한다.

  • 숫자가 팰린드롬이어야 하며,
  • 숫자를 반으로 쪼갰을 때, 앞쪽의 절반 역시 Nested 팰린드롬 이어야한다. 만약 자리수가 홀수개라면, 정가운데에 있는 한 자리의 수는 무시해도 된다.
  • 또한 두개의 인접한 수는 같아서는 안 된다.

꿍은 Nested 팰린드롬을 하나 만들었으며, 맨 앞에 0이 오지 않는다. 그 다음, 몇몇 숫자를 "?"로 바꾸었다. 꿍은 ?를 숫자로 바꿔서 만들 수 있는 모든 Nested 팰린드롬 중에서 k번째 큰 수를 찾으려고 한다. 꿍이 쓴 숫자는 처음부터 Nested 팰린드롬이 아닐 수도 있다.

입력

각 테스트 케이스는 두 줄로 이루어진다. 첫번째 줄에는 k(1≤k≤1018)가 주어지며 두번째 줄에는 오직 0~9와 "?"로만 이루어진 길이가 1~10000인 미지의 팰린드롬이 주어진다. 입력의 마지막은 0 하나만 주어진다.

출력

각 테스트 케이스에 대해 각 줄에 꿍이 찾고있는 Nested 팰린드롬을 출력한다. 만약 가능한 팰린드롬이 없거나 주어진 미지의 팰린드롬이 Nested 팰린드롬이 될 수 없을 경우 -1을 출력한다. 

예제 입력 1

1
1?1
1
?3?
1
?1?
55
???
55
1?1
3
0?0
0

예제 출력 1

101
131
212
707
-1
-1
W3sicHJvYmxlbV9pZCI6Ijk0NzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOZXN0ZWQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NDAgXHVjNTVlXHVjNzNjXHViODVjIFx1Yzc3ZFx1YzczY1x1YjA5OCBcdWI0YTRcdWI4NWMgXHVjNzdkXHVjNzNjXHViMDk4IFx1YjYxMVx1YWMxOVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWFmY2RcdWM3NDAgTmVzdGVkIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWJkODhcdWI5YWNcdWIyOTQgXHVkMmI5XHViY2M0XHVkNTVjIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1YzVkMCBcdWFkMDBcdWMyZWNcdWM3NDQgXHVhYzE2XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gTmVzdGVkIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NTggXHVjMTM4XHVhYzAwXHVjOWMwIFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjMjJiXHVjNzkwXHVhYzAwJm5ic3A7XHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCw8XC9saT5cclxuXHQ8bGk+XHVjMjJiXHVjNzkwXHViOTdjIFx1YmMxOFx1YzczY1x1Yjg1YyBcdWNhYmNcdWFjMzBcdWM3NDQgXHViNTRjLCBcdWM1NWVcdWNhYmRcdWM3NTggXHVjODA4XHViYzE4IFx1YzVlZFx1YzJkYyBOZXN0ZWQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1Yzc3NFx1YzViNFx1YzU3Y1x1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Yzc5MFx1YjlhY1x1YzIxOFx1YWMwMCBcdWQ2NDBcdWMyMThcdWFjMWNcdWI3N2NcdWJhNzQsIFx1YzgxNVx1YWMwMFx1YzZiNFx1YjM3MFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkNTVjIFx1Yzc5MFx1YjlhY1x1Yzc1OCBcdWMyMThcdWIyOTQgXHViYjM0XHVjMmRjXHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNjEwXHVkNTVjIFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4XHViMjk0IFx1YWMxOVx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWZjZFx1Yzc0MCBOZXN0ZWQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3M2NcdWJhNzAsIFx1YjllOCBcdWM1NWVcdWM1ZDAgMFx1Yzc3NCBcdWM2MjRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWJhODdcdWJhODcgXHVjMjJiXHVjNzkwXHViOTdjICZxdW90Oz8mcXVvdDtcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWM4XHViMmU0LiZuYnNwO1x1YWZjZFx1Yzc0MCZuYnNwOz9cdWI5N2MgXHVjMjJiXHVjNzkwXHViODVjIFx1YmMxNFx1YWZkNFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCZuYnNwO1x1YmFhOFx1YjRlMCBOZXN0ZWQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1YzkxMVx1YzVkMFx1YzExYyBrXHViYzg4XHVjOWY4IFx1ZDA3MCBcdWMyMThcdWI5N2MgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZmNkXHVjNzc0IFx1YzRmNCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjYzk4XHVjNzRjXHViZDgwXHVkMTMwIE5lc3RlZCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHVjNTQ0XHViMmQwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4Jm5ic3A7XHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0Jm5ic3A7aygxJmxlO2smbGU7MTA8c3VwPjE4PFwvc3VwPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwIFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjI0XHVjOWMxIDB+OVx1YzY0MCAmcXVvdDs/JnF1b3Q7XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzRcdWFjMDAgMX4xMDAwMFx1Yzc3OCBcdWJiZjhcdWM5YzBcdWM3NTggXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOVx1Yzc0MCAwIFx1ZDU1OFx1YjA5OFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWMwMSBcdWM5MDRcdWM1ZDAmbmJzcDtcdWFmY2RcdWM3NzQgXHVjYzNlXHVhY2UwXHVjNzg4XHViMjk0IE5lc3RlZCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWM1YzZcdWFjNzBcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmJmOFx1YzljMFx1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgTmVzdGVkIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWFjYmRcdWM2YjAgLTFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk0NzgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOZXN0ZWQgUGFsaW5kcm9tZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlBhbGluZHJvbWVzIGFyZSBudW1iZXJzIHRoYXQgcmVhZCB0aGUgc2FtZSBmb3J3YXJkcyBhbmQgYmFja3dhcmRzLiBZb3VyIGZyaWVuZCBQZXJjeSByZWNlbnRseSBiZWNhbWUgaW50ZXJlc3RlZCBpbiBhIHNwZWNpYWwga2luZCBvZiBwYWxpbmRyb21lIHRoYXQgaGUgY2FsbHMgYSBOZXN0ZWQgUGFsaW5kcm9tZS4gQSBOZXN0ZWQgUGFsaW5kcm9tZSBtZWV0cyB0aHJlZSBjb25kaXRpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBudW1iZXIgaXMgYSBwYWxpbmRyb21lLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5TcGxpdCB0aGUgbnVtYmVyIGluIHRoZSBtaWRkbGUuIFRoZSBmaXJzdCBoYWxmIG9mIHRoZSBkaWdpdHMgb2YgdGhlIG51bWJlciBpcyBhbHNvIGEgTmVzdGVkIFBhbGluZHJvbWUuIElmIHRoZSBudW1iZXIgaGFzIGFuIG9kZCBudW1iZXIgb2YgZGlnaXRzLCBkb24mcnNxdW87dCBjb25zaWRlciB0aGUgbWlkZGxlIGRpZ2l0IGFzIHBhcnQgb2YgdGhlIGZpcnN0IGhhbGYuPFwvbGk+XHJcblx0PGxpPk5vIHR3byBhZGphY2VudCBkaWdpdHMgYXJlIHRoZSBzYW1lLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlBlcmN5IHNheXMgdGhhdCBoZSBoYXMgd3JpdHRlbiBhIE5lc3RlZCBQYWxpbmRyb21lIHdpdGggbm8gbGVhZGluZyB6ZXJvcyBvbiBhIHNsaXAgb2YgcGFwZXIuIE5leHQsIFBlcmN5IHNheXMgdGhhdCBoZSBoYXMgZXJhc2VkIHNvbWUgb2YgdGhlIGRpZ2l0cyBpbiB0aGUgbnVtYmVyIGFuZCByZXBsYWNlZCB0aG9zZSBkaWdpdHMgd2l0aCBxdWVzdGlvbiBtYXJrcy4gSGUgYXNrcyB5b3UgdG8gdGhpbmsgYWJvdXQgYWxsIHBvc3NpYmxlIG51bWJlcnMsIGluIGluY3JlYXNpbmcgb3JkZXIsIHRoYXQgY2FuIGZpbGwgdGhvc2UgZGlnaXRzIGFuZCBjb3VsZCBwb3NzaWJseSBmb3JtIHRoZSBudW1iZXIgUGVyY3kgd3JvdGUuIE9mIGNvdXJzZSwgUGVyY3kgbWF5IG5vdCBiZSB0ZWxsaW5nIHRoZSB0cnV0aCBhYm91dCBoYXZpbmcgd3JpdHRlbiBhIE5lc3RlZCBQYWxpbmRyb21lIGluIHRoZSBmaXJzdCBwbGFjZS48XC9wPlxyXG5cclxuPHA+UGVyY3kgdGVsbHMgeW91IHRoYXQgdGhlIG51bWJlciBoZSB3cm90ZSBpcyB0aGUga3RoIG51bWJlciBvZiB0aGlzIHBvdGVudGlhbGx5IGxhcmdlIGxpc3QuIFlvdXIgdGFzayBpcyB0byBmaW5kIHRoYXQga3RoIG51bWJlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb25zaXN0IG9mIHR3byBsaW5lcy4gVGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIGFuIGludGVnZXIgayAoMSZsZTtrJmxlOzEwMTgpLCB3aGljaCBpcyB0aGUgcG9zaXRpb24gaW4gdGhlIG9yZGVyZWQgbGlzdCB5b3UgbXVzdCBmaW5kLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYSBzdHJpbmcgb2YgbGVuZ3RoIDEgdG8gMTAsMDAwLCBjb25zaXN0aW5nIG9ubHkgb2YgZGlnaXRzICgmbHNxdW87MCZyc3F1bzsgdG8gJmxzcXVvOzkmcnNxdW87KSBhbmQgcXVlc3Rpb24gbWFya3MgKCZsc3F1bzs/JnJzcXVvOykuIElucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSBsaW5lIHdpdGggYSBzaW5nbGUgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgTmVzdGVkIFBhbGluZHJvbWUgdGhhdCBQZXJjeSBpcyBsb29raW5nIGZvci4gSWYgdGhhdCBudW1iZXIgZG9lcyBub3QgZXhpc3QsIG9yIGlmIHRoZSBzdHJpbmcgY2Fubm90IGZvcm0gYSBOZXN0ZWQgUGFsaW5kcm9tZSwgb3V0cHV0IC0xLiBPdXRwdXQgbm8gc3BhY2VzLCBhbmQgZG8gbm90IHNlcGFyYXRlIGFuc3dlcnMgd2l0aCBibGFuayBsaW5lcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > North America > Southeast USA Regional > 2013 Southeast USA Regional Programming Contest B번

  • 문제의 오타를 찾은 사람: august14
  • 문제를 번역한 사람: seok9311