| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 77 | 62 | 52 | 83.871% |
We call a permutation p0, p1, ... , pn-1 of a sequence of integers 0, 1, ... , n-1 mod-3 when for each index i, pi mod 3 = i mod 3. For example, the permutation 3,1,5,0,4,2 is mod-3 but the permutation 1,2,0,4,5,3 is not. You will be given a permutation. You are required to convert the given permutation into a mod-3 permutationin the minimum number of steps. For each step of the conversion, you need to select two different indices and swap their values.
The first line has a positive integer T, T <= 100000, denoting the number of test cases. This is followed by each test case per line.
Each test case consists of two lines; the first line contains an integer n while the next line contains n integers separated by a single space. These n integers denotes a permutation of 0, 1, .., n-1. n is between 3 and 501 inclusive and is always a multiple of 3.
For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the minimum number of swaps required to convert the given permutation into a mod-3 permutation.
10 3 2 0 1 6 1 0 3 2 5 4 6 4 0 3 5 2 4 6 5 3 4 2 0 1 3 0 2 1 9 5 3 8 6 7 0 1 2 4 9 2 1 7 3 5 4 8 6 0 9 3 5 2 0 6 4 7 1 8 9 5 7 1 8 2 6 0 4 3 9 8 3 5 0 6 7 4 2 1
Case #1: 2 Case #2: 3 Case #3: 3 Case #4: 4 Case #5: 1 Case #6: 3 Case #7: 4 Case #8: 2 Case #9: 3 Case #10: 4