C - Special Trains

Contest Duration: 2017-12-30(Sat) 12:00 - 2017-12-30(Sat) 13:40 (local time) (100 minutes) Back to Home

C - Special Trains Editorial

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : $300$ 点

問題文

Atcoder国に、 $1$ 本の東西方向に走る鉄道が完成しました。

この鉄道には $N$ 個の駅があり、西から順に $1$ , $2$ , $...$ , $N$ の番号がついています。

明日、鉄道の開通式が開かれます。

この鉄道では、 $1≦i≦N-1$ を満たす全ての整数 $i$ に対して、駅 $i$ から駅 $i+1$ に、 $C_i$ 秒で向かう列車が運行されます。ただし、これら以外の列車は運行されません。

駅 $i$ から駅 $i+1$ に移動する列車のうち最初の列車は、開通式開始 $S_i$ 秒後に駅 $i$ を発車し、その後は $F_i$ 秒おきに駅 $i$ を発車する列車があります。

また、 $S_i$ は $F_i$ で割り切れることが保証されます。

つまり、 $A％B$ で $A$ を $B$ で割った余りを表すとき、 $S_i≦t$ , $t％F_i=0$ を満たす全ての $t$ に対してのみ、開通式開始 $t$ 秒後に駅 $i$ を出発し、開通式開始 $t+C_i$ 秒後に駅 $i+1$ に到着する列車があります。

列車の乗り降りにかかる時間を考えないとき、全ての駅 $i$ に対して、開通式開始時に駅 $i$ にいる場合、駅 $N$ に到着できるのは最も早くて開通式開始何秒後か、答えてください。

制約

$1≦N≦500$
$1≦C_i≦100$
$1≦S_i≦10^5$
$1≦F_i≦100$
$S_i％F_i=0$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $C_1$   $S_1$   $F_1$ 
 $:$ 
 $C_{N-1}$   $S_{N-1}$   $F_{N-1}$

出力

$i$ 行目 $(1≦i≦N)$ に、開通式開始時に駅 $i$ にいる場合、駅 $N$ に到着できるのが最も早くて開通式開始 $x$ 秒後のとき、 $x$ を出力せよ。

入力例 1Copy

Copy

3
6 5 1
1 10 1

出力例 1Copy

Copy

12
11
0

駅 $1$ からは、以下のように移動します。

開通式開始 $5$ 秒後に、駅 $2$ に向かう列車に乗る。
開通式開始 $11$ 秒後に、駅 $2$ に到着する。
開通式開始 $11$ 秒後に、駅 $3$ に向かう列車に乗る。
開通式開始 $12$ 秒後に、駅 $3$ に到着する。

駅 $2$ からは、以下のように移動します。

開通式開始 $10$ 秒後に、駅 $3$ に向かう列車に乗る。
開通式開始 $11$ 秒後に、駅 $3$ に到着する。

駅 $3$ に対しても、 $0$ を出力しなければならないことに注意してください。

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

出力例 3Copy

Copy

Score : $300$ points

Problem Statement

A railroad running from west to east in Atcoder Kingdom is now complete.

There are $N$ stations on the railroad, numbered $1$ through $N$ from west to east.

Tomorrow, the opening ceremony of the railroad will take place.

On this railroad, for each integer $i$ such that $1≤i≤N-1$ , there will be trains that run from Station $i$ to Station $i+1$ in $C_i$ seconds. No other trains will be operated.

The first train from Station $i$ to Station $i+1$ will depart Station $i$ $S_i$ seconds after the ceremony begins. Thereafter, there will be a train that departs Station $i$ every $F_i$ seconds.

Here, it is guaranteed that $F_i$ divides $S_i$ .

That is, for each Time $t$ satisfying $S_i≤t$ and $t％F_i=0$ , there will be a train that departs Station $i$ $t$ seconds after the ceremony begins and arrives at Station $i+1$ $t+C_i$ seconds after the ceremony begins, where $A％B$ denotes $A$ modulo $B$ , and there will be no other trains.

For each $i$ , find the earliest possible time we can reach Station $N$ if we are at Station $i$ when the ceremony begins, ignoring the time needed to change trains.

Constraints

$1≤N≤500$
$1≤C_i≤100$
$1≤S_i≤10^5$
$1≤F_i≤10$
$S_i％F_i=0$
All input values are integers.

Input

Input is given from Standard Input in the following format:

 $N$ 
 $C_1$   $S_1$   $F_1$ 
 $:$ 
 $C_{N-1}$   $S_{N-1}$   $F_{N-1}$

Output

Print $N$ lines. Assuming that we are at Station $i$ $(1≤i≤N)$ when the ceremony begins, if the earliest possible time we can reach Station $N$ is $x$ seconds after the ceremony begins, the $i$ -th line should contain $x$ .

Sample Input 1Copy

Copy

3
6 5 1
1 10 1

Sample Output 1Copy

Copy

12
11
0

We will travel from Station $1$ as follows:

$5$ seconds after the beginning: take the train to Station $2$ .
$11$ seconds: arrive at Station $2$ .
$11$ seconds: take the train to Station $3$ .
$12$ seconds: arrive at Station $3$ .

We will travel from Station $2$ as follows:

$10$ seconds: take the train to Station $3$ .
$11$ seconds: arrive at Station $3$ .

Note that we should print $0$ for Station $3$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy