시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 147 104 84 67.742%

문제

존 폰 노이만은 1946년에 유사난수(Pseudo-random Number) 수열을 만드는 방법을 제시했다. 이 방법은 "middle-square" 방법으로 알려져 있으며, 다음과 같이 동작한다.

먼저, 초기값 a0을 고른다. a0은 십진법으로 표기했을 때, 길이가 n을 넘지 않아야 한다. 그 다음, a0을 제곱한 다음에, 길이가 2*n이 될 때 까지 앞에 0을 붙인다. 이제, 가운데 n자리를 ai라고 한다. 이 방법을 사용해 각각의 i>0에 대해서, ai를 계산할 수 있다. 이 문제에서 n=4를 이용한다.

예 1: a0 = 5555, a02 = 30858025, a1 = 8580

예 2: a0 = 1111, a02 = 01234321, a1 = 2343

사실 이 방법은 난수를 만드는데 그렇게 좋은 방법은 아니다. 

a0이 주어졌을 때, 서로 다른 난수를 몇 개 만드는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, a0을 포함하고 있다. (0 < a0 < 10000) 숫자가 네 자리가 아닌 경우에는, 앞에 0을 추가해 네 자리로 만들어져 있다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 서로 다른 ai가 몇 개 나오는지 출력한다. a0도 포함해서 세야 한다.

예제 입력 1

5555
0815
6239
0

예제 출력 1

