시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 1 1 100.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"을 출력한다.

예제 입력

25
30
3121
-1

예제 출력

25 coconuts, 3 people and 1 monkey
30 coconuts, no solution
3121 coconuts, 5 people and 1 monkey

힌트