시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
30 초 (추가 시간 없음) | 1024 MB | 30 | 17 | 14 | 58.333% |
Imagine you have a padlock, which is a combination lock consisting of $N$ dials, set initially to a random combination. The dials of the padlock are of size $D$, which means that they can have values between $0$ and $D-1$, inclusive, and can be rotated upwards or downwards. They are also ordered from left to right, with the leftmost and rightmost dials at positions $1$ and $N$, respectively. The padlock can be unlocked by setting the values of all its dials to $0$.
You can perform zero or more operations of this kind:
The series of operations must satisfy the following condition:
Example of a valid sequence of operations to unlock a padlock with initial combination $[1,1,2,2,3,3]$:
The following are some operations that cannot be performed:
The goal for you is to output the minimum number of valid operations needed to make all dials in the padlock set to $0$.
The first line of the input contains the number of test cases, $T$. $T$ test cases follow.
Each test case consists of two lines.
The first line of each test case contains two integers $N$ and $D$, representing the number of dials in the padlock and the size of the dials, respectively.
The second line of each test case contains $N$ integers $V_1,V_2,\dots ,V_N$, where the $i$-th integer represents the value of the $i$-th dial in the initial combination of the padlock.
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 minimum number of operations needed to unlock the padlock as described in the statement.
2 6 2 1 1 0 1 0 1 6 2 0 1 0 0 1 1
Case #1: 3 Case #2: 2
In Sample Case #1, the minimum number of operations needed to unlock the padlock is $3$. We can unlock it using the following operations:
In Sample Case #2, the minimum number of operations needed to unlock the padlock is $2$. We can unlock it using the following operations:
2 6 10 1 1 2 2 3 3 6 10 1 1 9 9 1 1
Case #1: 3 Case #2: 3
In Sample Case #1, the minimum number of operations needed to unlock the padlock is $3$. We can unlock it using the following operations:
In Sample Case #2, the minimum number of operations needed to unlock the padlock is $3$. We can unlock it using the following operations:
Contest > Google > Kick Start > Google Kick Start 2022 > Round B C번