시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB349633.333%

문제

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

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

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

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

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

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

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

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

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

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

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

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

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

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

입력

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

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

출력

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

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

제한

  • 1 ≤ N ≤ 1,000,000

예제 입력 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+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkNCBcdWJiMzhcdWM4MWNcdWM3NTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIE5cdWM3NzQgLTFcdWM3N2MgXHVhY2JkXHVjNmIwIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWM4ODVcdWI4Y2NcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBOXHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwLCBLXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU2MCBcdWFjYmRcdWM2YjAgJnF1b3Q7TiBjb2NvbnV0cywgbWF4KEspIHBlb3BsZSBhbmQgMSBtb25rZXkmcXVvdDsgXHViOTdjLDxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWI1YTQgS1x1YjNjNCBcdWNmNTRcdWNmNTRcdWIxMWJcdWM3NDQgXHVhZGRjXHVjZTU5XHViMzAwXHViODVjIFx1YjA5OFx1YjIwYyBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YWNiZFx1YzZiMCAmcXVvdDtOIGNvY29udXRzLCBubyBzb2x1dGlvbiZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBOICZsZTsgMSwwMDAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiI2NDE3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ29jb251dHMsIFJldmlzaXRlZCIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHNob3J0IHN0b3J5IHRpdGxlZCBDb2NvbnV0cywgYnkgQmVuIEFtZXMgV2lsbGlhbXMsIGFwcGVhcmVkIGluIHRoZSBTYXR1cmRheSBFdmVuaW5nIFBvc3Qgb24gT2N0b2JlciA5LCAxOTI2LiBUaGUgc3RvcnkgdGVsbHMgYWJvdXQgZml2ZSBtZW4gYW5kIGEgbW9ua2V5IHdobyB3ZXJlIHNoaXB3cmVja2VkIG9uIGFuIGlzbGFuZC4gVGhleSBzcGVudCB0aGUgZmlyc3QgbmlnaHQgZ2F0aGVyaW5nIGNvY29udXRzLiBEdXJpbmcgdGhlIG5pZ2h0LCBvbmUgbWFuIHdva2UgdXAgYW5kIGRlY2lkZWQgdG8gdGFrZSBoaXMgc2hhcmUgb2YgdGhlIGNvY29udXRzLiBIZSBkaXZpZGVkIHRoZW0gaW50byBmaXZlIHBpbGVzLiBPbmUgY29jb251dCB3YXMgbGVmdCBvdmVyIHNvIGhlIGdhdmUgaXQgdG8gdGhlIG1vbmtleSwgdGhlbiBoaWQgaGlzIHNoYXJlIGFuZCB3ZW50IGJhY2sgdG8gc2hlZXAuPFwvcD5cclxuXHJcbjxwPlNvb24gYSBzZWNvbmQgbWFuIHdva2UgdXAgYW5kIGRpZCB0aGUgc2FtZSB0aGluZy4gQWZ0ZXIgZGl2aWRpbmcgdGhlIGNvY29udXRzIGludG8gZml2ZSBwaWxlcywgb25lIGNvY29udXQgd2FzIGxlZnQgb3ZlciB3aGljaCBoZSBnYXZlIHRvIHRoZSBtb25rZXkuIEhlIHRoZW4gaGlkIGhpcyBzaGFyZSBhbmQgd2VudCBiYWNrIHRvIGJlZC4gVGhlIHRoaXJkLCBmb3VydGgsIGFuZCBmaWZ0aCBtYW4gZm9sbG93ZWQgZXhhY3RseSB0aGUgc2FtZSBwcm9jZWR1cmUuIFRoZSBuZXh0IG1vcm5pbmcsIGFmdGVyIHRoZXkgYWxsIHdva2UgdXAsIHRoZXkgZGl2aWRlZCB0aGUgcmVtYWluaW5nIGNvY29udXRzIGludG8gZml2ZSBlcXVhbCBzaGFyZXMuIFRoaXMgdGltZSBubyBjb2NvbnV0cyB3ZXJlIGxlZnQgb3Zlci48XC9wPlxyXG5cclxuPHA+QW4gb2J2aW91cyBxdWVzdGlvbiBpcyAmcXVvdDtob3cgbWFueSBjb2NvbnV0cyBkaWQgdGhleSBvcmlnaW5hbGx5IGdhdGhlcj8mcXVvdDsgVGhlcmUgYXJlIGFuIGluZmluaXRlIG51bWJlciBvZiBhbnN3ZXJzLCBidXQgdGhlIGxvd2VzdCBvZiB0aGVzZSBpcyAzLDEyMS4gQnV0IHRoYXQmIzM5O3Mgbm90IG91ciBwcm9ibGVtIGhlcmUuPFwvcD5cclxuXHJcbjxwPlN1cHBvc2Ugd2UgdHVybiB0aGUgcHJvYmxlbSBhcm91bmQuIElmIHdlIGtub3cgdGhlIG51bWJlciBvZiBjb2NvbnV0cyB0aGF0IHdlcmUgZ2F0aGVyZWQsIHdoYXQgaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBlcnNvbnMgKGFuZCBvbmUgbW9ua2V5KSB0aGF0IGNvdWxkIGhhdmUgYmVlbiBzaGlwd3JlY2tlZCBpZiB0aGUgc2FtZSBwcm9jZWR1cmUgY291bGQgb2NjdXI/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgd2lsbCBjb25zaXN0IG9mIGEgc2VxdWVuY2Ugb2YgaW50ZWdlcnMsIGVhY2ggcmVwcmVzZW50aW5nIHRoZSBudW1iZXIgb2YgY29jb251dHMgZ2F0aGVyZWQgYnkgYSBncm91cCBvZiBwZXJzb25zIChhbmQgYSBtb25rZXkpIHRoYXQgd2VyZSBzaGlwd3JlY2tlZC4gVGhlIHNlcXVlbmNlIHdpbGwgYmUgZm9sbG93ZWQgYnkgJnF1b3Q7LTEmcXVvdDsuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbnVtYmVyIG9mIGNvY29udXRzLCBkZXRlcm1pbmUgdGhlIGxhcmdlc3QgbnVtYmVyIG9mIHBlcnNvbnMgd2hvIGNvdWxkIGhhdmUgcGFydGljaXBhdGVkIGluIHRoZSBwcm9jZWR1cmUgZGVzY3JpYmVkIGFib3ZlLiBEaXNwbGF5IHRoZSByZXN1bHRzIHNpbWlsYXIgdG8gdGhlIG1hbm5lciBzaG93biBiZWxvdywgaW4gdGhlIEV4cGVjdGVkIE91dHB1dC4gVGhlcmUgbWF5IGJlIG5vIHNvbHV0aW9uIGZvciBzb21lIG9mIHRoZSBpbnB1dCBjYXNlczsgaWYgc28sIHN0YXRlIHRoYXQgb2JzZXJ2YXRpb24uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgTiAmbGU7IDEsMDAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn1d

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 1997 3번