10435번 - 만칼라 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 153 | 98 | 72 | 61.538% |
문제
만칼라는 보드 게임의 한 종류로, 여러 변형 판이 존재한다.
그 중 가장 간단한 종류인 1인용 만칼라 게임 Tchoukaillon에 대해 살펴볼 것이다.
Tchoukaillon는 여러 개의 빈칸과 하나의 Roumba로 이루어진 보드 위에서 진행된다.
가장 왼쪽의 빈칸은 Roumba이며, 처음엔 항상 비어있는 상태여야 한다.
게임은 다음과 같이 진행된다. 우선, 각 칸을 B[N]이라 할 때, B[N]에 N개의 구슬이 들어 있는 칸을 찾는다. 그런 칸이 여러 개라면 아무 것이나 선택해도 상관없다. 만일 B[N]=N인 칸이 없다면 그 판은 패배이다.
위의 예제에서는 맨 첫 줄을 보면 된다. 3번 칸을 선택한 상황이다.
이제 고른 칸의 구슬을 Roumba와 B[1], B[2], ... , B[N-1]에 하나씩 고르게 나누어준다.
위의 시행을 계속 반복하여 모든 구슬이 Roumba로 들어간다면 게임을 성공적으로 마치게 되는 것이고, 이처럼 성공이 가능한 모든 게임판을 승리하는 게임판이라고 한다. 모든 정수 N에 대해, 구슬이 총 N개일 때의 승리하는 게임판은 항상 유일하다. 따라서 위에서의 Roumba를 뺀 보드판의 초기 상태 { 0, 1, 3 } 은 구슬이 4개일 때의 유일한 승리하는 게임판이다.
총 구슬의 개수 N이 주어지면 승리하는 게임판을 출력하라.
입력
첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)
각 테스트 케이스는 테스트 케이스의 번호 T와 보드판에 들어갈 구슬의 총 개수 N으로 이루어져 있다.
출력
각 테스트 케이스마다 첫 줄에 테스트 케이스의 번호 T와 구슬이 하나 이상 담겨 있는 보드판의 마지막 위치 B를 출력한다.
그 후 승리하는 게임판의 상태를 B개의 정수로 출력하는데, 수는 10개 단위로 끊어서 출력해야 한다.
모든 테스트 케이스에서 B는 80을 넘지 않는다.
예제 입력 1
3 1 4 2 57 3 500
예제 출력 1
1 3 0 1 3 2 12 1 2 2 2 2 6 2 4 6 8 10 12 3 39 0 2 2 1 3 2 2 2 6 7 5 0 6 12 2 6 10 14 18 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
출처
ICPC > Regionals > North America > Greater New York Region > 2014 Greater New York Programming Contest E번
- 문제를 번역한 사람: portableangel
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호