시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 0 | 0 | 0 | 0.000% |
계단에 그림과 같이 검은색 혹은 흰색 모자를 쓴 아이들이 서 있다. 아이들은 계단 아래쪽만 볼 수 있고 전체 검은색 모자와 흰색 모자의 개수를 각각 알고 있다. 아이들보다 모자가 많아서, 모자가 남을 수 있는데, 이 경우 아이들이 쓰고 있지 않은 모자는 인솔자가 감추고 있다. 인솔자는 계단 맨 위에 있는 아이부터 차례차례 자신이 쓰고 있는 모자의 색을 알 수 있는지 물어보았고, 한 아이가 정답을 맞혔다. (즉 자신이 쓰고 있는 모자의 색을 맞혔다.) 정답을 맞힌 아이가 나온 후에는 그 앞에 있는 아이들에게는 더 이상 물어보지 않았다.
위 그림은 3명의 아이가 검은색/흰색 모자가 각각 2개인 상황에 뒤에서부터 2번째 아이가 정답을 말한 경우이다.
당신은 이 상황에 대해 친구에게 전해 들었다. 친구는 상황이 정확히 어땠는지는 기억하지 못하고, 다만 아이들의 수와 검은색/흰색 모자의 수, 그리고 뒤에서 몇 번째 아이가 답을 맞혔는지만 알려주었다. 당신은 친구가 얘기해 준 정보에 맞는 경우의 수가 궁금해졌다. 이 경우의 수는 물론 매우 클 수 있기 때문에 32749로 나눈 나머지를 구하기로 한다.
입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 아래로 T 줄의 입력이 주어지며 각 줄은 하나의 테스트 케이스에 대한 입력이다. 각 테스트 케이스는 아래와 같이 4개의 자연수로 주어진다.
B W k i
여기에서 B와 W는 각각 검은색 모자와 흰색 모자의 수, k는 아이들의 수, 그리고 i는 뒤에서 몇 번째 아이가 맞췄는지를 나타낸다.
각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 주어진 조건에 맞는 경우의 수를 32749로 나눈 나머지이다.
3 2 2 3 2 2 4 6 1 0 7 5 1
Case #1: 4 Case #2: 15 Case #3: 1
Contest > Google > Google's Coding Competitions > Google Code Jam Korea 2012 > Code Jam Korea 2012 본선 라운드 C2번