codeforces-scrape

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

756B.md (2562B)


      1 Source: https://codeforces.com/problemset/problem/756/B
      2 
      3 B. Travel Card
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A new innovative ticketing systems for public transport is introduced in Bytesburg. Now there is a single travel card for all transport. To make a trip a passenger scan his card and then he is charged according to the fare.
     22 
     23 The fare is constructed in the following manner. There are three types of tickets:
     24 
     25 1. a ticket for one trip costs 20 byteland rubles,
     26 2. a ticket for 90 minutes costs 50 byteland rubles,
     27 3. a ticket for one day (1440 minutes) costs 120 byteland rubles.
     28 
     29 Note that a ticket for *x* minutes activated at time *t* can be used for trips started in time range from *t* to *t* + *x* - 1, inclusive. Assume that all trips take exactly one minute.
     30 
     31 To simplify the choice for the passenger, the system automatically chooses the optimal tickets. After each trip starts, the system analyses all the previous trips and the current trip and chooses a set of tickets for these trips with a minimum total cost. Let the minimum total cost of tickets to cover all trips from the first to the current is *a*, and the total sum charged before is *b*. Then the system charges the passenger the sum *a* - *b*.
     32 
     33 You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.
     34 
     35 Input
     36 
     37 The first line of input contains integer number *n* (1 ≤ *n* ≤ 105) — the number of trips made by passenger.
     38 
     39 Each of the following *n* lines contains the time of trip *t**i* (0 ≤ *t**i* ≤ 109), measured in minutes from the time of starting the system. All *t**i* are different, given in ascending order, i. e. *t**i* + 1 > *t**i* holds for all 1 ≤ *i* < *n*.
     40 
     41 Output
     42 
     43 Output *n* integers. For each trip, print the sum the passenger is charged after it.
     44 
     45 Examples
     46 
     47 Input
     48 
     49 ```
     50 3  
     51 10  
     52 20  
     53 30
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 20  
     60 20  
     61 10
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 10  
     68 13  
     69 45  
     70 46  
     71 60  
     72 103  
     73 115  
     74 126  
     75 150  
     76 256  
     77 516
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 20  
     84 20  
     85 10  
     86 0  
     87 20  
     88 0  
     89 0  
     90 20  
     91 20  
     92 10
     93 ```
     94 
     95 Note
     96 
     97 In the first example, the system works as follows: for the first and second trips it is cheaper to pay for two one-trip tickets, so each time 20 rubles is charged, after the third trip the system understands that it would be cheaper to buy a ticket for 90 minutes. This ticket costs 50 rubles, and the passenger had already paid 40 rubles, so it is necessary to charge 10 rubles only.