시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 7 4 50.000%

문제

1926년 10월 9일의 신문엔 미국의 유명 극작가 벤 윌리암스의 짤막한 문제 하나가 실렸다. 전문은 다음과 같다.

다섯 명의 남자가 무인도에 갇혔다. 그들은 표류 첫 날, 하루 종일 힘을 합쳐 코코넛을 모았다.

그날 밤 첫 사람이 일어나 코코넛을 세어보니 하나를 빼면 정확히 5등분을 할 수 있었다.

그래서 지나가던 원숭이에게 코코넛 하나를 주고 나머지를 5등분하여 자기 몫의 한 무더기를 숨겨 두고 잠들었다.

그리고 바로 그 직후, 두 번째 사람이 일어나 코코넛을 세어보니 하나를 빼면 정확히 5등분을 할 수 있었다.

그래서 지나가던 원숭이에게 코코넛 하나를 주고 나머지를 5등분하여 자기 몫의 한 무더기를 숨겨 두고 잠들었다.

그 바로 다음 세 번째 사람도, 네 번째 사람도, 다섯 번째 사람도 같은 일을 했다.

이제 잠에서 깬 다섯 명이 남은 코코넛을 세어 보니 정확히 5등분을 할 수 있었다.

그래서 그들은 남은 코코넛을 5등분하여 한 묶음씩 가졌다.

이때, 그들이 처음 모은 코코넛은 모두 몇 개였을까?

문제의 답은 사실 무수히 많다. 하지만 그 중 가장 작은 수는 3121개이다.

하지만 이 문제는 우리가 풀 문제가 아니다.

우리는 코코넛 이야기를 반대로 생각해보기로 하자.

처음 모은 코코넛이 N개였고, 위의 규칙대로 K명의 사람들이 코코넛을 다들 나누어 가지는 데 성공했다면, 이때 K는 최대 몇이 될 수 있을까?

입력

입력은 여러 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫 줄엔 문제의 N이 주어지며, N이 음수일 경우 입력의 종료를 의미한다.

출력

각 N에 따라 한 줄에, K가 존재할 경우 "N coconuts, max(K) people and 1 monkey" 를,

어떤 K도 코코넛을 규칙대로 나눌 수 없을 경우 "N coconuts, no solution"을 출력한다.

예제 입력 1

25
30
3121
-1

예제 출력 1

