1176C.md (1866B)
1 Source: https://codeforces.com/problemset/problem/1176/C 2 3 C. Lose it! 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 You are given an array $a$ consisting of $n$ integers. Each $a_i$ is one of the six following numbers: $4, 8, 15, 16, 23, 42$. 22 23 Your task is to remove the minimum number of elements to make this array good. 24 25 An array of length $k$ is called good if $k$ is divisible by $6$ and it is possible to split it into $\frac{k}{6}$ subsequences $4, 8, 15, 16, 23, 42$. 26 27 Examples of good arrays: 28 29 * $[4, 8, 15, 16, 23, 42]$ (the whole array is a required sequence); 30 * $[4, 8, 4, 15, 16, 8, 23, 15, 16, 42, 23, 42]$ (the first sequence is formed from first, second, fourth, fifth, seventh and tenth elements and the second one is formed from remaining elements); 31 * $[]$ (the empty array is good). 32 33 Examples of bad arrays: 34 35 * $[4, 8, 15, 16, 42, 23]$ (the order of elements should be exactly $4, 8, 15, 16, 23, 42$); 36 * $[4, 8, 15, 16, 23, 42, 4]$ (the length of the array is not divisible by $6$); 37 * $[4, 8, 15, 16, 23, 42, 4, 8, 15, 16, 23, 23]$ (the first sequence can be formed from first six elements but the remaining array cannot form the required sequence). 38 39 Input 40 41 The first line of the input contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of elements in $a$. 42 43 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ (each $a_i$ is one of the following numbers: $4, 8, 15, 16, 23, 42$), where $a_i$ is the $i$-th element of $a$. 44 45 Output 46 47 Print one integer — the minimum number of elements you have to remove to obtain a good array. 48 49 Examples 50 51 Input 52 53 ``` 54 5 55 4 8 15 16 23 56 ``` 57 58 Output 59 60 ``` 61 5 62 ``` 63 64 Input 65 66 ``` 67 12 68 4 8 4 15 16 8 23 15 16 42 23 42 69 ``` 70 71 Output 72 73 ``` 74 0 75 ``` 76 77 Input 78 79 ``` 80 15 81 4 8 4 8 15 16 8 16 23 15 16 4 42 23 42 82 ``` 83 84 Output 85 86 ``` 87 3 88 ```