2195C.md (2526B)
1 Source: https://codeforces.com/problemset/problem/2195/C 2 3 C. Dice Roll Sequence 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Consider the following cube $D$ where numbers $x$ and $7-x$ lie on opposite sides: 22 23  Image generated by Nano Banana Pro. 24 25 A sequence $b$ of integers from $1$ to $6$ is called a dice roll sequence if it satisfies the following condition: 26 27 * All pairs of adjacent elements lie on adjacent$^{\text{∗}}$ sides of the cube. 28 29 For example, $[1,4,2]$ is a dice roll sequence, while $[3,4,6,3]$ is not because $3$ and $4$ are not on adjacent sides of the dice. Additionally, $[2,2,4]$ is not a dice roll sequence because $2$ and $2$ are on the same (not adjacent) side of the dice. 30 31 Given a sequence $a$ of $n$ integers from $1$ to $6$, you can perform the following operation any number of times (possibly zero). 32 33 * Select an index $1 \le i \le n$ and an integer $1 \le x \le 6$. Then, change the value of $a_i$ to $x$. 34 35 Please determine the minimum number of operations required to make $a$ a dice roll sequence. 36 37 $^{\text{∗}}$Two sides of the cube $S$ and $T$ are called adjacent if they share exactly one edge of the cube. Do note that this condition implies $S \neq T$ as well. 38 39 Input 40 41 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 42 43 The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$). 44 45 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 6$). 46 47 It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$. 48 49 Output 50 51 For each test case, output the minimum number of operations required to make $a$ a dice roll sequence. 52 53 Example 54 55 Input 56 57 ``` 58 3 59 60 3 61 62 1 4 2 63 64 4 65 66 3 4 6 3 67 68 10 69 70 6 1 4 3 1 3 2 5 4 4 71 ``` 72 73 Output 74 75 ``` 76 0 77 78 1 79 80 4 81 ``` 82 83 Note 84 85 For the first test case, the sequence $a$ is $[1,4,2]$. As this is already a dice roll sequence, the answer is $0$. 86 87 For the second test case, the sequence $a$ is $[3,4,6,3]$. 88 89 Changing exactly one element, you can get $[3,\color{red}{5},6,3]$, which is a dice roll sequence. 90 91 For the third test case, the sequence $a$ is $[6,1,4,3,1,3,2,5,4,4]$. 92 93 Changing exactly $4$ elements, you can get $[\color{red}{5},1,4,\color{red}{2},1,3,2,\color{red}{1},\color{red}{5},4]$, which is a dice roll sequence.