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

문제

팰린드롬은 앞에서 부터 읽었을 때와 뒤에서 부터 읽었을 때가 같은 문자열을 말한다. 예를 들어, "ala"과 "aa"는 팰린드롬이고, "adam"은 팰린드롬이 아니다.

모든 정수는 \((a_na_{n-1}\dots a_1a_0)_k\)와 같이 k진법으로 나타낼 수 있다. 모든 \(a_i\)는 k보다 작은 음이 아닌 정수이어야 한다.

\((a_na_{n-1}\dots a_1a_0)_k\)가 나타내는 값은 \(a_n \cdot k^n + a_{n-1} \cdot k^{n-1} + \cdots + a_1 \cdot k + a_0\) 이다. 예를 들어, 10진법 숫자 \(123_{10}\)의 값은 \(1 \cdot 100 + 2 \cdot 10 + 3\)이고, 8진법 숫자 \(123_8\)의 값은 \(1 \cdot 64 + 2 \cdot 8 + 3\) 이다.

10진법 숫자 \(n\)이 주어졌을 때, \(\left\{ 2, 3, \dots, 10 \right\} \)진법으로 나타냈을 때, 팰린드롬인 것을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 \(n\)이 주어진다. (1 ≤ \(n\) ≤ 101000)

출력

\(n\)을 \(2, 3, \dots, 10\) 진법으로 나타냈을 때, 팰린드롬인 경우가 없다면, "NIE"를 출력한다. 그 외의 경우에는 팰린드롬이 되는 진법 \(b\)와 \(n\)을 \(b\)진법으로 나타낸 수 \(m\)을 출력한다. 출력은 \(b\)가 증가하는 순서대로 한다.

예제 입력 1

15

예제 출력 1

2 1111
4 33

힌트

\(1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2 + 1 = 3 \cdot 4 + 3 = 15\)

