6417번 - 코코넛 그 두 번째 이야기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 143 | 47 | 32 | 33.684% |
문제
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
출처
ICPC > Regionals > North America > North Central North America Regional > NCNA 1997 3번
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호