시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 16 14 87.500%

문제

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+XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUKDEgJmxlOyZuYnNwO1QgJmxlOyA1MClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4MTVcdWMyMTggMVx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IFIoMSAmbGU7IFIgJmxlOyAyMClcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YjljOFx1YzljMFx1YjljOSBSXHVjNzkwXHViOWFjXHVhYzAwJm5ic3A7MVx1YWNmYyAyXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFjMDBcdWM3YTUgMjxzdXA+azxcL3N1cD5cdWM3NTgga1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjcwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBUd28gTm90ZSBSYWciLCJkZXNjcmlwdGlvbiI6IjxwPlNpbmNlIG1vc3QgY29tcHV0ZXJzIGFyZSBiaW5hcnkgbWFjaGluZXMsIGJvdGggcG93ZXJzIG9mIHR3byBhbmQgcHJvYmxlbXMgdGhhdCBpbnZvbHZlIG9ubHkgdHdvIHZhbHVlcyBhcmUgaW1wb3J0YW50IHRvIGNvbXB1dGVyIHNjaWVudGlzdHMuIFRoZSBmb2xsb3dpbmcgcHJvYmxlbSBoYXMgdG8gZG8gd2l0aCBwb3dlcnMgb2YgdHdvIGFuZCB0aGUgZGlnaXRzIDEgYW5kIDIuPFwvcD5cclxuXHJcbjxwPlNvbWUgcG93ZXJzIG9mIHR3byBhcyBkZWNpbWFsIHZhbHVlcywgc3VjaCBhcyAyPHN1cD45PFwvc3VwPiA9IDUxMiBhbmQgMjxzdXA+ODk8XC9zdXA+ID0gNjE4LDk3MCwwMTksNjQyLDY5MCwxMzcsNDQ5LDU2MiwxMTIgZW5kIGluIGEgc3RyaW5nIG9mIGRpZ2l0cyBjb25zaXN0aW5nIG9ubHkgb2YgMSYjMzk7cyBhbmQgMiYjMzk7cyAoMTIgZm9yIDI8c3VwPjk8XC9zdXA+IGFuZCAyMTEyIGZvciAyPHN1cD44OTxcL3N1cD4pLiBJbiBmYWN0LCBpdCBjYW4gYmUgcHJvdmVkIHRoYXQ6PFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPlxyXG48cD5Gb3IgZXZlcnkgaW50ZWdlciBSLCB0aGVyZSBleGlzdHMgYSBwb3dlciBvZiAyIHN1Y2ggdGhhdCAyPHN1cD5LPFwvc3VwPiB1c2VzIG9ubHkgdGhlIGRpZ2l0cyAxIGFuZCAyIGluIGl0cyBsYXN0IFIgZGlnaXRzLjxcL3A+XHJcbjxcL2Jsb2NrcXVvdGU+XHJcblxyXG48cD5UaGlzIGlzIHNob3duIGEgYml0IG1vcmUgY2xlYXJseSBpbiB0aGUgZm9sbG93aW5nIHRhYmxlOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3R3b3JhZy5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTFweDsgd2lkdGg6Mjk3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91ciBqb2IgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUsIGZvciBnaXZlbiBSLCB0aGUgc21hbGxlc3QgSyBzdWNoIHRoYXQgMjxzdXA+SzxcL3N1cD4gZW5kcyBpbiBhIHN0cmluZyBvZiBSIGRpZ2l0cyBjb250YWluaW5nIG9ubHkgMSYjMzk7cyBhbmQgMiYjMzk7cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBkZWNpbWFsIGludGVnZXIsIE4sIDEgJnBvdW5kOyBOICZwb3VuZDsgNTAsIHRoZSBudW1iZXIgb2YgcHJvYmxlbSBkYXRhIHNldHMgdG8gZm9sbG93LiBFYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGludGVnZXIgUiwgMSAmcG91bmQ7IFIgJnBvdW5kOyAyMCwgZm9yIHdoaWNoIHdlIHdhbnQgYSBwb3dlciBvZiAyIGVuZGluZyBpbiBhIHN0cmluZyBvZiBSIDEmIzM5O3MgYW5kIDImIzM5O3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIHlvdSBzaG91bGQgZ2VuZXJhdGUgb25lIGxpbmUgb2Ygb3V0cHV0IHdpdGggdGhlIGZvbGxvd2luZyB2YWx1ZXM6IFRoZSBkYXRhIHNldCBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIgKHN0YXJ0IGNvdW50aW5nIGF0IG9uZSksIGEgc3BhY2UsIHRoZSBpbnB1dCB2YWx1ZSBSLCBhbm90aGVyIHNwYWNlLCBhbmQgdGhlIHNtYWxsZXN0IHZhbHVlIEsgZm9yIHdoaWNoIDI8c3VwPks8XC9zdXA+IGVuZHMgaW4gYSBzdHJpbmcgb2YgUiAxJiMzOTtzIGFuZCAyJiMzOTtzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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