100842: [AtCoder]ABC084 C - Special Trains

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

Description

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 1

3
6 5 1
1 10 1

Sample Output 1

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 2

4
12 24 6
52 16 4
99 2 2

Sample Output 2

187
167
101
0

Sample Input 3

4
12 13 1
44 17 17
66 4096 64

Sample Output 3

4162
4162
4162
0

Input

题意翻译

### 题面翻译 在AtCoder国里，明天将会举行一场铁路开通仪式。 在这条铁路上，从左往右依次有n个车站。我们不妨依次编号为1，2，3，······，n。 在这条铁路上，对于满足 1≤i≤n-1 的所有整数 i ，从车站 i 到车站 i+1 ，以 c[i] 秒运行列车。同时，这些列车以外的列车不运行。 从站 i 移动到站 i+1 的列车中的第一列列车，在开通仪式上将在开始 s[i] 秒后从站i出发，然后隔 f[i] 秒从站I I出发的shan列车。之后有每隔 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 的火车将在开始通车式几秒后。 ------------ ### 输入与输出: 输入第一行只有一个数 N ,接下来将会有 N-1 行,分别有三个数字,依次表示 c[i] , s[i] , f[i] 。 1≦N≦500 1≦c[i]≦100 1≦s[i]≦100,000 1≦f[i]≦100 输出 N-1 行，依次表示所对应数据的答案，最后输出个 0 表示输出结束。 #### 温馨提示：岛国题目最后输出完也要再换个行！ ------------

Source/Category

加入题单

算法标签：