시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 257 74 65 32.995%

문제

팰린드롬은 앞에서 부터 읽었을 때와 뒤에서 부터 읽었을 때가 같은 문자열을 말한다. 예를 들어, "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+XFwoMSBcXGNkb3QgMl4zICsgMSBcXGNkb3QgMl4yICsgMSBcXGNkb3QgMiArIDEgPSAzIFxcY2RvdCA0ICsgMyA9IDE1XFwpPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4NjExIiwicHJvYmxlbV9sYW5nIjoiMyIsInRpdGxlIjoiUGFsaW5kcm9saWN6YnkiLCJkZXNjcmlwdGlvbiI6IjxwPlBhbGluZHJvbSB0byB0ZWtzdCwga3Qmb2FjdXRlO3J5IGN6eXRhbnkgd3NwYWsgamVzdCBpZGVudHljem55IHogc2FteW0gc29iXHUwMTA1LiBOcC4gdGVrc3R5ICZxdW90O2FsYSZxdW90OyBvcmF6ICZxdW90O2FhJnF1b3Q7IHNcdTAxMDUgcGFsaW5kcm9tYW1pLCB6YVx1MDE1YiB0ZWtzdCAmcXVvdDthZGFtJnF1b3Q7IC0ganVcdTAxN2MgbmllLjxcL3A+XHJcblxyXG48cD5LYVx1MDE3Y2RcdTAxMDUgbGljemJcdTAxMTkgY2FcdTAxNDJrb3dpdFx1MDEwNSBtb1x1MDE3Y25hIHphcGlzYVx1MDEwNyB3IHN5c3RlbWllIHBvenljeWpueW0gbyBwb2RzdGF3aWUgYlx1MDExOWRcdTAxMDVjZWogZG93b2xuXHUwMTA1IGxpY3piXHUwMTA1IGNhXHUwMTQya293aXRcdTAxMDUgd2lcdTAxMTlrc3pcdTAxMDUgbmlcdTAxN2MgMS4gWmFwaXMgXFwoKGFfbmFfe24tMX1cXGRvdHMgYV8xYV8wKV9rXFwpIG96bmFjemEgbGljemJcdTAxMTkgbyBrb2xlam55Y2ggY3lmcmFjaCBcXChhX25hX3tuLTF9XFxkb3RzIGFfMWFfMFxcKSB3IHphcGlzaWUgcG96eWN5am55bSBvIHBvZHN0YXdpZSBcXChrXFwpLiBLYVx1MDE3Y2RhIHogdHljaCBjeWZyIG11c2kgbWllXHUwMTA3IHd0ZWR5IHdhcnRvXHUwMTViXHUwMTA3IG5pZXVqZW1uXHUwMTA1IG1uaWVqc3pcdTAxMDUgbmlcdTAxN2MgXFwoa1xcKS48XC9wPlxyXG5cclxuPHA+TGljemJhIFxcKChhX25hX3tuLTF9XFxkb3RzIGFfMWFfMClfa1xcKSBtYSB3YXJ0b1x1MDE1Ylx1MDEwNzogXFwoYV9uIFxcY2RvdCBrXm4gKyBhX3tuLTF9IFxcY2RvdCBrXntuLTF9ICsgXFxjZG90cyArIGFfMSBcXGNkb3QgayArIGFfMFxcKS4gTmEgcHJ6eWtcdTAxNDJhZCBsaWN6YmEgXFwoMTIzX3sxMH1cXCkgamVzdCB6YXBpc2FuYSB3IHN5c3RlbWllIGR6aWVzaVx1MDExOXRueW0gaSBtYSB3YXJ0b1x1MDE1Ylx1MDEwNyBcXCgxIFxcY2RvdCAxMDAgKyAyIFxcY2RvdCAxMCArIDNcXCkuIE5hdG9taWFzdCBsaWN6YmEgXFwoMTIzXzhcXCkgamVzdCB6YXBpc2FuYSB3IHN5c3RlbWllICZvYWN1dGU7c2Vta293eW0gaSBtYSB3YXJ0b1x1MDE1Ylx1MDEwNyBcXCgxIFxcY2RvdCA2NCArIDIgXFxjZG90IDggKyAzXFwpLjxcL3A+XHJcblxyXG48cD5QYWxpbmRyb2xpY3piXHUwMTA1IG5hendpZW15IGxpY3piXHUwMTE5LCBrdCZvYWN1dGU7cmEgemFwaXNhbmEgdyBwZXdueW0gc3lzdGVtaWUgcG96eWN5am55bSBqZXN0IHBhbGluZHJvbWVtLiBUd29pbSB6YWRhbmllbSBqZXN0IG5hcGlzYW5pZSBwcm9ncmFtdSwga3Qmb2FjdXRlO3J5IGRsYSBkYW5laiBsaWN6Ynkgc3ByYXdkemksIHcgamFraWNoIHN5c3RlbWFjaCBwb3p5Y3lqbnljaCBvIHBvZHN0YXdpZSB6ZSB6YmlvcnUgXFwoXFxsZWZ0XFx7IDIsIDMsIFxcZG90cywgMTAgXFxyaWdodFxcfSBcXCkgamVzdCBvbmEgcGFsaW5kcm9saWN6Ylx1MDEwNS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlBpZXJ3c3p5IGkgamVkeW55IHdpZXJzeiBzdGFuZGFyZG93ZWdvIHdlalx1MDE1YmNpYSB6YXdpZXJhIGplZG5cdTAxMDUgbGljemJcdTAxMTkgY2FcdTAxNDJrb3dpdFx1MDEwNSBuICgxICZsZTsgbiAmbGU7IDEwPHN1cD4xMDAwPFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkplXHUwMTdjZWxpIFxcKG5cXCkgbmllIGplc3QgcGFsaW5kcm9saWN6Ylx1MDEwNSBwcnp5IFx1MDE3Y2FkbmVqIHogcG9kc3RhdyBcXCgyLCAzLCBcXGRvdHMsIDEwXFwpLCB0byBuYSBzdGFuZGFyZG93eW0gd3lqXHUwMTViY2l1IG5hbGVcdTAxN2N5IHd5cGlzYVx1MDEwNyBqZWRubyBzXHUwMTQyb3dvICZxdW90O05JRSZxdW90OyAoYmV6IGN1ZHp5c1x1MDE0Mm93dSkuIFcgcHJ6ZWNpd255bSBwcnp5cGFka3UgVHcmb2FjdXRlO2ogcHJvZ3JhbSBwb3dpbmllbiBkbGEga2FcdTAxN2NkZWogcG9kc3Rhd3kgemUgemJpb3J1ICZuYnNwO1xcKFxcbGVmdFxceyAyLCAzLCBcXGRvdHMsIDEwIFxccmlnaHRcXH0gXFwpLCBwcnp5IGt0Jm9hY3V0ZTtyZWogXFwoblxcKSBqZXN0IHBhbGluZHJvbGljemJcdTAxMDUsIHd5cGlzYVx1MDEwNyBuYSB3eWpcdTAxNWJjaXUgamVkZW4gd2llcnN6LCB6YXdpZXJhalx1MDEwNWN5IGR3aWUgbGljemJ5IGNhXHUwMTQya293aXRlIFxcKGtcXCkgb3JheiBcXChtXFwpIG9kZHppZWxvbmUgcG9qZWR5bmN6eW0gb2RzdFx1MDExOXBlbSwgZ2R6aWU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XFwoa1xcKSBqZXN0IHBvZHN0YXdcdTAxMDUgc3lzdGVtdSBwb3p5Y3lqbmVnbyB6YXBpc2FuXHUwMTA1IGR6aWVzaVx1MDExOXRuaWUsPFwvbGk+XHJcblx0PGxpPlxcKG1cXCkgamVzdCBsaWN6Ylx1MDEwNSBcXChuXFwpIHphcGlzYW5cdTAxMDUgdyBzeXN0ZW1pZSBwb3p5Y3lqbnltIG8gcG9kc3Rhd2llIFxcKGtcXCkgKGp1XHUwMTdjIGJleiBkb2xuZWdvIGluZGVrc3Ugb3puYWN6YWpcdTAxMDVjZWdvIHBvZHN0YXdcdTAxMTkgemFwaXN1KS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5XaWVyc3plIHRlIHBvd2lubnkgYnlcdTAxMDcgcG9zb3J0b3dhbmUgemdvZG5pZSB6IHJvc25cdTAxMDVjXHUwMTA1IHdhcnRvXHUwMTViY2lcdTAxMDUgXFwoa1xcKS48XC9wPlxyXG4iLCJoaW50IjoiPHA+XFwoMSBcXGNkb3QgMl4zICsgMSBcXGNkb3QgMl4yICsgMSBcXGNkb3QgMiArIDEgPSAzIFxcY2RvdCA0ICsgMyA9IDE1XFwpPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQzZjRcdWI3ODBcdWI0ZGNcdWM1YjQifV0=

출처

Olympiad > Junior Polish Olympiad in Informatics > JPOI 2009 20번

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