codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

178A3.md (2369B)


      1 Source: https://codeforces.com/problemset/problem/178/A3
      2 
      3 A3. 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 ```