小X 分砖块

小X 分砖块

测试数据来自 wjszez/1010

【问题描述】
小X 喜欢跟着爸爸跑到建筑工地上去。
这天,小X 看到一排砖,每块要么是白色的(0),要么是黑色的(1)。小X 想把这排砖分成若干非空段,使得每段白砖和黑砖块数的比例相同。
当然,小X 可以直接把整排砖作为一段,那就太简单了。为了增加难度,小X 想知道最多能分成多少段,例如:
100011 = 10 + 0011(即样例1,最多分成2 段,比例为1:1);
0001110000000001 = 0001 + 11000000 + 0001(即样例2,最多分成3 段,比例为3:1)。
小X 百思不得其解,希望你帮帮他。
【输入文件】
第一行包含一个整数N。我们将用N 行来描述这排砖,初始时这排砖为空。
接下来N 行,每行包含用一个空格隔开的两个整数Ki,Ci(Ci 只可能是0 或1),表示在上一行描述完后尾部又有了Ki 块颜色为Ci 的砖。
【输出文件】
第一行包含一个整数,表示最多能分成的段数。
【样例输入1】
3
1 1
3 0
2 1
【样例输出1】
2
【样例输入2】
4
3 0
3 1
9 0
1 1
【样例输出2】
3
【数据范围】
对于30%的数据,N=1。
对于60%的数据,所有Ki 均相等。
对于100%的数据,1≤N≤100000,1≤Ki≤1000000000,砖的总块数不超过1000000000。

信息

ID
2407
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者