TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

93.3% (42/45)

Submission's AC Ratio

57.7% (82/142)

Tags

Description

桌面上有許多堆豆子和一個筒子。
現在進行一種遊戲:每次找一堆豆子,如果這堆豆子只有1個,就將它放入筒子,
如果多於一個,則將它分成盡量多而且相等的兩堆,並且把剩下的一個(如果有的話)丟掉。
重複進行許多次之後,所有的豆子要不是在筒子內就是被丟掉了。
現在,我們想要知道在遊戲中會有多少豆子被放入筒子。

Input Format

輸入可能包含了好幾列測試資料,每一列有至多100個整數資料 ai ,表示第 i 堆豆子的個數,每列最後會有一個 0 代表這列結束。
最後會有一列以 0 開始,表示測試資料結束。
其中 0 < ai < 10000000

Output Format

對每一列輸入,輸出會有多少豆子在遊戲中被放入筒子。

Sample Input

16 0
16 8 4 2 1 0
999999 999999 0
0

Sample Output

16
31
1048576

Hints

2015/7/28 由samsam2310新增測資,也許會有錯喔XDD

Problem Source

原TIOJ1031 / KSHSVC 97,98 TOI 初選練習(07/02/01 prob 2)

Subtasks

For Testdata: 0 ~ 2, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536