SRM616Div1Easy
問題
N個()のアラームが与えられる。各アラームは、
に
を
の間隔で鳴らすようになっている。Alexは眠気指数Sを持っており、毎分Dずつ増えていく。これが0以下になると目覚める。Alexが起きることができる最大のSを求めよ。
解法
アラーム全体での周期を求め、シミュレートすることで求まる。アラーム全体の周期Fはの最大公約数で求まる。Fの最大値は、
なので、
でも泊まる。
計算量
O(FN)
F: アラーム全体の周期
N: アラームの数
N個()のアラームが与えられる。各アラームは、
に
を
の間隔で鳴らすようになっている。Alexは眠気指数Sを持っており、毎分Dずつ増えていく。これが0以下になると目覚める。Alexが起きることができる最大のSを求めよ。
アラーム全体での周期を求め、シミュレートすることで求まる。アラーム全体の周期Fはの最大公約数で求まる。Fの最大値は、
なので、
でも泊まる。
O(FN)
F: アラーム全体の周期
N: アラームの数