시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 14 | 9 | 9 | 75.000% |
The king has hired you to make him an elegant diamond. An elegant diamond is a two-dimensional object made out of digits that's symmetric about a horizontal and a vertical axis. For example, the following four shapes are elegant diamonds:
2 8 3 7 3 3 8 8 2 2 4 1 4 8 3 3 3 2
These three shapes are diamonds, but are not elegant:
2 1 3 1 1 1 2 1 1 1 1 1 1 3 1 3 2 1 1 1 1 2
These three shapes are not diamonds:
1 2 8 8 1 1 222 0 2 00000
The king will start by giving you a diamond, which may not be elegant. Your job is to make it elegant by enhancing it, adding digits on to make a bigger diamond. Because you don't want to spend too much money, you want to do it with as little cost as possible.
A diamond of size k is 2k-1 lines of digits, 0-9, separated by single spaces, organized in the following way:
An elegant diamond of size k is a diamond of size k with the following two symmetry properties:
A diamond of size k can be enhanced by adding digits to it. The result of enhancing a diamond of size k has the following properties:
The cost of enhancing a diamond is equal to the number of digits in the result of the enhancement, minus the number of digits in the original diamond.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single integer k in a line on its own, followed by a diamond of size k.
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the minimum cost required to enhance the given diamond into an elegant diamond. If the diamond is already elegant, y=0.
4 1 0 2 1 2 2 1 2 1 1 2 1 3 1 6 3 9 5 5 6 3 1
Case #1: 0 Case #2: 0 Case #3: 5 Case #4: 7
There are four cases. The first two cases start as elegant diamonds of size 1 and 2, respectively, and don't need to be enhanced; so the cost is 0. The third case can be enhanced to look like:
3 1 1 1 2 1 1 1 3
There are several possible enhancements, but this is one with the lowest possible cost, which is 5. In the fourth case we can enhance the diamond into the following elegant diamond:
9 1 1 6 3 6 9 5 5 9 6 3 6 1 1 9
...for a cost of 7.
Contest > Google > Code Jam > Google Code Jam 2010 > Round 2 A1번