W3sicHJvYmxlbV9pZCI6Ijg2MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMgXHVjMjJiXHVjNzkwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NDAgXHVjNTVlXHVjNWQwXHVjMTFjIFx1YmQ4MFx1ZDEzMCBcdWM3N2RcdWM1YzhcdWM3NDQgXHViNTRjXHVjNjQwIFx1YjRhNFx1YzVkMFx1YzExYyBcdWJkODBcdWQxMzAgXHVjNzdkXHVjNWM4XHVjNzQ0IFx1YjU0Y1x1YWMwMCBcdWFjMTlcdWM3NDAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YjlkMFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgJnF1b3Q7YWxhJnF1b3Q7XHVhY2ZjICZxdW90O2FhJnF1b3Q7XHViMjk0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YWNlMCwgJnF1b3Q7YWRhbSZxdW90O1x1Yzc0MCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHViMjk0IFxcKChhX25hX3tuLTF9XFxkb3RzIGFfMWFfMClfa1xcKVx1YzY0MCBcdWFjMTlcdWM3NzQga1x1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViYWE4XHViNGUwIFxcKGFfaVxcKVx1YjI5NCBrXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxcKChhX25hX3tuLTF9XFxkb3RzIGFfMWFfMClfa1xcKVx1YWMwMCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzEyXHVjNzQwIFxcKGFfbiBcXGNkb3Qga15uICsgYV97bi0xfSBcXGNkb3Qga157bi0xfSArIFxcY2RvdHMgKyBhXzEgXFxjZG90IGsgKyBhXzBcXCkgXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxMFx1YzljNFx1YmM5NSBcdWMyMmJcdWM3OTAgXFwoMTIzX3sxMH1cXClcdWM3NTggXHVhYzEyXHVjNzQwIFxcKDEgXFxjZG90IDEwMCArIDIgXFxjZG90IDEwICsgM1xcKVx1Yzc3NFx1YWNlMCwgOFx1YzljNFx1YmM5NSBcdWMyMmJcdWM3OTAgXFwoMTIzXzhcXClcdWM3NTggXHVhYzEyXHVjNzQwIFxcKDEgXFxjZG90IDY0ICsgMiBcXGNkb3QgOCArIDNcXCkgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4xMFx1YzljNFx1YmM5NSBcdWMyMmJcdWM3OTAgXFwoblxcKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcXChcXGxlZnRcXHsgMiwgMywgXFxkb3RzLCAxMCBcXHJpZ2h0XFx9IFxcKVx1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYzhcdWM3NDQgXHViNTRjLCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzggXHVhYzgzXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXFwoblxcKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgXFwoblxcKSAmbGU7IDEwPHN1cD4xMDAwPFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cXChuXFwpXHVjNzQ0IFxcKDIsIDMsIFxcZG90cywgMTBcXCkgXHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBjOFx1Yzc0NCBcdWI1NGMsIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0LCAmcXVvdDtOSUUmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFkZjggXHVjNjc4XHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHViNDE4XHViMjk0IFx1YzljNFx1YmM5NSBcXChiXFwpXHVjNjQwIFxcKG5cXClcdWM3NDQgXFwoYlxcKVx1YzljNFx1YmM5NVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVjMjE4IFxcKG1cXClcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWM3NDAgXFwoYlxcKVx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XFwoMSBcXGNkb3QgMl4zICsgMSBcXGNkb3QgMl4yICsgMSBcXGNkb3QgMiArIDEgPSAzIFxcY2RvdCA0ICsgMyA9IDE1XFwpPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI4NjExIiwicHJvYmxlbV9sYW5nIjoiMyIsInRpdGxlIjoiUGFsaW5kcm9saWN6YnkiLCJkZXNjcmlwdGlvbiI6IjxwPlBhbGluZHJvbSB0byB0ZWtzdCwga3Qmb2FjdXRlO3J5IGN6eXRhbnkgd3NwYWsgamVzdCBpZGVudHljem55IHogc2FteW0gc29iXHUwMTA1LiBOcC4gdGVrc3R5ICZxdW90O2FsYSZxdW90OyBvcmF6ICZxdW90O2FhJnF1b3Q7IHNcdTAxMDUgcGFsaW5kcm9tYW1pLCB6YVx1MDE1YiB0ZWtzdCAmcXVvdDthZGFtJnF1b3Q7IC0ganVcdTAxN2MgbmllLjxcL3A+XHJcblxyXG48cD5LYVx1MDE3Y2RcdTAxMDUgbGljemJcdTAxMTkgY2FcdTAxNDJrb3dpdFx1MDEwNSBtb1x1MDE3Y25hIHphcGlzYVx1MDEwNyB3IHN5c3RlbWllIHBvenljeWpueW0gbyBwb2RzdGF3aWUgYlx1MDExOWRcdTAxMDVjZWogZG93b2xuXHUwMTA1IGxpY3piXHUwMTA1IGNhXHUwMTQya293aXRcdTAxMDUgd2lcdTAxMTlrc3pcdTAxMDUgbmlcdTAxN2MgMS4gWmFwaXMgXFwoKGFfbmFfe24tMX1cXGRvdHMgYV8xYV8wKV9rXFwpIG96bmFjemEgbGljemJcdTAxMTkgbyBrb2xlam55Y2ggY3lmcmFjaCBcXChhX25hX3tuLTF9XFxkb3RzIGFfMWFfMFxcKSB3IHphcGlzaWUgcG96eWN5am55bSBvIHBvZHN0YXdpZSBcXChrXFwpLiBLYVx1MDE3Y2RhIHogdHljaCBjeWZyIG11c2kgbWllXHUwMTA3IHd0ZWR5IHdhcnRvXHUwMTViXHUwMTA3IG5pZXVqZW1uXHUwMTA1IG1uaWVqc3pcdTAxMDUgbmlcdTAxN2MgXFwoa1xcKS48XC9wPlxyXG5cclxuPHA+TGljemJhIFxcKChhX25hX3tuLTF9XFxkb3RzIGFfMWFfMClfa1xcKSBtYSB3YXJ0b1x1MDE1Ylx1MDEwNzogXFwoYV9uIFxcY2RvdCBrXm4gKyBhX3tuLTF9IFxcY2RvdCBrXntuLTF9ICsgXFxjZG90cyArIGFfMSBcXGNkb3QgayArIGFfMFxcKS4gTmEgcHJ6eWtcdTAxNDJhZCBsaWN6YmEgXFwoMTIzX3sxMH1cXCkgamVzdCB6YXBpc2FuYSB3IHN5c3RlbWllIGR6aWVzaVx1MDExOXRueW0gaSBtYSB3YXJ0b1x1MDE1Ylx1MDEwNyBcXCgxIFxcY2RvdCAxMDAgKyAyIFxcY2RvdCAxMCArIDNcXCkuIE5hdG9taWFzdCBsaWN6YmEgXFwoMTIzXzhcXCkgamVzdCB6YXBpc2FuYSB3IHN5c3RlbWllICZvYWN1dGU7c2Vta293eW0gaSBtYSB3YXJ0b1x1MDE1Ylx1MDEwNyBcXCgxIFxcY2RvdCA2NCArIDIgXFxjZG90IDggKyAzXFwpLjxcL3A+XHJcblxyXG48cD5QYWxpbmRyb2xpY3piXHUwMTA1IG5hendpZW15IGxpY3piXHUwMTE5LCBrdCZvYWN1dGU7cmEgemFwaXNhbmEgdyBwZXdueW0gc3lzdGVtaWUgcG96eWN5am55bSBqZXN0IHBhbGluZHJvbWVtLiBUd29pbSB6YWRhbmllbSBqZXN0IG5hcGlzYW5pZSBwcm9ncmFtdSwga3Qmb2FjdXRlO3J5IGRsYSBkYW5laiBsaWN6Ynkgc3ByYXdkemksIHcgamFraWNoIHN5c3RlbWFjaCBwb3p5Y3lqbnljaCBvIHBvZHN0YXdpZSB6ZSB6YmlvcnUgXFwoXFxsZWZ0XFx7IDIsIDMsIFxcZG90cywgMTAgXFxyaWdodFxcfSBcXCkgamVzdCBvbmEgcGFsaW5kcm9saWN6Ylx1MDEwNS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlBpZXJ3c3p5IGkgamVkeW55IHdpZXJzeiBzdGFuZGFyZG93ZWdvIHdlalx1MDE1YmNpYSB6YXdpZXJhIGplZG5cdTAxMDUgbGljemJcdTAxMTkgY2FcdTAxNDJrb3dpdFx1MDEwNSBuICgxICZsZTsgbiAmbGU7IDEwPHN1cD4xMDAwPFwvc3VwPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SmVcdTAxN2NlbGkgXFwoblxcKSBuaWUgamVzdCBwYWxpbmRyb2xpY3piXHUwMTA1IHByenkgXHUwMTdjYWRuZWogeiBwb2RzdGF3IFxcKDIsIDMsIFxcZG90cywgMTBcXCksIHRvIG5hIHN0YW5kYXJkb3d5bSB3eWpcdTAxNWJjaXUgbmFsZVx1MDE3Y3kgd3lwaXNhXHUwMTA3IGplZG5vIHNcdTAxNDJvd28gJnF1b3Q7TklFJnF1b3Q7IChiZXogY3VkenlzXHUwMTQyb3d1KS4gVyBwcnplY2l3bnltIHByenlwYWRrdSBUdyZvYWN1dGU7aiBwcm9ncmFtIHBvd2luaWVuIGRsYSBrYVx1MDE3Y2RlaiBwb2RzdGF3eSB6ZSB6YmlvcnUgJm5ic3A7XFwoXFxsZWZ0XFx7IDIsIDMsIFxcZG90cywgMTAgXFxyaWdodFxcfSBcXCksIHByenkga3Qmb2FjdXRlO3JlaiBcXChuXFwpIGplc3QgcGFsaW5kcm9saWN6Ylx1MDEwNSwgd3lwaXNhXHUwMTA3IG5hIHd5alx1MDE1YmNpdSBqZWRlbiB3aWVyc3osIHphd2llcmFqXHUwMTA1Y3kgZHdpZSBsaWN6YnkgY2FcdTAxNDJrb3dpdGUgXFwoa1xcKSBvcmF6IFxcKG1cXCkgb2RkemllbG9uZSBwb2plZHluY3p5bSBvZHN0XHUwMTE5cGVtLCBnZHppZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cXChrXFwpIGplc3QgcG9kc3Rhd1x1MDEwNSBzeXN0ZW11IHBvenljeWpuZWdvIHphcGlzYW5cdTAxMDUgZHppZXNpXHUwMTE5dG5pZSw8XC9saT5cclxuXHQ8bGk+XFwobVxcKSBqZXN0IGxpY3piXHUwMTA1IFxcKG5cXCkgemFwaXNhblx1MDEwNSB3IHN5c3RlbWllIHBvenljeWpueW0gbyBwb2RzdGF3aWUgXFwoa1xcKSAoanVcdTAxN2MgYmV6IGRvbG5lZ28gaW5kZWtzdSBvem5hY3phalx1MDEwNWNlZ28gcG9kc3Rhd1x1MDExOSB6YXBpc3UpLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldpZXJzemUgdGUgcG93aW5ueSBieVx1MDEwNyBwb3NvcnRvd2FuZSB6Z29kbmllIHogcm9zblx1MDEwNWNcdTAxMDUgd2FydG9cdTAxNWJjaVx1MDEwNSBcXChrXFwpLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cXCgxIFxcY2RvdCAyXjMgKyAxIFxcY2RvdCAyXjIgKyAxIFxcY2RvdCAyICsgMSA9IDMgXFxjZG90IDQgKyAzID0gMTVcXCk8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IlBvbGlzaCJ9XQ==

출처

Olympiad > Junior Polish Olympiad in Informatics > JPOI 2009 2-0번

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