25 coconuts, 3 people and 1 monkey
30 coconuts, no solution
3121 coconuts, 5 people and 1 monkey
W3sicHJvYmxlbV9pZCI6IjY0MTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWNmNTRcdWIxMWIgXHVhZGY4IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjNzc0XHVjNTdjXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4xOTI2XHViMTQ0IDEwXHVjNmQ0IDlcdWM3N2NcdWM3NTggXHVjMmUwXHViYjM4XHVjNWQ0IFx1YmJmOFx1YWQ2ZFx1Yzc1OCBcdWM3MjBcdWJhODUgXHVhZGY5XHVjNzkxXHVhYzAwIFx1YmNhNCBcdWM3MGNcdWI5YWNcdWM1NTRcdWMyYTRcdWM3NTggXHVjOWU0XHViOWM5XHVkNTVjIFx1YmIzOFx1YzgxYyBcdWQ1NThcdWIwOThcdWFjMDAgXHVjMmU0XHViODM4XHViMmU0LiBcdWM4MDRcdWJiMzhcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWIyZTRcdWMxMmYgXHViYTg1XHVjNzU4IFx1YjBhOFx1Yzc5MFx1YWMwMCBcdWJiMzRcdWM3NzhcdWIzYzRcdWM1ZDAgXHVhYzA3XHVkNjE0XHViMmU0LiBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVkNDVjXHViOTU4IFx1Y2NhYiBcdWIwYTAsIFx1ZDU1OFx1YjhlOCBcdWM4ODVcdWM3N2MgXHVkNzk4XHVjNzQ0IFx1ZDU2OVx1Y2NkMCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHViYWE4XHVjNTU4XHViMmU0LiA8XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVhZGY4XHViMGEwIFx1YmMyNCBcdWNjYWIgXHVjMGFjXHViNzhjXHVjNzc0IFx1Yzc3Y1x1YzViNFx1YjA5OCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHVjMTM4XHVjNWI0XHViY2Y0XHViMmM4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWJlN2NcdWJhNzQgXHVjODE1XHVkNjU1XHVkNzg4IDVcdWI0ZjFcdWJkODRcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM1YzhcdWIyZTQuPFwvc3Ryb25nPjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1YWRmOFx1Yjc5OFx1YzExYyBcdWM5YzBcdWIwOThcdWFjMDBcdWIzNTggXHVjNmQwXHVjMjJkXHVjNzc0XHVjNWQwXHVhYzhjIFx1Y2Y1NFx1Y2Y1NFx1YjExYiBcdWQ1NThcdWIwOThcdWI5N2MgXHVjOGZjXHVhY2UwIFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyA1XHViNGYxXHViZDg0XHVkNTU4XHVjNWVjIFx1Yzc5MFx1YWUzMCBcdWJhYWJcdWM3NTggXHVkNTVjIFx1YmIzNFx1YjM1NFx1YWUzMFx1Yjk3YyBcdWMyMjhcdWFjYTggXHViNDUwXHVhY2UwIFx1YzdhMFx1YjRlNFx1YzVjOFx1YjJlNC4gPFwvc3Ryb25nPjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWJjMTRcdWI4NWMgXHVhZGY4IFx1YzljMVx1ZDZjNCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWMxMzhcdWM1YjRcdWJjZjRcdWIyYzggXHVkNTU4XHViMDk4XHViOTdjIFx1YmU3Y1x1YmE3NCBcdWM4MTVcdWQ2NTVcdWQ3ODggNVx1YjRmMVx1YmQ4NFx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzVjOFx1YjJlNC48XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVhZGY4XHViNzk4XHVjMTFjIFx1YzljMFx1YjA5OFx1YWMwMFx1YjM1OCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjZjU0XHVjZjU0XHViMTFiIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM4ZmNcdWFjZTAgXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIDVcdWI0ZjFcdWJkODRcdWQ1NThcdWM1ZWMgXHVjNzkwXHVhZTMwIFx1YmFhYlx1Yzc1OCBcdWQ1NWMgXHViYjM0XHViMzU0XHVhZTMwXHViOTdjIFx1YzIyOFx1YWNhOCBcdWI0NTBcdWFjZTAgXHVjN2EwXHViNGU0XHVjNWM4XHViMmU0LiA8XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVhZGY4IFx1YmMxNFx1Yjg1YyBcdWIyZTRcdWM3NGMgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWIzYzQsIFx1YjEyNCBcdWJjODhcdWM5ZjggXHVjMGFjXHViNzhjXHViM2M0LCBcdWIyZTRcdWMxMmYgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1YjNjNCBcdWFjMTlcdWM3NDAgXHVjNzdjXHVjNzQ0IFx1ZDU4OFx1YjJlNC4gPFwvc3Ryb25nPjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1Yzc3NFx1YzgxYyBcdWM3YTBcdWM1ZDBcdWMxMWMgXHVhZTZjIFx1YjJlNFx1YzEyZiBcdWJhODVcdWM3NzQgXHViMGE4XHVjNzQwIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWMxMzhcdWM1YjQgXHViY2Y0XHViMmM4IFx1YzgxNVx1ZDY1NVx1ZDc4OCA1XHViNGYxXHViZDg0XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNWM4XHViMmU0LiA8XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVhZGY4XHViNzk4XHVjMTFjIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWIwYThcdWM3NDAgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IDVcdWI0ZjFcdWJkODRcdWQ1NThcdWM1ZWMgXHVkNTVjIFx1YmIzNlx1Yzc0Y1x1YzUyOSBcdWFjMDBcdWM4NGNcdWIyZTQuIDxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWM3NzRcdWI1NGMsIFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWNjOThcdWM3NGMgXHViYWE4XHVjNzQwIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0MCBcdWJhYThcdWI0NTAgXHViYTg3IFx1YWMxY1x1YzYwMFx1Yzc0NFx1YWU0Yz88XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1Yzc1OCBcdWIyZjVcdWM3NDAgXHVjMGFjXHVjMmU0IFx1YmIzNFx1YzIxOFx1ZDc4OCBcdWI5Y2VcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWFkZjggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHViMjk0IDMxMjFcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzQgXHViYjM4XHVjODFjXHViMjk0IFx1YzZiMFx1YjlhY1x1YWMwMCBcdWQ0ODAgXHViYjM4XHVjODFjXHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1Y2Y1NFx1Y2Y1NFx1YjExYiBcdWM3NzRcdWM1N2NcdWFlMzBcdWI5N2MgXHViYzE4XHViMzAwXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Y2M5OFx1Yzc0YyBcdWJhYThcdWM3NDAgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzc0IE5cdWFjMWNcdWM2MDBcdWFjZTAsIFx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWIzMDBcdWI4NWMgS1x1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjJlNFx1YjRlNCBcdWIwOThcdWIyMDRcdWM1YjQgXHVhYzAwXHVjOWMwXHViMjk0IFx1YjM3MCBcdWMxMzFcdWFjZjVcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1Yzc3NFx1YjU0YyBLXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWJhODdcdWM3NzQgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWM3NDRcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkNCBcdWJiMzhcdWM4MWNcdWM3NTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIE5cdWM3NzQgXHVjNzRjXHVjMjE4XHVjNzdjIFx1YWNiZFx1YzZiMCBcdWM3ODVcdWI4MjVcdWM3NTggXHVjODg1XHViOGNjXHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgTlx1YzVkMCBcdWI1MzBcdWI3N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCwgS1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHVhY2JkXHVjNmIwICZxdW90O04gY29jb251dHMsIG1heChLKSBwZW9wbGUgYW5kIDEgbW9ua2V5JnF1b3Q7IFx1Yjk3Yyw8XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IEtcdWIzYzQgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YWRkY1x1Y2U1OVx1YjMwMFx1Yjg1YyBcdWIwOThcdWIyMGMgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWFjYmRcdWM2YjAgJnF1b3Q7TiBjb2NvbnV0cywgbm8gc29sdXRpb24mcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY0MTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb2NvbnV0cywgUmV2aXNpdGVkIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgc2hvcnQgc3RvcnkgdGl0bGVkIENvY29udXRzLCBieSBCZW4gQW1lcyBXaWxsaWFtcywgYXBwZWFyZWQgaW4gdGhlIFNhdHVyZGF5IEV2ZW5pbmcgUG9zdCBvbiBPY3RvYmVyIDksIDE5MjYuIFRoZSBzdG9yeSB0ZWxscyBhYm91dCBmaXZlIG1lbiBhbmQgYSBtb25rZXkgd2hvIHdlcmUgc2hpcHdyZWNrZWQgb24gYW4gaXNsYW5kLiBUaGV5IHNwZW50IHRoZSBmaXJzdCBuaWdodCBnYXRoZXJpbmcgY29jb251dHMuIER1cmluZyB0aGUgbmlnaHQsIG9uZSBtYW4gd29rZSB1cCBhbmQgZGVjaWRlZCB0byB0YWtlIGhpcyBzaGFyZSBvZiB0aGUgY29jb251dHMuIEhlIGRpdmlkZWQgdGhlbSBpbnRvIGZpdmUgcGlsZXMuIE9uZSBjb2NvbnV0IHdhcyBsZWZ0IG92ZXIgc28gaGUgZ2F2ZSBpdCB0byB0aGUgbW9ua2V5LCB0aGVuIGhpZCBoaXMgc2hhcmUgYW5kIHdlbnQgYmFjayB0byBzaGVlcC48XC9wPlxyXG5cclxuPHA+U29vbiBhIHNlY29uZCBtYW4gd29rZSB1cCBhbmQgZGlkIHRoZSBzYW1lIHRoaW5nLiBBZnRlciBkaXZpZGluZyB0aGUgY29jb251dHMgaW50byBmaXZlIHBpbGVzLCBvbmUgY29jb251dCB3YXMgbGVmdCBvdmVyIHdoaWNoIGhlIGdhdmUgdG8gdGhlIG1vbmtleS4gSGUgdGhlbiBoaWQgaGlzIHNoYXJlIGFuZCB3ZW50IGJhY2sgdG8gYmVkLiBUaGUgdGhpcmQsIGZvdXJ0aCwgYW5kIGZpZnRoIG1hbiBmb2xsb3dlZCBleGFjdGx5IHRoZSBzYW1lIHByb2NlZHVyZS4gVGhlIG5leHQgbW9ybmluZywgYWZ0ZXIgdGhleSBhbGwgd29rZSB1cCwgdGhleSBkaXZpZGVkIHRoZSByZW1haW5pbmcgY29jb251dHMgaW50byBmaXZlIGVxdWFsIHNoYXJlcy4gVGhpcyB0aW1lIG5vIGNvY29udXRzIHdlcmUgbGVmdCBvdmVyLjxcL3A+XHJcblxyXG48cD5BbiBvYnZpb3VzIHF1ZXN0aW9uIGlzICZxdW90O2hvdyBtYW55IGNvY29udXRzIGRpZCB0aGV5IG9yaWdpbmFsbHkgZ2F0aGVyPyZxdW90OyBUaGVyZSBhcmUgYW4gaW5maW5pdGUgbnVtYmVyIG9mIGFuc3dlcnMsIGJ1dCB0aGUgbG93ZXN0IG9mIHRoZXNlIGlzIDMsMTIxLiBCdXQgdGhhdCYjMzk7cyBub3Qgb3VyIHByb2JsZW0gaGVyZS48XC9wPlxyXG5cclxuPHA+U3VwcG9zZSB3ZSB0dXJuIHRoZSBwcm9ibGVtIGFyb3VuZC4gSWYgd2Uga25vdyB0aGUgbnVtYmVyIG9mIGNvY29udXRzIHRoYXQgd2VyZSBnYXRoZXJlZCwgd2hhdCBpcyB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGVyc29ucyAoYW5kIG9uZSBtb25rZXkpIHRoYXQgY291bGQgaGF2ZSBiZWVuIHNoaXB3cmVja2VkIGlmIHRoZSBzYW1lIHByb2NlZHVyZSBjb3VsZCBvY2N1cj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCB3aWxsIGNvbnNpc3Qgb2YgYSBzZXF1ZW5jZSBvZiBpbnRlZ2VycywgZWFjaCByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBjb2NvbnV0cyBnYXRoZXJlZCBieSBhIGdyb3VwIG9mIHBlcnNvbnMgKGFuZCBhIG1vbmtleSkgdGhhdCB3ZXJlIHNoaXB3cmVja2VkLiBUaGUgc2VxdWVuY2Ugd2lsbCBiZSBmb2xsb3dlZCBieSBhIG5lZ2F0aXZlIG51bWJlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBudW1iZXIgb2YgY29jb251dHMsIGRldGVybWluZSB0aGUgbGFyZ2VzdCBudW1iZXIgb2YgcGVyc29ucyB3aG8gY291bGQgaGF2ZSBwYXJ0aWNpcGF0ZWQgaW4gdGhlIHByb2NlZHVyZSBkZXNjcmliZWQgYWJvdmUuIERpc3BsYXkgdGhlIHJlc3VsdHMgc2ltaWxhciB0byB0aGUgbWFubmVyIHNob3duIGJlbG93LCBpbiB0aGUgRXhwZWN0ZWQgT3V0cHV0LiBUaGVyZSBtYXkgYmUgbm8gc29sdXRpb24gZm9yIHNvbWUgb2YgdGhlIGlucHV0IGNhc2VzOyBpZiBzbywgc3RhdGUgdGhhdCBvYnNlcnZhdGlvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=