시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB22817213178.443%

문제

R이 주어졌을 때, 마지막 R자리가 1과 2로만 이루어진 가장 작은 2k를 구하는 프로그램을 작성하시오.

예를 들어, 29 = 512이고, 289 = 618970019642690137449562112 이다. 29는 마지막 2자리가 1과 2로 이루어져 있고, 289는 마지막 4자리가 1과 2로만 이루어져 있다.

R이 6일때까지 답을 구해보면 다음과 같다.

R 가장 작은 k 2k
1 1 2
2 9 512
3 89 ...112
4 89 ...2112
5 589 ...22112
6 3089 ...122112

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다. 각 테스트 케이스는 정수 1개로 이루어져 있고, 이 수는 R(1 ≤ R ≤ 20)이다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 마지막 R자리가 1과 2로만 이루어진 가장 2k의 k를 출력한다.

예제 입력 1

6
1
2
4
5
7
15

예제 출력 1

1
9
89
589
3089
11687815589
W3sicHJvYmxlbV9pZCI6IjI3MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIEsiLCJkZXNjcmlwdGlvbiI6IjxwPlJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOWM4XHVjOWMwXHViOWM5IFJcdWM3OTBcdWI5YWNcdWFjMDAgMVx1YWNmYyAyXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIDI8c3VwPms8XC9zdXA+XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyPHN1cD45PFwvc3VwPiA9IDUxMlx1Yzc3NFx1YWNlMCwgMjxzdXA+ODk8XC9zdXA+ID0gNjE4OTcwMDE5NjQyNjkwMTM3NDQ5NTYyMTEyIFx1Yzc3NFx1YjJlNC4gMjxzdXA+OTxcL3N1cD5cdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5IDJcdWM3OTBcdWI5YWNcdWFjMDAgMVx1YWNmYyAyXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIDI8c3VwPjg5PFwvc3VwPlx1YjI5NCBcdWI5YzhcdWM5YzBcdWI5YzkgNFx1Yzc5MFx1YjlhY1x1YWMwMCAxXHVhY2ZjIDJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Ulx1Yzc3NCA2XHVjNzdjXHViNTRjXHVhZTRjXHVjOWMwIFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjMwJTtcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEwJTtcIj5SPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZT1cIndpZHRoOjEwJTtcIj5cdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIGs8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MTAlO1wiPjI8c3VwPms8XC9zdXA+PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4xPFwvdGQ+XHJcblx0XHRcdDx0ZD4yPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjI8XC90ZD5cclxuXHRcdFx0PHRkPjk8XC90ZD5cclxuXHRcdFx0PHRkPjUxMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4zPFwvdGQ+XHJcblx0XHRcdDx0ZD44OTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Li4uMTEyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjQ8XC90ZD5cclxuXHRcdFx0PHRkPjg5PFwvdGQ+XHJcblx0XHRcdDx0ZD4uLi4yMTEyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjU8XC90ZD5cclxuXHRcdFx0PHRkPjU4OTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Li4uMjIxMTI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+NjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MzA4OTxcL3RkPlxyXG5cdFx0XHQ8dGQ+Li4uMTIyMTEyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmxlOyBUICZsZTsgNTApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjODE1XHVjMjE4IDFcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzIxOFx1YjI5NCBSKDEgJmxlOyBSICZsZTsgMjApXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWI5YzhcdWM5YzBcdWI5YzkgUlx1Yzc5MFx1YjlhY1x1YWMwMCAxXHVhY2ZjIDJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWMwMFx1YzdhNSAyPHN1cD5rPFwvc3VwPlx1Yzc1OCBrXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNzA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFR3byBOb3RlIFJhZyIsImRlc2NyaXB0aW9uIjoiPHA+U2luY2UgbW9zdCBjb21wdXRlcnMgYXJlIGJpbmFyeSBtYWNoaW5lcywgYm90aCBwb3dlcnMgb2YgdHdvIGFuZCBwcm9ibGVtcyB0aGF0IGludm9sdmUgb25seSB0d28gdmFsdWVzIGFyZSBpbXBvcnRhbnQgdG8gY29tcHV0ZXIgc2NpZW50aXN0cy4gVGhlIGZvbGxvd2luZyBwcm9ibGVtIGhhcyB0byBkbyB3aXRoIHBvd2VycyBvZiB0d28gYW5kIHRoZSBkaWdpdHMgMSBhbmQgMi48XC9wPlxyXG5cclxuPHA+U29tZSBwb3dlcnMgb2YgdHdvIGFzIGRlY2ltYWwgdmFsdWVzLCBzdWNoIGFzIDI8c3VwPjk8XC9zdXA+ID0gNTEyIGFuZCAyPHN1cD44OTxcL3N1cD4gPSA2MTgsOTcwLDAxOSw2NDIsNjkwLDEzNyw0NDksNTYyLDExMiBlbmQgaW4gYSBzdHJpbmcgb2YgZGlnaXRzIGNvbnNpc3Rpbmcgb25seSBvZiAxJiMzOTtzIGFuZCAyJiMzOTtzICgxMiBmb3IgMjxzdXA+OTxcL3N1cD4gYW5kIDIxMTIgZm9yIDI8c3VwPjg5PFwvc3VwPikuIEluIGZhY3QsIGl0IGNhbiBiZSBwcm92ZWQgdGhhdDo8XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+XHJcbjxwPkZvciBldmVyeSBpbnRlZ2VyIFIsIHRoZXJlIGV4aXN0cyBhIHBvd2VyIG9mIDIgc3VjaCB0aGF0IDI8c3VwPks8XC9zdXA+IHVzZXMgb25seSB0aGUgZGlnaXRzIDEgYW5kIDIgaW4gaXRzIGxhc3QgUiBkaWdpdHMuPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlRoaXMgaXMgc2hvd24gYSBiaXQgbW9yZSBjbGVhcmx5IGluIHRoZSBmb2xsb3dpbmcgdGFibGU6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHdvcmFnLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MXB4OyB3aWR0aDoyOTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3VyIGpvYiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGRldGVybWluZSwgZm9yIGdpdmVuIFIsIHRoZSBzbWFsbGVzdCBLIHN1Y2ggdGhhdCAyPHN1cD5LPFwvc3VwPiBlbmRzIGluIGEgc3RyaW5nIG9mIFIgZGlnaXRzIGNvbnRhaW5pbmcgb25seSAxJiMzOTtzIGFuZCAyJiMzOTtzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGRlY2ltYWwgaW50ZWdlciwgTiwgMSAmcG91bmQ7IE4gJnBvdW5kOyA1MCwgdGhlIG51bWJlciBvZiBwcm9ibGVtIGRhdGEgc2V0cyB0byBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgaW50ZWdlciBSLCAxICZwb3VuZDsgUiAmcG91bmQ7IDIwLCBmb3Igd2hpY2ggd2Ugd2FudCBhIHBvd2VyIG9mIDIgZW5kaW5nIGluIGEgc3RyaW5nIG9mIFIgMSYjMzk7cyBhbmQgMiYjMzk7cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgeW91IHNob3VsZCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlczogVGhlIGRhdGEgc2V0IG51bWJlciBhcyBhIGRlY2ltYWwgaW50ZWdlciAoc3RhcnQgY291bnRpbmcgYXQgb25lKSwgYSBzcGFjZSwgdGhlIGlucHV0IHZhbHVlIFIsIGFub3RoZXIgc3BhY2UsIGFuZCB0aGUgc21hbGxlc3QgdmFsdWUgSyBmb3Igd2hpY2ggMjxzdXA+SzxcL3N1cD4gZW5kcyBpbiBhIHN0cmluZyBvZiBSIDEmIzM5O3MgYW5kIDImIzM5O3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > North America > Greater New York Region > 2008 Greater New York Programming Contest H번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: zxcvber