31066번 - 비 오는 날 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1091 | 437 | 402 | 42.903% |
문제
비 오는 날 $N$명의 학생이 창의인재관에서 융합인재관으로 건너가려고 한다. 창의인재관에는 $M$개의 우산이 있고, 융합인재관에는 우산이 없다. 한 우산은 한 번에 최대 $K$명까지 쓸 수 있다. 학생들은 다음 시행을 반복해 건너갈 수 있다.
- 한 건물에 있는 학생 중 몇 명이 우산을 쓰고 다른 건물로 넘어간다. 이때, 모두가 같은 우산을 쓸 필요는 없다.
- 아무도 쓰고 있지 않은 우산은 학생들이 제한 없이 들고 갈 수 있다. 예를 들어, 1명의 학생이 1개의 우산을 쓰고 3개의 우산을 들고 가는 것이 가능하다.
모든 학생이 비를 맞지 않고 융합인재관으로 건너갈 수 있는지 판별하여라. 만약 건너갈 수 있다면, 모든 학생이 건너가기 위한 시행의 최소 횟수를 구하여라. 단, 모든 우산을 융합인재관으로 가지고 올 필요는 없다.
엄밀히 말해, 4개의 정수로 이루어진 순서쌍 $(a,b,c,d)$가 주어진다. 이는 현재 창의인재관에 있는 학생이 $a$명, 창의인재관에 있는 우산이 $b$개, 융합인재관에 있는 학생이 $c$명, 융합인재관에 있는 우산이 $d$개라는 뜻이다. 초기에 $a=N$, $b=M$, $c=d=0$이며, 최소 횟수의 시행을 통해 $c=N$으로 만들어야 한다. 시행은 다음 행동 중 하나를 하는 것으로 정의된다.
- 두 양의 정수 $x$, $y$를 선택하여 순서쌍 $(a,b,c,d)$를 $(a-x,b-y,c+x,d+y)$로 바꾼다. 이는 창의인재관에서 $x$명의 학생이 $y$개의 우산을 이용하여 융합인재관으로 이동한다는 뜻이다. 이때, $0<x\le a$와 $0<y\le b$와 $x\le Ky$이어야 한다.
- 두 양의 정수 $z$, $w$를 선택하여 순서쌍 $(a,b,c,d)$를 $(a+z,b+w,c-z,d-w)$로 바꾼다. 이는 융합인재관에서 $z$명의 학생이 $w$개의 우산을 이용하여 창의인재관으로 이동한다는 뜻이다. 이때, $0<z\le c$와 $0<w\le d$와 $z\le Kw$이어야 한다.
입력
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.
다음 $T$개의 줄 중 $i$번째 줄에는 $i$번째 테스트 케이스를 나타내는 세 정수 $N$, $M$, $K$가 띄어쓰기를 사이에 두고 주어진다.
출력
$T$개의 줄에 걸쳐, $i$번째 줄에는 $i$번째 테스트 케이스의 답에 해당하는 정수 1개를 출력한다. 모든 학생이 융합인재관으로 건너갈 수 있다면 모든 학생이 건너가기 위한 시행의 최소 횟수를 출력하고, 그렇지 않다면 -1을 출력한다.
제한
- $1\le T\le 1\, 000$
- $1\le i\le T$
- $1\le N,M,K\le 10$
예제 입력 1
3 7 2 2 2 1 1 1 3 5
예제 출력 1
3 -1 1
출처
School > 서울과학고등학교 > SciOI 2023 A-1번
- 문제를 만든 사람: qwerasdfzxcl
- 문제를 검수한 사람: 79brue, ibm2006, mjhmjh1104, naeby, solvedac, utilforever, whqkrkt04
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호