303923: CF756B. Travel Card

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Travel Card

题意翻译

为了乘车,有三种票可买: 1. 花 $20$ 元购买单程票; 2. 花 $50$ 元购买 $90$ 分钟内任意乘车的票; 3. 花 $120$ 元购买 $1440$ 分钟内任意乘车的票。 你计划乘 $n$ 次车,第 $i$ 次乘车开始于第 $t_i$ 分钟的开头且恰好持续一分钟。 对于每一个 $1 \le i \le n$ , 计算出完成前 $i$ 次乘车需要的最少金额。 输出完成第 $i$ 次乘车需要的金额与完成第 $i - 1$ 次乘车需要的金额差值。

题目描述

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. The fare is constructed in the following manner. There are three types of tickets: 1. a ticket for one trip costs $ 20 $ byteland rubles, 2. a ticket for $ 90 $ minutes costs $ 50 $ byteland rubles, 3. a ticket for one day ( $ 1440 $ minutes) costs $ 120 $ byteland rubles. 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. 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 $ . You have to write a program that, for given trips made by a passenger, calculates the sum the passenger is charged after each trip.

输入输出格式

输入格式


The first line of input contains integer number $ n $ ( $ 1<=n<=10^{5} $ ) — the number of trips made by passenger. Each of the following $ n $ lines contains the time of trip $ t_{i} $ ( $ 0<=t_{i}<=10^{9} $ ), measured in minutes from the time of starting the system. All $ t_{i} $ are different, given in ascending order, i. e. $ t_{i+1}&gt;t_{i} $ holds for all $ 1<=i&lt;n $ .

输出格式


Output $ n $ integers. For each trip, print the sum the passenger is charged after it.

输入输出样例

输入样例 #1

3
10
20
30

输出样例 #1

20
20
10

输入样例 #2

10
13
45
46
60
103
115
126
150
256
516

输出样例 #2

20
20
10
0
20
0
0
20
20
10

说明

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.

Input

题意翻译

为了乘车,有三种票可买: 1. 花 $20$ 元购买单程票; 2. 花 $50$ 元购买 $90$ 分钟内任意乘车的票; 3. 花 $120$ 元购买 $1440$ 分钟内任意乘车的票。 你计划乘 $n$ 次车,第 $i$ 次乘车开始于第 $t_i$ 分钟的开头且恰好持续一分钟。 对于每一个 $1 \le i \le n$ , 计算出完成前 $i$ 次乘车需要的最少金额。 输出完成第 $i$ 次乘车需要的金额与完成第 $i - 1$ 次乘车需要的金额差值。

加入题单

上一题 下一题 算法标签: