codeforces-scrape

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

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  ![](https://espresso.codeforces.com/dd6abac016113099a6ce1ec5d44c9aa65bdf9dc3.png) 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$.