ABC195B - Many Oranges


B問題なのに手間取ったのでメモ.
全探索せずに,切り上げ・切り下げで考えて沼ってしまった...

考え方1:全探索

B問題としては,全探索するのが素直.

個数$N$のパターンは高々$10^{6}$通りなので,$A \leq 1000W/N \leq B$となるもののうち,最小・最大を答えれば良い.

条件を満たすものがなければ,UNSATISFIABLE

考え方2:割り算

ナイーブに考えれば,$1000W$を一番大きい$B$で割れば最小値が求まり,$1000W$を一番小さい$A$で割れば最大値が求まる.ちゃんと式で考えないと間違えやすい.

個数を$N$とすると,条件

\begin{aligned}
& A \leq 1000W/N \leq B \\
& \Leftrightarrow
1000W / B \leq N \leq 1000W / A
\end{aligned}
を満たす$N$が実現可能である($N$を求めたいので,$N$について解いている).

特に,$N$は整数なので,

\begin{aligned}
& \Leftrightarrow
\lceil 1000W / B \rceil \leq N \leq \lfloor 1000W / A \rfloor
\end{aligned}
となる.

【参考】Editorial - Panasonic Programming Contest (AtCoder Beginner Contest 195)