P7075: 桑给巴尔的海龟
传统题
1.000s
时间限制
256MB
内存限制
2 提交
1 解决
【题目描述】
【题目描述】
海龟寿命长（而且兴旺发达）。桑给巴尔岛上的海龟甚至是不朽的。此外，他们每年最多生一个孩子。除此之外，他们什么也不做。他们从未离开过他们的热带天堂。
桑给巴尔岛上的第一只海龟桑兹有一项活动：它跟踪岛上海龟的数量。每年元旦，它都会清点海龟，并将总数写在一本小册子上。多年后，这本小册子包含了一个非递减的整数序列，从一个或多个整数开始。（桑给巴尔美丽的海滩上，桑兹从卵里出来后，花了一段时间独自组建了一个家庭。）
有一天，桑兹意识到，从国外来桑给巴尔的海龟也可能是乘船或飞机。现在，人们想知道有多少居民不是桑给巴尔人。不幸的是，它只能从小册子中的顺序得出一个下限。事实上，如果一年中海龟的数量是前一年的两倍多，那么这种差异必须通过进口来充分解释。
桑给巴尔岛最多容纳100万只海龟，如果超过100万只海龟，繁殖和进口都停止了。请帮帮桑兹！编写一个程序，计算输入海龟的下限，给定一个序列，如上所述。
【输入】
输入第一行一个整数T（1≤
T≤
13），表示测试用例的数量。
以下T行，每行输入以空格分隔的正整数非递减序列（≤
1000000），每行以1开始。以0 结束。
【输出】
对于每个测试用例，输出一行包含一个整数：即桑给巴尔出生的海龟数量的下限。
【样本输入1】
3
1 100 0
1 1 1 2 2 4 8 8 9 0
1 28 72 0
【样本输出1】
98
0
42