Tax Included Price

問題

A - Tax Included Price

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44471413 - AtCoder Regular Contest 118

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

公式解説とは異なるやり方だが解けた

以下、解法を書く。

税込価格を変形して、
$\lfloor \frac{100+t}{100}A \rfloor = \lfloor (1+\frac{t}{100})A \rfloor = \lfloor (A+\frac{t}{100}A) \rfloor = A + \lfloor (\frac{t}{100}A) \rfloor$

例えば、t=10の時、$\lfloor (\frac{t}{100}A) \rfloor$は以下のようになる。
A=1..10の時、0
A=10..20の時、1

t=3の時、
A=1..33の時、0
A=34..67の時、1
A=68..101の時、2

つまり、$\lfloor (\frac{t}{100}A) \rfloor$の値が切り替わる時、税込価格として現れないものが出現する。
1番目に小さい値は、$\lfloor (\frac{t}{100}A) \rfloor$が1になる一つ前になる。
2番目に小さい値は、$\lfloor (\frac{t}{100}A) \rfloor$が2になる一つ前になる。
そこで、二分探索を用いて$\lfloor (\frac{t}{100}A) \rfloor$の値がN以上になるところを探し、その一つ前を出力する。