CodeForces #266_Div2 : B. Wonder Room
問題
入力として、が与えられる。
はそれぞれ部屋の縦、横の長さであり、部屋の面積を 以上にしたい。
を満たすように、 の長さを拡張した時の 最小の面積を求めよ。
落とし穴が多く、roomでは解けた人が一人もいなかった。
解法
各値の制約が ~ と大きいため長さを全通り試すことはできない。
作りたい面積が 以上 ということから、 a, bの内小さい方は必ず 以下になることが分かる。
よってa, bの内小さい方(mとする)を まで探索すれば良い。 大きい方の辺は となる。
計算量は