178A1.md (2369B)
1 Source: https://codeforces.com/problemset/problem/178/A1 2 3 A1. Educational Game 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 The Smart Beaver from ABBYY began to develop a new educational game for children. The rules of the game are fairly simple and are described below. 22 23 The playing field is a sequence of *n* non-negative integers *a**i* numbered from 1 to *n*. The goal of the game is to make numbers *a*1, *a*2, ..., *a**k* (i.e. some prefix of the sequence) equal to zero for some fixed *k* (*k* < *n*), and this should be done in the smallest possible number of moves. 24 25 One move is choosing an integer *i* (1 ≤ *i* ≤ *n*) such that *a**i* > 0 and an integer *t* (*t* ≥ 0) such that *i* + 2*t* ≤ *n*. After the values of *i* and *t* have been selected, the value of *a**i* is decreased by 1, and the value of *a**i* + 2*t* is increased by 1. For example, let *n* = 4 and *a* = (1, 0, 1, 2), then it is possible to make move *i* = 3, *t* = 0 and get *a* = (1, 0, 0, 3) or to make move *i* = 1, *t* = 1 and get *a* = (0, 0, 2, 2) (the only possible other move is *i* = 1, *t* = 0). 26 27 You are given *n* and the initial sequence *a**i*. The task is to calculate the minimum number of moves needed to make the first *k* elements of the original sequence equal to zero for each possible *k* (1 ≤ *k* < *n*). 28 29 Input 30 31 The first input line contains a single integer *n*. The second line contains *n* integers *a**i* (0 ≤ *a**i* ≤ 104), separated by single spaces. 32 33 The input limitations for getting 20 points are: 34 35 * 1 ≤ *n* ≤ 300 36 37 The input limitations for getting 50 points are: 38 39 * 1 ≤ *n* ≤ 2000 40 41 The input limitations for getting 100 points are: 42 43 * 1 ≤ *n* ≤ 105 44 45 Output 46 47 Print exactly *n* - 1 lines: the *k*-th output line must contain the minimum number of moves needed to make the first *k* elements of the original sequence *a**i* equal to zero. 48 49 Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams, or the %I64d specifier. 50 51 Examples 52 53 Input 54 55 ``` 56 4 57 1 0 1 2 58 ``` 59 60 Output 61 62 ``` 63 1 64 1 65 3 66 ``` 67 68 Input 69 70 ``` 71 8 72 1 2 3 4 5 6 7 8 73 ``` 74 75 Output 76 77 ``` 78 1 79 3 80 6 81 10 82 16 83 24 84 40 85 ```