Man with No Name

All submissions for this problem are available.
Blondie is a bounty hunter. Today, he is on a mission to shoot criminals in a particular city. A city is divided into $N$ areas, numbered $1$ through $N$. It is known that an area numbered $i$ contains $A_i$ criminals. But the problem here is that for some areas, the number of criminals is unknown. Blondie needs to know the number of criminals in each area in advance, as he is very good with the gun, so he only needs a single bullet for one criminal, that’s why he needs to know the count. He doesn’t like to carry more bullets with him. The areas are arranged linearly in order. And the good part is that for each area with unknown criminals, the number of criminals can be calculated by following these simple steps: *Step 1*: Count the criminals shot before *Step 2*: Count the areas visited before *Step 3*: Divide criminals found in *Step 1* by areas found in *Step 2* *Step 4*: Round it down to the nearest integer *Step 5*: That’s it Calculate the number of bullets Blondie needs for each area. ###Input:  The first line of the input contains an integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_1, A_2, ..., A_N$ denoting the number of criminals in each area respectively. An area with unknown number of criminals is denoted by $1$. ###Output: For each testcase, print a single line containing $N$ space separated integers, denoting the number of bullets required by Blondie for each area in the city in order. ###Constraints  $1 \leq T \leq 10$  $1 \leq N \leq 10^5$  $1 \leq A_i \leq 10^9$ or $A_i = 1$ (for each valid $i$)  $A_1\gt 0$ ###Subtasks  **30 points**: $1 \leq N \leq 100$  **70 points**: original constraints ###Sample Input: 2 5 23 2 4 1 1 8 34 56 1 4 67 2 1 43 ###Sample Output: 23 2 4 1 7 34 56 45 4 67 2 34 43 ###EXPLANATION: **Example Case 1:** For last area, $\lfloor \frac{(23 + 2 + 4 + 1)}{4}\rfloor = 7$ bullets **Example Case 2:** For $3^{rd}$ area, $\lfloor \frac{(34 + 56)}{2}\rfloor = 45$ bullets Then, for $7^{th}$ area, $\lfloor \frac{(34 + 56 + 45 + 4 + 67 + 2)}{6}\rfloor = 34$ bulletsAuthor:  ankushkhanna 
Editorial  https://discuss.codechef.com/problems/BLONDIE 
Tags  ankushkhanna, ankushkhanna, cakewalk, cobe2019, prefixsum 
Date Added:  28012019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions