시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 22 6 3 75.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

힌트

W3sicHJvYmxlbV9pZCI6IjY0MTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNmNTRcdWNmNTRcdWIxMWIgXHVhZGY4IFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWM3NzRcdWM1N2NcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPjE5MjZcdWIxNDQgMTBcdWM2ZDQgOVx1Yzc3Y1x1Yzc1OCBcdWMyZTBcdWJiMzhcdWM1ZDQgXHViYmY4XHVhZDZkXHVjNzU4IFx1YzcyMFx1YmE4NSBcdWFkZjlcdWM3OTFcdWFjMDAgXHViY2E0IFx1YzcwY1x1YjlhY1x1YzU1NFx1YzJhNFx1Yzc1OCBcdWM5ZTRcdWI5YzlcdWQ1NWMgXHViYjM4XHVjODFjIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWMyZTRcdWI4MzhcdWIyZTQuIFx1YzgwNFx1YmIzOFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1YjJlNFx1YzEyZiBcdWJhODVcdWM3NTggXHViMGE4XHVjNzkwXHVhYzAwIFx1YmIzNFx1Yzc3OFx1YjNjNFx1YzVkMCBcdWFjMDdcdWQ2MTRcdWIyZTQuIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWQ0NWNcdWI5NTggXHVjY2FiIFx1YjBhMCwgXHVkNTU4XHViOGU4IFx1Yzg4NVx1Yzc3YyBcdWQ3OThcdWM3NDQgXHVkNTY5XHVjY2QwIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWJhYThcdWM1NThcdWIyZTQuIDxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWFkZjhcdWIwYTAgXHViYzI0IFx1Y2NhYiBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWMxMzhcdWM1YjRcdWJjZjRcdWIyYzggXHVkNTU4XHViMDk4XHViOTdjIFx1YmU3Y1x1YmE3NCBcdWM4MTVcdWQ2NTVcdWQ3ODggNVx1YjRmMVx1YmQ4NFx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzVjOFx1YjJlNC48XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVhZGY4XHViNzk4XHVjMTFjIFx1YzljMFx1YjA5OFx1YWMwMFx1YjM1OCBcdWM2ZDBcdWMyMmRcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjZjU0XHVjZjU0XHViMTFiIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM4ZmNcdWFjZTAgXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIDVcdWI0ZjFcdWJkODRcdWQ1NThcdWM1ZWMgXHVjNzkwXHVhZTMwIFx1YmFhYlx1Yzc1OCBcdWQ1NWMgXHViYjM0XHViMzU0XHVhZTMwXHViOTdjIFx1YzIyOFx1YWNhOCBcdWI0NTBcdWFjZTAgXHVjN2EwXHViNGU0XHVjNWM4XHViMmU0LiA8XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVhZGY4XHViOWFjXHVhY2UwIFx1YmMxNFx1Yjg1YyBcdWFkZjggXHVjOWMxXHVkNmM0LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3N2NcdWM1YjRcdWIwOTggXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YzEzOFx1YzViNFx1YmNmNFx1YjJjOCBcdWQ1NThcdWIwOThcdWI5N2MgXHViZTdjXHViYTc0IFx1YzgxNVx1ZDY1NVx1ZDc4OCA1XHViNGYxXHViZDg0XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNWM4XHViMmU0LjxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWFkZjhcdWI3OThcdWMxMWMgXHVjOWMwXHViMDk4XHVhYzAwXHViMzU4IFx1YzZkMFx1YzIyZFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWNmNTRcdWNmNTRcdWIxMWIgXHVkNTU4XHViMDk4XHViOTdjIFx1YzhmY1x1YWNlMCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgNVx1YjRmMVx1YmQ4NFx1ZDU1OFx1YzVlYyBcdWM3OTBcdWFlMzAgXHViYWFiXHVjNzU4IFx1ZDU1YyBcdWJiMzRcdWIzNTRcdWFlMzBcdWI5N2MgXHVjMjI4XHVhY2E4IFx1YjQ1MFx1YWNlMCBcdWM3YTBcdWI0ZTRcdWM1YzhcdWIyZTQuIDxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWFkZjggXHViYzE0XHViODVjIFx1YjJlNFx1Yzc0YyBcdWMxMzggXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1YjNjNCwgXHViMTI0IFx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWIzYzQsIFx1YjJlNFx1YzEyZiBcdWJjODhcdWM5ZjggXHVjMGFjXHViNzhjXHViM2M0IFx1YWMxOVx1Yzc0MCBcdWM3N2NcdWM3NDQgXHVkNTg4XHViMmU0LiA8XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+XHVjNzc0XHVjODFjIFx1YzdhMFx1YzVkMFx1YzExYyBcdWFlNmMgXHViMmU0XHVjMTJmIFx1YmE4NVx1Yzc3NCBcdWIwYThcdWM3NDAgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YzEzOFx1YzViNCBcdWJjZjRcdWIyYzggXHVjODE1XHVkNjU1XHVkNzg4IDVcdWI0ZjFcdWJkODRcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM1YzhcdWIyZTQuIDxcL3N0cm9uZz48XC9wPlxyXG5cclxuPHA+PHN0cm9uZz5cdWFkZjhcdWI3OThcdWMxMWMgXHVhZGY4XHViNGU0XHVjNzQwIFx1YjBhOFx1Yzc0MCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgNVx1YjRmMVx1YmQ4NFx1ZDU1OFx1YzVlYyBcdWQ1NWMgXHViYjM2XHVjNzRjXHVjNTI5IFx1YWMwMFx1Yzg0Y1x1YjJlNC4gPFwvc3Ryb25nPjxcL3A+XHJcblxyXG48cD48c3Ryb25nPlx1Yzc3NCBcdWI1NGMsIFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWNjOThcdWM3NGMgXHViYWE4XHVjNzQwIFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0MCBcdWJhYThcdWI0NTAgXHViYTg3IFx1YWMxY1x1YzYwMFx1Yzc0NFx1YWU0Yz88XC9zdHJvbmc+PFwvcD5cclxuXHJcbjxwPlx1YmIzOFx1YzgxY1x1Yzc1OCBcdWIyZjVcdWM3NDAgXHVjMGFjXHVjMmU0IFx1YmIzNFx1YzIxOFx1ZDc4OCBcdWI5Y2VcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWFkZjggXHVjOTExIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMjE4XHViMjk0IDMxMjFcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzQgXHViYjM4XHVjODFjXHViMjk0IFx1YzZiMFx1YjlhY1x1YWMwMCBcdWQ0ODAgXHViYjM4XHVjODFjXHVhYzAwIFx1YzU0NFx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1Y2Y1NFx1Y2Y1NFx1YjExYiBcdWM3NzRcdWM1N2NcdWFlMzBcdWI5N2MgXHViYzE4XHViMzAwXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1YWUzMFx1Yjg1YyBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Y2M5OFx1Yzc0YyBcdWJhYThcdWM3NDAgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzc0IE5cdWFjMWNcdWM2MDBcdWFjZTAsIFx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWIzMDBcdWI4NWMgS1x1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjZjU0XHVjZjU0XHViMTFiXHVjNzQ0IFx1YjJlNFx1YjRlNCBcdWIwOThcdWIyMDRcdWM1YjQgXHVhYzAwXHVjOWMwXHViMjk0IFx1YjM3MCBcdWMxMzFcdWFjZjVcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1Yzc3NCBcdWI1NGMgS1x1YjI5NCBcdWNkNWNcdWIzMDAgXHViYTg3XHVjNzc0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDQgXHViYjM4XHVjODFjXHVjNzU4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBOXHVjNzc0IFx1Yzc0Y1x1YzIxOFx1Yzc3YyBcdWFjYmRcdWM2YjAgXHVjNzg1XHViODI1XHVjNzU4IFx1Yzg4NVx1YjhjY1x1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIE5cdWM1ZDAgXHViNTMwXHViNzdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAsIEtcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTYwIFx1YWNiZFx1YzZiMCAmcXVvdDtOIGNvY29udXRzLCBtYXgoSykgcGVvcGxlIGFuZCAxIG1vbmtleSZxdW90OyBcdWI5N2MsPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBLXHViM2M0IFx1Y2Y1NFx1Y2Y1NFx1YjExYlx1Yzc0NCBcdWFkZGNcdWNlNTlcdWIzMDBcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM1YzZcdWM3NDQgXHVhY2JkXHVjNmIwICZxdW90O04gY29jb251dHMsIG5vIHNvbHV0aW9uJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NDE3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29jb251dHMsIFJldmlzaXRlZCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHNob3J0IHN0b3J5IHRpdGxlZCBDb2NvbnV0cywgYnkgQmVuIEFtZXMgV2lsbGlhbXMsIGFwcGVhcmVkIGluIHRoZSBTYXR1cmRheSBFdmVuaW5nIFBvc3Qgb24gT2N0b2JlciA5LCAxOTI2LiBUaGUgc3RvcnkgdGVsbHMgYWJvdXQgZml2ZSBtZW4gYW5kIGEgbW9ua2V5IHdobyB3ZXJlIHNoaXB3cmVja2VkIG9uIGFuIGlzbGFuZC4gVGhleSBzcGVudCB0aGUgZmlyc3QgbmlnaHQgZ2F0aGVyaW5nIGNvY29udXRzLiBEdXJpbmcgdGhlIG5pZ2h0LCBvbmUgbWFuIHdva2UgdXAgYW5kIGRlY2lkZWQgdG8gdGFrZSBoaXMgc2hhcmUgb2YgdGhlIGNvY29udXRzLiBIZSBkaXZpZGVkIHRoZW0gaW50byBmaXZlIHBpbGVzLiBPbmUgY29jb251dCB3YXMgbGVmdCBvdmVyIHNvIGhlIGdhdmUgaXQgdG8gdGhlIG1vbmtleSwgdGhlbiBoaWQgaGlzIHNoYXJlIGFuZCB3ZW50IGJhY2sgdG8gc2hlZXAuPFwvcD5cclxuXHJcbjxwPlNvb24gYSBzZWNvbmQgbWFuIHdva2UgdXAgYW5kIGRpZCB0aGUgc2FtZSB0aGluZy4gQWZ0ZXIgZGl2aWRpbmcgdGhlIGNvY29udXRzIGludG8gZml2ZSBwaWxlcywgb25lIGNvY29udXQgd2FzIGxlZnQgb3ZlciB3aGljaCBoZSBnYXZlIHRvIHRoZSBtb25rZXkuIEhlIHRoZW4gaGlkIGhpcyBzaGFyZSBhbmQgd2VudCBiYWNrIHRvIGJlZC4gVGhlIHRoaXJkLCBmb3VydGgsIGFuZCBmaWZ0aCBtYW4gZm9sbG93ZWQgZXhhY3RseSB0aGUgc2FtZSBwcm9jZWR1cmUuIFRoZSBuZXh0IG1vcm5pbmcsIGFmdGVyIHRoZXkgYWxsIHdva2UgdXAsIHRoZXkgZGl2aWRlZCB0aGUgcmVtYWluaW5nIGNvY29udXRzIGludG8gZml2ZSBlcXVhbCBzaGFyZXMuIFRoaXMgdGltZSBubyBjb2NvbnV0cyB3ZXJlIGxlZnQgb3Zlci48XC9wPlxyXG5cclxuPHA+QW4gb2J2aW91cyBxdWVzdGlvbiBpcyAmcXVvdDtob3cgbWFueSBjb2NvbnV0cyBkaWQgdGhleSBvcmlnaW5hbGx5IGdhdGhlcj8mcXVvdDsgVGhlcmUgYXJlIGFuIGluZmluaXRlIG51bWJlciBvZiBhbnN3ZXJzLCBidXQgdGhlIGxvd2VzdCBvZiB0aGVzZSBpcyAzLDEyMS4gQnV0IHRoYXQmIzM5O3Mgbm90IG91ciBwcm9ibGVtIGhlcmUuPFwvcD5cclxuXHJcbjxwPlN1cHBvc2Ugd2UgdHVybiB0aGUgcHJvYmxlbSBhcm91bmQuIElmIHdlIGtub3cgdGhlIG51bWJlciBvZiBjb2NvbnV0cyB0aGF0IHdlcmUgZ2F0aGVyZWQsIHdoYXQgaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBlcnNvbnMgKGFuZCBvbmUgbW9ua2V5KSB0aGF0IGNvdWxkIGhhdmUgYmVlbiBzaGlwd3JlY2tlZCBpZiB0aGUgc2FtZSBwcm9jZWR1cmUgY291bGQgb2NjdXI/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgd2lsbCBjb25zaXN0IG9mIGEgc2VxdWVuY2Ugb2YgaW50ZWdlcnMsIGVhY2ggcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgY29jb251dHMgZ2F0aGVyZWQgYnkgYSBncm91cCBvZiBwZXJzb25zIChhbmQgYSBtb25rZXkpIHRoYXQgd2VyZSBzaGlwd3JlY2tlZC4gVGhlIHNlcXVlbmNlIHdpbGwgYmUgZm9sbG93ZWQgYnkgYSBuZWdhdGl2ZSBudW1iZXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbnVtYmVyIG9mIGNvY29udXRzLCBkZXRlcm1pbmUgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHBlcnNvbnMgd2hvIGNvdWxkIGhhdmUgcGFydGljaXBhdGVkIGluIHRoZSBwcm9jZWR1cmUgZGVzY3JpYmVkIGFib3ZlLiBEaXNwbGF5IHRoZSByZXN1bHRzIHNpbWlsYXIgdG8gdGhlIG1hbm5lciBzaG93biBiZWxvdywgaW4gdGhlIEV4cGVjdGVkIE91dHB1dC4gVGhlcmUgbWF5IGJlIG5vIHNvbHV0aW9uIGZvciBzb21lIG9mIHRoZSBpbnB1dCBjYXNlczsgaWYgc28sIHN0YXRlIHRoYXQgb2JzZXJ2YXRpb24uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d