1209B.md (1963B)
1 Source: https://codeforces.com/problemset/problem/1209/B 2 3 B. Koala and Lights 4 5 time limit per test 6 7 1 second 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 It is a holiday season, and Koala is decorating his house with cool lights! He owns $n$ lights, all of which flash periodically. 22 23 After taking a quick glance at them, Koala realizes that each of his lights can be described with two parameters $a_i$ and $b_i$. Light with parameters $a_i$ and $b_i$ will toggle (on to off, or off to on) every $a_i$ seconds starting from the $b_i$-th second. In other words, it will toggle at the moments $b_i$, $b_i + a_i$, $b_i + 2 \cdot a_i$ and so on. 24 25 You know for each light whether it's initially on or off and its corresponding parameters $a_i$ and $b_i$. Koala is wondering what is the maximum number of lights that will ever be on at the same time. So you need to find that out. 26 27  Here is a graphic for the first example. 28 29 Input 30 31 The first line contains a single integer $n$ ($1 \le n \le 100$), the number of lights. 32 33 The next line contains a string $s$ of $n$ characters. The $i$-th character is "1", if the $i$-th lamp is initially on. Otherwise, $i$-th character is "0". 34 35 The $i$-th of the following $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 5$) — the parameters of the $i$-th light. 36 37 Output 38 39 Print a single integer — the maximum number of lights that will ever be on at the same time. 40 41 Examples 42 43 Input 44 45 ``` 46 3 47 101 48 3 3 49 3 2 50 3 1 51 ``` 52 53 Output 54 55 ``` 56 2 57 ``` 58 59 Input 60 61 ``` 62 4 63 1111 64 3 4 65 5 2 66 3 1 67 3 2 68 ``` 69 70 Output 71 72 ``` 73 4 74 ``` 75 76 Input 77 78 ``` 79 6 80 011100 81 5 3 82 5 5 83 2 4 84 3 5 85 4 2 86 1 5 87 ``` 88 89 Output 90 91 ``` 92 6 93 ``` 94 95 Note 96 97 For first example, the lamps' states are shown in the picture above. The largest number of simultaneously on lamps is $2$ (e.g. at the moment $2$). 98 99 In the second example, all lights are initially on. So the answer is $4$.