codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/e047423e2d0117d489bd89afd6732f829aa2c224.png) 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.