시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 14 | 12 | 12 | 85.714% |
"Summer is finally here: time to relax, have some fun, go outside and enjoy the nice weather!" says Alice, a very dedicated Ranger working in a popular National Park. During the summer, lots of families take some time off to camp there and have a good time, and it is Alice's job to accommodate the visitors.
Alice is in charge of one of the many camps around the park. The camp can be described as a matrix of size N x N, where each cell has enough space for at most one tent. In order to arrange the families in the camp, there are several regulations that Alice needs to follow:
Additionally, Alice knows in advance that at least X three-member families will be visiting the camp, and that there will be enough one- or two-member families to fill the rest of the camp.
For example, these are valid arrangements for N = 3 and X = 0:
1 2 0 | 3 0 0 0 1 2 | 0 1 2 2 0 1 | 0 2 1
These are not valid arrangements for N = 3 and X = 1:
1 2 0 | 0 3 0 | 1 2 0 | 1 1 1 0 1 2 | 3 0 0 | 0 2 0 | 1 1 1 2 0 1 | 0 0 0 | 2 0 1 | 1 1 1
Finally, Alice likes to keep things interesting. She would like to know how many different arrangements are possible given N and X.
Two arrangements A and B are considered different, if a cell in one arrangement contains a tent, but the same cell in the other arrangement doesn't; or if there is a tent in the same cell of both arrangements, but the number of members in that cell in A is different than the number of members in the same cell in B.
The first line of the input contains T, the number of test cases. T test cases follow. Each test case consists of exactly one line with two integers N and X corresponding to the number of rows (and columns) in Alice's camp and the minimum number of three-member families, respectively.
For each test case, output one line containing "Case #X: Y", where X is the test case number (starting from 1) and Y is the number of possible arrangements.
The answer may be huge, so output the answer modulo 109 + 7.
3 2 2 3 1 15 0
Case #1: 2 Case #2: 24 Case #3: 738721209
In case #1, you have two different valid arrangements:
0 3 | 3 0 3 0 | 0 3
Contest > Google > Code Jam > Google Code Jam 2015 > World Finals B1번