問題一覧 > 通常問題

No.139 交差点

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 195
作問者 : kmjpkmjp
7 ProblemId : 250 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-25 01:45:03

問題文

yuki君は自宅から距離Lのところにある友人宅に遊びに行くことにした。
友人宅に着くには、間にあるN個の交差点を横断する必要がある。
i番目の交差点は、自宅から距離Xiの位置から始まり、幅がWiある。
すなわち、区間(Xi,Xi+Wi)は交差点である。

各交差点に設置された信号は、時間Tiごとに青信号と赤信号が交互に変化する。
なお、各交差点における信号はyuki君が出発すると同時に青信号になった。

yuki君は単位時間あたり距離1の速さでまっすぐ向かう。
ただし、yuki君は交差点手前の距離Xiに到着したとき、赤信号中に交差点内にいる可能性があるならば、その可能性がなくなるまで距離Xiの位置で待機する。

yuki君が自宅を出てから、友人宅に到着するまでにかかる経過時間を求めよ。

入力

各入力は以下の形式で与えられる。値はいずれも整数である。
N L
X1 W1 T1
X2 W2 T2
...
XN WN TN

1N100
1L105
1T107
交差点の情報は、自宅から距離の近い順に並んでいる。また、自宅や友人宅が交差点の中にあることはない。すなわち以下の関係を満たす。
0X1<X1+W1X2<X2+W2...XN<XN+WNL
また、青信号である時間は交差点を渡るのに十分である。すなわち以下の関係を満たす。
WiTi

出力

yuki君が自宅を出てから、友人宅に到着するまでの経過時間を1行で出力せよ。

サンプル

サンプル1
入力
1 8
5 2 2
出力
11

交差点についた時点では信号は青であるが、そのまま進むと交差点を渡りきる前に信号が赤になってしまう。
そのため、交差点の手前で次の青信号まで時間3だけ待機する。

サンプル2
入力
3 10
1 2 10
3 4 20
7 3 30
出力
10

いずれの交差点でも待機する必要はない。今日は運の良い日だ。

サンプル3
入力
4 20
3 2 2
6 3 3
10 2 9
15 3 5
出力
35

全ての交差点で信号待ちになってしまった。運の無い日もあるものだ。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。