きままにものづくり

日々の気付いたことなんかを書いてます。

SRM616Div1Easy

問題

N個( N \leq 50)のアラームが与えられる。各アラームは、start_ivolume_i period_i(\leq 10)の間隔で鳴らすようになっている。Alexは眠気指数Sを持っており、毎分Dずつ増えていく。これが0以下になると目覚める。Alexが起きることができる最大のSを求めよ。

解法

アラーム全体での周期を求め、シミュレートすることで求まる。アラーム全体の周期Fはperiod_iの最大公約数で求まる。Fの最大値は、period_i \leq 10なので、 2^3 * 3*2 * 5* 7でも泊まる。

計算量

O(FN)
F: アラーム全体の周期
N: アラームの数

コード

広告を非表示にする