CF1209B 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 ai and bi. Light with parameters ai and bi will toggle (on to off, or off to on) every ai seconds starting from the bi-th second. In other words, it will toggle at the moments bi, bi+ai, bi+2⋅ai and so on.
You know for each light whether it's initially on or off and its corresponding parameters ai and bi. 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.
Here is a graphic for the first example.
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 ii-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 ai and bi (1≤ai,bi≤5) — the parameters of the i-th light.
Print a single integer — the maximum number of lights that will ever be on at the same time.
3
101
3 3
3 2
3 1
2
4
1111
3 4
5 2
3 1
3 2
4
6
011100
5 3
5 5
2 4
3 5
4 2
1 5
6
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).
In the second example, all lights are initially on. So the answer is 4.
解释题意:有n盏灯,1代表开0代表关,初始状态已给出,每盏灯有a和b两个属性,bs之后灯切换一次状态,之后每a秒切换一次状态。求最多同时亮几盏灯。
不难想到我们可以模拟所有的状态而所有状态的周期最多是2*3*4*5+5种。保险起见可以多跑几次
#include <bits/stdc++.h>
using namespace std;
bool a[];
int l[];
int r[];
int c[];
int f[];
int main()
{
int n;
cin>>n;
string str;
cin>>str;
for(int i=;i<str.size();++i)
{
if(str[i]=='')
{
a[i+]=;
}
else
{
a[i+]=;
}
}
for(int i=;i<=n;++i)
{
cin>>l[i]>>r[i];
c[i]=l[i];
}
int mmax=;
int tmp=;
for(int i=;i<=n;++i)
{
if(a[i]==)
{
tmp++;
mmax=max(mmax,tmp);
}
}
for(int k=;k<=;++k)
{
int tmp=;
for(int i=;i<=n;++i)
{
if(a[i]==)
{
tmp++;
mmax=max(mmax,tmp);
}
}
for(int i=;i<=n;++i)
{
if(f[i]==&&r[i]==)
{
c[i]--;
if(c[i]==)
{
c[i]=l[i];
a[i]=!a[i];
}
}
if(r[i]>)
{
r[i]--;
if(r[i]==)
{
a[i]=!a[i];
f[i]=;
}
}
}
}
cout<<mmax;
return ;
}
最新文章
- 机器学习——支持向量机(SVM)之拉格朗日乘子法,KKT条件以及简化版SMO算法分析
- Vijos1006P1006晴天小猪历险记之Hill[最短路]
- JSP 简介
- javascript无缝滚动示例
- HDU 1080 Human Gene Functions
- margin系列之内秀篇(二)
- 【POJ1330】Nearest Common Ancestors(树链剖分求LCA)
- java中的输入流(Scanner),数据类型,运算符,switch,数组的用法
- 讲解——Trie树(字典树)
- mysq常用l性能分析方法
- SoapUI中XML解析
- DDD关键知识点整理汇总
- 关于 GET、POST、表单、Content-Type
- ORACLE procedure 一个参数分解成多个字符一点建议
- HTML中使用<;input>;添加的按钮打开一个链接
- dp 最大正方形
- TCP三次握手详解
- iOS UI基础-6.0 UIActionSheet的使用
- OpenGLES渲染
- Winafl学习笔记