程序设计在线评测(Online Judge)


问题 1678. -- Ada 学单双

1678: Ada 学单双

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

题目描述

Ada四岁了,开始学单数和双数,单是1,3,5,7,9,双是2,4,6,8,10。这样未免太乏味了,为了让她感兴趣,爸爸设计了下面的一个小游戏:
(1)给定数字系列1到n并依次编号
(2)给定一个字符串,里面的字符只有0或者1
(3)如果当前的数字系列只含一个整数,游戏终止。否则读取字符串中的下一个字符为当前字符。
(4)如果当前字符为0,把所有双数编号的数字删除;如果字符为1,把所有单数编号的数字删除。剩下的数字按次序重新从1开始编号。然后跳转到第三步。
问最后留下的数字是几?100以内的Ada也许还能应付,太大的数字就看你了。

给一个具体的例子,n为10,字符串为"1010101",
第一个读出的字符是'1',删掉所有单数编号的数字,剩下的数字系列是2 4 6 8 10。
第二个读出的字符是'0',删掉所有双数编号的数字,剩下的数字系列是2 6 10。
第三个读出的字符是'1',删掉所有单数编号的数字,剩下的数字系列是6。 

输入

输入包含多组数据(不超过5万组),每组数据一行,由空格分开的整数n和01字符串组成,1<= n < 2^31,字符串的长度保证游戏能够结束。

输出

对于每组数据,输出一行,即最后留下的数字。

样例输入

10 1010101
9 010101

样例输出

6
3

提示

来源

[提交][状态][讨论版]