문제
다음과 같은 수열을 생각해보자: 2ドル → 12 → 1112 → 3112 → 132112 → 1113122112 → \dots$.
이 수열의 초기값은 2ドル$이고, 이후의 수들은 다음과 같이 생성된다.
- 2ドル$에는 “1ドル$개의 2ドル$”가 있으므로, 다음 값은 12ドル$이다.
- 12ドル$에는 “1ドル$개의 1ドル,ドル 1ドル$개의 2ドル$”가 있으므로 다음 값은 1112ドル$이다.
- 1112ドル$에는 “3ドル$개의 1ドル,ドル 1ドル$개의 2ドル$”가 있으므로 다음 값은 3112ドル$이다.
- 3112ドル$에는 “1ドル$개의 3ドル,ドル 2ドル$개의 1ドル,ドル 1ドル$개의 2ドル$”가 있으므로, 다음 값은 132112ドル$이다.
이 수열은 이러한 “look-and-say” 규칙으로 생성된다. 이 수열에서 다음 항을 계산하는 규칙을 양의 정수 $x > 0$에 적용해서 나오는 수를 $f(x)$라고 하자. 즉, $f(2) = 12,ドル $f(12) = 1112,ドル $f(1112) = 3112,ドル $f(3112) = 132112$와 같이 주어지는 양의 정수에 대해 이를 십진법으로 읽었을 때 연속되는 숫자의 개수를 보이는 대로 읽어서 만들어지는 수를 의미한다.
양의 정수 $x$에 연속해서 나타나는 숫자가 9ドル$회를 넘지 않을 때에만 $f(x)$가 정의되며, “look-and-say” 규칙을 적용하여 $f(x) = n$인 $n$을 얻을 수 있다. 여러분이 할 일은 입력으로 양의 정수 $n$이 주어질때, $f(x) = n$인 양의 정수 $x$를 구하는 것이다. $x$가 존재한다면 그 값은 유일하다. 주의할 점은 어떤 양의 정수 $n$은 그러한 $x$를 가지지 않는다는 것이다. 예를 들어, $f(x) = 311$인 양의 정수 $x$는 존재하지않는다. 또한 $f(x) = 1111$인 양의 정수 $x$ 역시 존재하지 않는다. 1111ドル$의 경우 “1ドル$개의 1ドル,ドル 1ドル$개의 1ドル$”로 해석하여 $x$가 11ドル$이라 생각할 수 있으나, $f(11) = 21$이다. 어떤 양의 정수도 이 “look-and-say” 규칙에 따라 1111ドル$을 생성할 수 없다.
출력
$f(x) = n$인 양의 정수 $x$가 존재한다면 그 값을 출력하고, 그렇지 않다면 $-1$을 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0NjgyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiSW52ZXJzZSBMb29rLWFuZC1TYXkiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MDogJDIgJnJhcnI7IDEyICZyYXJyOyAxMTEyICZyYXJyOyAzMTEyICZyYXJyOyAxMzIxMTIgJnJhcnI7IDExMTMxMjIxMTIgJnJhcnI7IFxcZG90cyQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjZDA4XHVhZTMwXHVhYzEyXHVjNzQwICQyJFx1Yzc3NFx1YWNlMCwgXHVjNzc0XHVkNmM0XHVjNzU4IFx1YzIxOFx1YjRlNFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzBkZFx1YzEzMVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG48bGk+JDIkXHVjNWQwXHViMjk0ICZsZHF1bzskMSRcdWFjMWNcdWM3NTggJDIkJnJkcXVvO1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsIFx1YjJlNFx1Yzc0YyBcdWFjMTJcdWM3NDAgJDEyJFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPGxpPiQxMiRcdWM1ZDBcdWIyOTQgJmxkcXVvOyQxJFx1YWMxY1x1Yzc1OCAkMSQsICQxJFx1YWMxY1x1Yzc1OCAkMiQmcmRxdW87XHVhYzAwIFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyBcdWIyZTRcdWM3NGMgXHVhYzEyXHVjNzQwICQxMTEyJFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPGxpPiQxMTEyJFx1YzVkMFx1YjI5NCAmbGRxdW87JDMkXHVhYzFjXHVjNzU4ICQxJCwgJDEkXHVhYzFjXHVjNzU4ICQyJCZyZHF1bztcdWFjMDAgXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIFx1YjJlNFx1Yzc0YyBcdWFjMTJcdWM3NDAgJDMxMTIkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48bGk+JDMxMTIkXHVjNWQwXHViMjk0ICZsZHF1bzskMSRcdWFjMWNcdWM3NTggJDMkLCAkMiRcdWFjMWNcdWM3NTggJDEkLCAkMSRcdWFjMWNcdWM3NTggJDIkJnJkcXVvO1x1YWMwMCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMsIFx1YjJlNFx1Yzc0YyBcdWFjMTJcdWM3NDAgJDEzMjExMiRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWM3NzRcdWI3ZWNcdWQ1NWMgJmxkcXVvO2xvb2stYW5kLXNheSZyZHF1bzsgXHVhZGRjXHVjZTU5XHVjNzNjXHViODVjIFx1YzBkZFx1YzEzMVx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWIyZTRcdWM3NGMgXHVkNTZkXHVjNzQ0IFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkeCAmZ3Q7IDAkXHVjNWQwIFx1YzgwMVx1YzZhOVx1ZDU3NFx1YzExYyBcdWIwOThcdWM2MjRcdWIyOTQgXHVjMjE4XHViOTdjICRmKHgpJFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzk4OSwgJGYoMikgPSAxMiQsICRmKDEyKSA9IDExMTIkLCAkZigxMTEyKSA9IDMxMTIkLCAkZigzMTEyKSA9IDEzMjExMiRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM3NzRcdWI5N2MgXHVjMmVkXHVjOWM0XHViYzk1XHVjNzNjXHViODVjIFx1Yzc3ZFx1YzVjOFx1Yzc0NCBcdWI1NGMgXHVjNWYwXHVjMThkXHViNDE4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHViY2Y0XHVjNzc0XHViMjk0IFx1YjMwMFx1Yjg1YyBcdWM3N2RcdWM1YjRcdWMxMWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOWMwXHViMjk0IFx1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJHgkXHVjNWQwIFx1YzVmMFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwICQ5JFx1ZDY4Y1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YjU0Y1x1YzVkMFx1YjljYyAkZih4KSRcdWFjMDAgXHVjODE1XHVjNzU4XHViNDE4XHViYTcwLCAmbGRxdW87bG9vay1hbmQtc2F5JnJkcXVvOyBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjODAxXHVjNmE5XHVkNTU4XHVjNWVjICRmKHgpID0gbiRcdWM3NzggJG4kXHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1ZWNcdWI3ZWNcdWJkODRcdWM3NzQgXHVkNTYwIFx1Yzc3Y1x1Yzc0MCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCAkbiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4XHViNTRjLCAkZih4KSA9IG4kXHVjNzc4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJHgkXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuICR4JFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YWMxMlx1Yzc0MCBcdWM3MjBcdWM3N2NcdWQ1NThcdWIyZTQuIFx1YzhmY1x1Yzc1OFx1ZDU2MCBcdWM4MTBcdWM3NDAgXHVjNWI0XHViNWE0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJG4kXHVjNzQwIFx1YWRmOFx1YjdlY1x1ZDU1YyAkeCRcdWI5N2MgXHVhYzAwXHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICRmKHgpID0gMzExJFx1Yzc3OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4ICR4JFx1YjI5NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjYxMFx1ZDU1YyAkZih4KSA9IDExMTEkXHVjNzc4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJHgkIFx1YzVlZFx1YzJkYyBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiAkMTExMSRcdWM3NTggXHVhY2JkXHVjNmIwICZsZHF1bzskMSRcdWFjMWNcdWM3NTggJDEkLCAkMSRcdWFjMWNcdWM3NTggJDEkJnJkcXVvO1x1Yjg1YyBcdWQ1NzRcdWMxMWRcdWQ1NThcdWM1ZWMgJHgkXHVhYzAwICQxMSRcdWM3NzRcdWI3N2MgXHVjMGRkXHVhYzAxXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWIwOTgsICRmKDExKSA9IDIxJFx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWIzYzQgXHVjNzc0ICZsZHF1bztsb29rLWFuZC1zYXkmcmRxdW87IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWI1MzBcdWI3N2MgJDExMTEkXHVjNzQ0IFx1YzBkZFx1YzEzMVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1Y2NhYiBcdWM5MDRcdWM1ZDAgJDEwXnsxXFwsMDAwfSRcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJG4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4kZih4KSA9IG4kXHVjNzc4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMTggJHgkXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNFx1YmE3NCBcdWFkZjggXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCAkLTEkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNDY4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkludmVyc2UgTG9vay1hbmQtU2F5IiwiZGVzY3JpcHRpb24iOiI8cD5Db25zaWRlciB0aGUgZm9sbG93aW5nIHNlcXVlbmNlOiAkMiAmcmFycjsgMTIgJnJhcnI7IDExMTIgJnJhcnI7IDMxMTIgJnJhcnI7IDEzMjExMiAmcmFycjsgMTExMzEyMjExMiAmcmFycjsgXFxkb3RzJC48XC9wPlxyXG5cclxuPHA+VGhlIGluaXRpYWwgdmFsdWUgb2YgdGhpcyBzZXF1ZW5jZSBpcyAkMiQsIGFuZCBzdWJzZXF1ZW50IHZhbHVlcyBhcmUgZ2VuZXJhdGVkIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JDIkIGNvbnRhaW5zICZsZHF1bztvbmUgJDIkLCZyZHF1bzsgc28gdGhlIG5leHQgdGVybSBpcyAkMTIkLjxcL2xpPlxyXG5cdDxsaT4kMTIkIGNvbnRhaW5zICZsZHF1bztvbmUgJDEkIGFuZCBvbmUgJDIkLCZyZHF1bzsmbmJzcDtzbyB0aGUgbmV4dCB0ZXJtIGlzICQxMTEyJC48XC9saT5cclxuXHQ8bGk+JDExMTIkIGNvbnRhaW5zICZsZHF1bzt0aHJlZSAkMSQmIzM5O3MgYW5kIG9uZSAkMiQsJnJkcXVvOyZuYnNwO2FuZCB0aGUgbmV4dCB0ZXJtIGlzICQzMTEyJC48XC9saT5cclxuXHQ8bGk+JDMxMTIkIGNvbnRhaW5zICZsZHF1bztvbmUgJDMkLCB0d28gJDEkJiMzOTtzLCBhbmQgb25lICQyJCwmcmRxdW87Jm5ic3A7dGhlIG5leHQgdGVybSBpcyAkMTMyMTEyJC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGlzIHNlcXVlbmNlIGZvbGxvd3MgdGhlICZsZHF1bztsb29rLWFuZC1zYXkmcmRxdW87IHJ1bGUuIExldCAkZih4KSQgZGVub3RlIHRoZSBudW1iZXIgb2J0YWluZWQgYnkgYXBwbHlpbmcgdGhlIHJ1bGUgb2YgdGhlIHNlcXVlbmNlIHRvIGEgcG9zaXRpdmUgaW50ZWdlciAkeCAmZ3Q7IDAkLiBUaGVuLCAkZigyKSA9IDEyJCwgJGYoMTIpID0gMTExMiQsICRmKDExMTIpID0gMzExMiQsICRmKDMxMTIpID0gMTMyMTEyJCwgYW5kIHNvIG9uLjxcL3A+XHJcblxyXG48cD5UaGUgZnVuY3Rpb24gJGYoeCkkIGlzIGRlZmluZWQgb25seSB3aGVuIG5vIGRpZ2l0IGluIHRoZSBwb3NpdGl2ZSBpbnRlZ2VyICR4JCBhcHBlYXJzIGNvbnNlY3V0aXZlbHkgbW9yZSB0aGFuICQ5JCB0aW1lcy4gQnkgYXBwbHlpbmcgdGhlICZsZHF1bztsb29rLWFuZC1zYXkmcmRxdW87IHJ1bGUsIHdlIGNhbiBvYnRhaW4gYSBudW1iZXIgJG4kIHN1Y2ggdGhhdCAkZih4KSA9IG4kLiBZb3VyIHRhc2sgaXMsIGdpdmVuIGEgcG9zaXRpdmUgaW50ZWdlciAkbiQgYXMgaW5wdXQsIHRvIGZpbmQgYW4gJHgkIHN1Y2ggdGhhdCAkZih4KSA9IG4kLiBJZiAkeCQgZXhpc3RzLCBpdCBpcyB1bmlxdWUuIE5vdGUgdGhhdCBmb3Igc29tZSBwb3NpdGl2ZSBpbnRlZ2VycyAkbiQsIG5vIHN1Y2ggJHgkIGV4aXN0cy4gRm9yIGV4YW1wbGUsIHRoZXJlIGlzIG5vIHBvc2l0aXZlIGludGVnZXIgJHgkIHN1Y2ggdGhhdCAkZih4KSA9IDMxMSQuIExpa2V3aXNlLCB0aGVyZSBpcyBubyBwb3NpdGl2ZSBpbnRlZ2VyICR4JCBzdWNoIHRoYXQgJGYoeCkgPSAxMTExJC4gSW4gdGhlIGNhc2Ugb2YgJDExMTEkLCBvbmUgbWlnaHQgaW50ZXJwcmV0IGl0IGFzICZsZHF1bztvbmUgJDEkLCBvbmUgJDEkJnJkcXVvOyBhbmQgdGhpbmsgJHggPSAxMSQsIGJ1dCAkZigxMSkgPSAyMSQuIFRodXMsIG5vIHBvc2l0aXZlIGludGVnZXIgY2FuIHByb2R1Y2UgJDExMTEkIGFjY29yZGluZyB0byB0aGUgJmxkcXVvO2xvb2stYW5kLXNheSZyZHF1bzsgcnVsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBoYXMgYSBsaW5lIGNvbnRhaW5pbmcgb25lIHBvc2l0aXZlIGludGVnZXIgJG4kIGxlc3MgdGhhbiAkMTBeezFcXCwwMDB9JC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIHdpdGggb25lIGludGVnZXIgJHgkIHN1Y2ggdGhhdCAkZih4KSA9IG4kLiBJZiBzdWNoICR4JCBkb2VzIG5vdCBleGlzdCwgcHJpbnQgJC0xJC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d