问题 1128. -- 小X分砖块

1128: 小X分砖块

时间限制: 1 Sec  内存限制: 128 MB
提交: 44  解决: 8
[提交][状态][讨论版]

题目描述

小 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 的砖。

输出

第一行包含一个整数,表示最多能分成的段数。

样例输入

3
1 1
3 0
2 1

样例输出

2

提示

数据范围

对于 30%的数据,N=1。

对于 60%的数据,所有 Ki 均相等。

对于 100%的数据,1≤N≤100000,1≤Ki≤1000000000,砖的总块数不超过 1000000000。

来源

[提交][状态]