시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHViNjEwXHVkNTVjIFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4XHViMjk0IFx1YWMxOVx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWZjZFx1Yzc0MCBOZXN0ZWQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3M2NcdWJhNzAsIFx1YjllOCBcdWM1NWVcdWM1ZDAgMFx1Yzc3NCBcdWM2MjRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjLCBcdWJhODdcdWJhODcgXHVjMjJiXHVjNzkwXHViOTdjICZxdW90Oz8mcXVvdDtcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWM4XHViMmU0LiZuYnNwO1x1YWZjZFx1Yzc0MCZuYnNwOz9cdWI5N2MgXHVjMjJiXHVjNzkwXHViODVjIFx1YmMxNFx1YWZkNFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCZuYnNwO1x1YmFhOFx1YjRlMCBOZXN0ZWQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1YzkxMVx1YzVkMFx1YzExYyBrXHViYzg4XHVjOWY4IFx1ZDA3MCBcdWMyMThcdWI5N2MgXHVjYzNlXHVjNzNjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZmNkXHVjNzc0IFx1YzRmNCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjYzk4XHVjNzRjXHViZDgwXHVkMTMwIE5lc3RlZCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHVjNTQ0XHViMmQwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4Jm5ic3A7XHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCZuYnNwO2soMSZsZTtrJmxlOzEwPHN1cD4xODxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MjRcdWM5YzEgMH45XHVjNjQwICZxdW90Oz8mcXVvdDtcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWUzOFx1Yzc3NFx1YWMwMCAxfjEwMDAwXHVjNzc4IFx1YmJmOFx1YzljMFx1Yzc1OCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVjNzQwIDAgXHVkNTU4XHViMDk4XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzAxIFx1YzkwNFx1YzVkMCZuYnNwO1x1YWZjZFx1Yzc3NCBcdWNjM2VcdWFjZTBcdWM3ODhcdWIyOTQgTmVzdGVkIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YzVjNlx1YWM3MFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYmY4XHVjOWMwXHVjNzU4IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NCBOZXN0ZWQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YWNiZFx1YzZiMCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTQ3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik5lc3RlZCBQYWxpbmRyb21lcyIsImRlc2NyaXB0aW9uIjoiPHA+UGFsaW5kcm9tZXMgYXJlIG51bWJlcnMgdGhhdCByZWFkIHRoZSBzYW1lIGZvcndhcmRzIGFuZCBiYWNrd2FyZHMuIFlvdXIgZnJpZW5kIFBlcmN5IHJlY2VudGx5IGJlY2FtZSBpbnRlcmVzdGVkIGluIGEgc3BlY2lhbCBraW5kIG9mIHBhbGluZHJvbWUgdGhhdCBoZSBjYWxscyBhIE5lc3RlZCBQYWxpbmRyb21lLiBBIE5lc3RlZCBQYWxpbmRyb21lIG1lZXRzIHRocmVlIGNvbmRpdGlvbnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIG51bWJlciBpcyBhIHBhbGluZHJvbWUuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlNwbGl0IHRoZSBudW1iZXIgaW4gdGhlIG1pZGRsZS4gVGhlIGZpcnN0IGhhbGYgb2YgdGhlIGRpZ2l0cyBvZiB0aGUgbnVtYmVyIGlzIGFsc28gYSBOZXN0ZWQgUGFsaW5kcm9tZS4gSWYgdGhlIG51bWJlciBoYXMgYW4gb2RkIG51bWJlciBvZiBkaWdpdHMsIGRvbiZyc3F1bzt0IGNvbnNpZGVyIHRoZSBtaWRkbGUgZGlnaXQgYXMgcGFydCBvZiB0aGUgZmlyc3QgaGFsZi48XC9saT5cclxuXHQ8bGk+Tm8gdHdvIGFkamFjZW50IGRpZ2l0cyBhcmUgdGhlIHNhbWUuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+UGVyY3kgc2F5cyB0aGF0IGhlIGhhcyB3cml0dGVuIGEgTmVzdGVkIFBhbGluZHJvbWUgd2l0aCBubyBsZWFkaW5nIHplcm9zIG9uIGEgc2xpcCBvZiBwYXBlci4gTmV4dCwgUGVyY3kgc2F5cyB0aGF0IGhlIGhhcyBlcmFzZWQgc29tZSBvZiB0aGUgZGlnaXRzIGluIHRoZSBudW1iZXIgYW5kIHJlcGxhY2VkIHRob3NlIGRpZ2l0cyB3aXRoIHF1ZXN0aW9uIG1hcmtzLiBIZSBhc2tzIHlvdSB0byB0aGluayBhYm91dCBhbGwgcG9zc2libGUgbnVtYmVycywgaW4gaW5jcmVhc2luZyBvcmRlciwgdGhhdCBjYW4gZmlsbCB0aG9zZSBkaWdpdHMgYW5kIGNvdWxkIHBvc3NpYmx5IGZvcm0gdGhlIG51bWJlciBQZXJjeSB3cm90ZS4gT2YgY291cnNlLCBQZXJjeSBtYXkgbm90IGJlIHRlbGxpbmcgdGhlIHRydXRoIGFib3V0IGhhdmluZyB3cml0dGVuIGEgTmVzdGVkIFBhbGluZHJvbWUgaW4gdGhlIGZpcnN0IHBsYWNlLjxcL3A+XHJcblxyXG48cD5QZXJjeSB0ZWxscyB5b3UgdGhhdCB0aGUgbnVtYmVyIGhlIHdyb3RlIGlzIHRoZSBrdGggbnVtYmVyIG9mIHRoaXMgcG90ZW50aWFsbHkgbGFyZ2UgbGlzdC4gWW91ciB0YXNrIGlzIHRvIGZpbmQgdGhhdCBrdGggbnVtYmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGNvbnNpc3Qgb2YgdHdvIGxpbmVzLiBUaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gYW4gaW50ZWdlciBrICgxJmxlO2smbGU7MTAxOCksIHdoaWNoIGlzIHRoZSBwb3NpdGlvbiBpbiB0aGUgb3JkZXJlZCBsaXN0IHlvdSBtdXN0IGZpbmQuIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHN0cmluZyBvZiBsZW5ndGggMSB0byAxMCwwMDAsIGNvbnNpc3Rpbmcgb25seSBvZiBkaWdpdHMgKCZsc3F1bzswJnJzcXVvOyB0byAmbHNxdW87OSZyc3F1bzspIGFuZCBxdWVzdGlvbiBtYXJrcyAoJmxzcXVvOz8mcnNxdW87KS4gSW5wdXQgaXMgdGVybWluYXRlZCBieSBhIGxpbmUgd2l0aCBhIHNpbmdsZSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBOZXN0ZWQgUGFsaW5kcm9tZSB0aGF0IFBlcmN5IGlzIGxvb2tpbmcgZm9yLiBJZiB0aGF0IG51bWJlciBkb2VzIG5vdCBleGlzdCwgb3IgaWYgdGhlIHN0cmluZyBjYW5ub3QgZm9ybSBhIE5lc3RlZCBQYWxpbmRyb21lLCBvdXRwdXQgLTEuIE91dHB1dCBubyBzcGFjZXMsIGFuZCBkbyBub3Qgc2VwYXJhdGUgYW5zd2VycyB3aXRoIGJsYW5rIGxpbmVzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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