32
17
111
W3sicHJvYmxlbV9pZCI6IjY1MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI3OWNcdWIzNjQgXHVjMjJiXHVjNzkwIFx1YjljY1x1YjRlNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODc0IFx1ZDNmMCBcdWIxNzhcdWM3NzRcdWI5Y2NcdWM3NDAgMTk0Nlx1YjE0NFx1YzVkMCBcdWM3MjBcdWMwYWNcdWIwOWNcdWMyMTgoUHNldWRvLXJhbmRvbSBOdW1iZXIpIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzgxY1x1YzJkY1x1ZDU4OFx1YjJlNC4gXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0MCAmcXVvdDttaWRkbGUtc3F1YXJlJnF1b3Q7IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWM1NGNcdWI4MjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjNkOVx1Yzc5MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTNjXHVjODAwLCBcdWNkMDhcdWFlMzBcdWFjMTIgYTxzdWI+MDxcL3N1Yj5cdWM3NDQgXHVhY2UwXHViOTc4XHViMmU0LiBhPHN1Yj4wPFwvc3ViPlx1Yzc0MCBcdWMyZWRcdWM5YzRcdWJjOTVcdWM3M2NcdWI4NWMgXHVkNDVjXHVhZTMwXHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhZTM4XHVjNzc0XHVhYzAwIG5cdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIGE8c3ViPjA8XC9zdWI+XHVjNzQ0IFx1YzgxY1x1YWNmMVx1ZDU1YyBcdWIyZTRcdWM3NGNcdWM1ZDAsIFx1YWUzOFx1Yzc3NFx1YWMwMCAyKm5cdWM3NzQgXHViNDIwIFx1YjU0YyBcdWFlNGNcdWM5YzAgXHVjNTVlXHVjNWQwIDBcdWM3NDQgXHViZDk5XHVjNzc4XHViMmU0LiBcdWM3NzRcdWM4MWMsIFx1YWMwMFx1YzZiNFx1YjM3MCBuXHVjNzkwXHViOWFjXHViOTdjIGE8c3ViPmk8XC9zdWI+XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NzQgXHVhYzAxXHVhYzAxXHVjNzU4IGkmZ3Q7MFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIGE8c3ViPmk8XC9zdWI+XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIG49NFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOCAxOiBhPHN1Yj4wPFwvc3ViPiA9IDU1NTUsIGE8c3ViPjA8XC9zdWI+PHN1cD4yPFwvc3VwPiA9IDMwODU4MDI1LCBhPHN1Yj4xPFwvc3ViPiA9IDg1ODA8XC9wPlxyXG5cclxuPHA+XHVjNjA4IDI6IGE8c3ViPjA8XC9zdWI+ID0gMTExMSwgYTxzdWI+MDxcL3N1Yj48c3VwPjI8XC9zdXA+ID0gMDEyMzQzMjEsIGE8c3ViPjE8XC9zdWI+ID0gMjM0MzxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWMyZTQgXHVjNzc0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWIwOWNcdWMyMThcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1YWRmOFx1YjgwN1x1YWM4YyBcdWM4OGJcdWM3NDAgXHViYzI5XHViYzk1XHVjNzQwIFx1YzU0NFx1YjJjOFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+YTxzdWI+MDxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWIwOWNcdWMyMThcdWI5N2MgXHViYTg3IFx1YWMxYyBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM3NzRcdWJhNzAsIGE8c3ViPjA8XC9zdWI+XHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuICgwICZsdDsgYTxzdWI+MDxcL3N1Yj4gJmx0OyAxMDAwMCkgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjEyNCBcdWM3OTBcdWI5YWNcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHVjNTVlXHVjNWQwIDBcdWM3NDQgXHVjZDk0XHVhYzAwXHVkNTc0IFx1YjEyNCBcdWM3OTBcdWI5YWNcdWI4NWMgXHViOWNjXHViNGU0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWQ1NThcdWIwOTggXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBhPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWJhODcgXHVhYzFjIFx1YjA5OFx1YzYyNFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIGE8c3ViPjA8XC9zdWI+XHViM2M0IFx1ZDNlY1x1ZDU2OFx1ZDU3NFx1YzExYyBcdWMxMzhcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY1MDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHZW5lcmF0ZSByYW5kb20gbnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+Sm9obiB2b24gTmV1bWFubiBzdWdnZXN0ZWQgaW4gMTk0NiBhIG1ldGhvZCB0byBjcmVhdGUgYSBzZXF1ZW5jZSBvZiBwc2V1ZG8tcmFuZG9tIG51bWJlcnMuIEhpcyBpZGVhIGlzIGtub3duIGFzIHRoZSAmcXVvdDttaWRkbGUtc3F1YXJlJnF1b3Q7LW1ldGhvZCBhbmQgd29ya3MgYXMgZm9sbG93czogV2UgY2hvb3NlIGFuIGluaXRpYWwgdmFsdWUgYTAsIHdoaWNoIGhhcyBhIGRlY2ltYWwgcmVwcmVzZW50YXRpb24gb2YgbGVuZ3RoIGF0IG1vc3Qgbi4gV2UgdGhlbiBtdWx0aXBseSB0aGUgdmFsdWUgYTxzdWI+MDxcL3N1Yj4gYnkgaXRzZWxmLCBhZGQgbGVhZGluZyB6ZXJvcyB1bnRpbCB3ZSBnZXQgYSBkZWNpbWFsIHJlcHJlc2VudGF0aW9uIG9mIGxlbmd0aCAyICZ0aW1lczsgbiBhbmQgdGFrZSB0aGUgbWlkZGxlIG4gZGlnaXRzIHRvIGZvcm0gYTxzdWI+aTxcL3N1Yj4uIFRoaXMgcHJvY2VzcyBpcyByZXBlYXRlZCBmb3IgZWFjaCBhPHN1Yj5pPFwvc3ViPiB3aXRoIGkmZ3Q7MC4gSW4gdGhpcyBwcm9ibGVtIHdlIHVzZSBuID0gNC48XC9wPlxyXG5cclxuPHA+RXhhbXBsZSAxOiBhPHN1Yj4wPFwvc3ViPj01NTU1LCBhPHN1Yj4wPFwvc3ViPjxzdXA+MjxcL3N1cD49MzA4NTgwMjUsIGE8c3ViPjE8XC9zdWI+PTg1ODAsLi4uPFwvcD5cclxuXHJcbjxwPkV4YW1wbGUgMjogYTxzdWI+MDxcL3N1Yj49MTExMSwgYTxzdWI+MDxcL3N1Yj48c3VwPjI8XC9zdXA+PTAxMjM0MzIxLCBhPHN1Yj4xPFwvc3ViPj0yMzQzLC4uLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCB0aGlzIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yIGlzIG5vdCB2ZXJ5IGdvb2QuIFdoZW4gc3RhcnRlZCB3aXRoIGFuIGluaXRpYWwgdmFsdWUgaXQgZG9lcyBub3QgcHJvZHVjZSBhbGwgb3RoZXIgbnVtYmVycyB3aXRoIHRoZSBzYW1lIG51bWJlciBvZiBkaWdpdHMuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBjaGVjayBmb3IgYSBnaXZlbiBpbml0aWFsIHZhbHVlIGEwIGhvdyBtYW55IGRpZmZlcmVudCBudW1iZXJzIGFyZSBwcm9kdWNlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIG9uZSBsaW5lIGNvbnRhaW5pbmcgYTxzdWI+MDxcL3N1Yj4gKDAgJmx0OyBhPHN1Yj4wPFwvc3ViPiAmbHQ7IDEwMDAwKS4gTnVtYmVycyBhcmUgcG9zc2libHkgcGFkZGVkIHdpdGggbGVhZGluZyB6ZXJvcyBzdWNoIHRoYXQgZWFjaCBudW1iZXIgY29uc2lzdHMgb2YgZXhhY3RseSA0IGRpZ2l0cy4gVGhlIGlucHV0IGlzIHRlcm1pbmF0ZWQgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgdmFsdWUgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IGEgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHZhbHVlcyBhaSBwcm9kdWNlZCBieSB0aGlzIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yIHdoZW4gc3RhcnRlZCB3aXRoIHRoZSBnaXZlbiB2YWx1ZSBhPHN1Yj4wPFwvc3ViPi4gTm90ZSB0aGF0IGE8c3ViPjA8XC9zdWI+IHNob3VsZCBhbHNvIGJlIGNvdW50ZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > University of Ulm Local Contest > University of Ulm Local Contest 2009 G번

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