codeforces-scrape

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

581B.md (1999B)


      1 Source: https://codeforces.com/problemset/problem/581/B
      2 
      3 B. Luxurious Houses
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The capital of Berland has *n* multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.
     22 
     23 Let's enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.
     24 
     25 The new architect is interested in *n* questions, *i*-th of them is about the following: "how many floors should be added to the *i*-th house to make it luxurious?" (for all *i* from 1 to *n*, inclusive). You need to help him cope with this task.
     26 
     27 Note that all these questions are independent from each other — the answer to the question for house *i* does not affect other answers (i.e., the floors to the houses are not actually added).
     28 
     29 Input
     30 
     31 The first line of the input contains a single number *n* (1 ≤ *n* ≤ 105) — the number of houses in the capital of Berland.
     32 
     33 The second line contains *n* space-separated positive integers *h**i* (1 ≤ *h**i* ≤ 109), where *h**i* equals the number of floors in the *i*-th house.
     34 
     35 Output
     36 
     37 Print *n* integers *a*1, *a*2, ..., *a**n*, where number *a**i* is the number of floors that need to be added to the house number *i* to make it luxurious. If the house is already luxurious and nothing needs to be added to it, then *a**i* should be equal to zero.
     38 
     39 All houses are numbered from left to right, starting from one.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 5  
     47 1 2 3 1 2
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 3 2 0 2 0
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 4  
     60 3 2 1 4
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 2 3 4 0
     67 ```