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.