Codeforces 1209B Koala and Lights:模拟

题目

It is a holiday season, and Koala is decorating his house with cool lights! He owns n lights, all of which flash periodically.

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⋅a_i and so on.

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.

imgHere is a graphic for the first example.

Input

The first line contains a single integer n (1≤n≤100), the number of lights.

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".

The i-th of the following n lines contains two integers a_i and b_i (1≤a_i,b_i≤5) — the parameters of the i-th light.

Output

Print a single integer — the maximum number of lights that will ever be on at the same time.

题解

每个灯在 b_i 秒之后,都是亮 a_i 秒然后灭 a_i 秒(或先灭后亮),所以对于单独的一个灯来说,周期为 2a_i

由于 1≤a_i≤5,所以所有灯合在一起的发光的周期最大为 lcm(2,4,6,8,10)=120

再考虑 b_i:因为 1≤b_i≤5,所以在最多前五秒内,还有灯没有进入自己的发光周期,所以这前五秒也要纳入计算

所以我们要枚举的就是前120+5=125秒,对每一秒计算有多少灯同时亮着,取最大答案即可

Code

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105

using namespace std;

int n, ans = 0;
int a[MAX_N];
int b[MAX_N];
char s[MAX_N];

inline bool check(int t, int i) {
    if (t < b[i]) {
        return s[i] == '1';
    }
    return ((t - b[i]) % (a[i] << 1) < a[i]) ^ (s[i] == '1');
}

int main() {
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", a + i, b + i);
    }
    for (int i = 0; i < 125; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++) {
            cnt += check(i, j);
        }
        ans = max(ans, cnt);
    }
    printf("%d\n", ans);
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注