Responsive image

问题 3431 --猫猫狗狗

3431: 猫猫狗狗

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 45
[提交][状态][讨论版][命题人:]

题目描述

我们学校校园里有许多的小猫，小狗(动物学长(姐)(o(^▽^)o))，小猫，小狗都是非常可爱的动物，想必大家都很喜欢。

现在小劉同学拿来数只猫和狗，将它们放在一个并列排列的连续的房间内，每个房间都有一个窗户能够看到第二个房间里边，一共n个房间。

我们假设猫能够很确定的分清楚对方是猫还是狗，狗不能十分确定的分清楚对方是猫还是狗，也就是说猫的判断总是正确的，而狗的判断不一定正确。

给你一个长度为n-1的01字符串，字符串中只含有0和1，1表示第i个房间的动物判断第i+1个房间的动物是狗，而0表示表示第i个房间的动物判断第i+1个房间的动物不是狗。

由于小劉同学忘记了拿来的狗和猫的数量，请你帮助小劉同学判断在狗的数量最少的情况下，有几只狗，几只猫。

输入描述

第一行一个整数t，表示一共有t组样例(1<=t<=104)
接下来每个样例中
第一行一个数字n，表示一共有n只动物(2<=n<=103)
第二行一个01字符串，表示前n-1个房间的判断情况(1<=字符串的长度<=103-1)

输出描述

输出在狗的数量最少的情况下，有几只狗，几只猫，每个结果占一行。

样例输入

3
5
0001
5
1010
7
101110

样例输出

1 4
2 3
3 4

提示

对题目中样例的解释：

第一个样例：猫，猫，猫，猫，狗

第二个样例：猫，狗，猫，狗，猫

第三个样例：猫，狗，猫，狗，猫，狗，猫


来源

23软3刘震峰 

[提交][状态]
ACM算法攻关部