codeforces-scrape

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

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 ```