codeforces-scrape

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

2206K.md (1899B)


      1 Source: https://codeforces.com/problemset/problem/2206/K
      2 
      3 K. Time Display Stickers
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You have a collection of $n$ digit stickers, represented by a string $S$ of length $n$. Each character of $S$ is a digit 0 through 9, representing one sticker of that digit.
     22 
     23 You want to create time displays using these stickers. Each time display shows a time in the format HH:MM, where:
     24 
     25 * HH is a two-digit hour between $00$ and $11$ (inclusive), and
     26 * MM is a two-digit minute between $00$ and $59$ (inclusive).
     27 
     28 In other words, each time display requires exactly four stickers: two for the hours and two for the minutes. Each sticker can only be used for at most one time display.
     29 
     30 What is the maximum number of time displays you can create?
     31 
     32 Input
     33 
     34 The first line of input contains one integer $t$ ($1 \le t \le 10\,000$) representing the number of test cases. After that, $t$ test cases follow. Each of them is presented as follows.
     35 
     36 The first line of each test case contains an integer $n$ ($1 \le n \le 10^6$).
     37 
     38 The second line contains a string $S$ of length $n$, consisting only of digits 0–9.
     39 
     40 The sum of $n$ across all test cases in one input file does not exceed $10^6$.
     41 
     42 Output
     43 
     44 For each test case, output the maximum number of time displays you can create.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 4
     52 10
     53 0123456789
     54 11
     55 00123456789
     56 8
     57 99111111
     58 4
     59 1234
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 1
     66 2
     67 2
     68 0
     69 ```
     70 
     71 Note
     72 
     73 Explanation for the sample input/output #1
     74 
     75 For the first test case, you can create one time display 10:59. It can be shown that you cannot create two displays for a given collection of stickers.
     76 
     77 For the second test case, you can create two time displays: 10:59 and 04:27.
     78 
     79 For the third test case, you can create two time displays: 11:19 and 11:19.
     80 
     81 For the fourth test case, you cannot create any time displays.