問題一覧 > 通常問題

No.139 交差点

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

問題文

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

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

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

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

入力

各入力は以下の形式で与えられる。値はいずれも整数である。
\(N\) \(L\)
\(X_1\) \(W_1\) \(T_1\)
\(X_2\) \(W_2\) \(T_2\)
...
\(X_N\) \(W_N\) \(T_N\)

\(1 \le N \le 100\)
\(1 \le L \le 10^5\)
\(1 \le T \le 10^7\)
交差点の情報は、自宅から距離の近い順に並んでいる。また、自宅や友人宅が交差点の中にあることはない。すなわち以下の関係を満たす。
\(0 \le X_1 \lt X_1+W_1 \le X_2 \lt X_2+W_2 \le ... \le X_N \lt X_N+W_N \le L\)
また、青信号である時間は交差点を渡るのに十分である。すなわち以下の関係を満たす。
\(W_i \le T_i\)

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。