整数 \(A\) の税込み価格を、\(f(A)\) と表すことにします。

---

◆解法1：周期性の利用

\(A\) が \(100\) 増加すると、\(\frac{100+t}{100}A\) は \(100+t\) 増加、したがって \(f(A+100) = f(A) + (100 + t)\) が成り立ちます。

このことから、「正の整数 \(x\) が税込み価格として現れるか否か」は、周期 \(100+t\) を持つことが分かります。例えば、【入力例2】 の消費税率が \(3\) パーセントの場合には、税込み価格として現れない金額は

\[(34,68,102), (137,171,205), (240,274,308), \ldots\]

のように、\(100+t = 103\) 以下の値 \((34,68,102)\) から始まり周期 \(103\) の規則になります。

結局、本問は次のようにして解くことができます。

• \(f(1), \ldots, f(100)\) を計算することで、\(100 + t\) 以下のどの金額が税込み価格として現れないのかを計算する。
• 税込み価格として現れない金額のうち \(N\) 番目が、何回目の周期の何番目の金額であるかを求める。それを利用して答を求める。

この解法の時間計算量は \(O(1)\) です。

【解答例】 https://atcoder.jp/contests/arc118/submissions/22160671 （Python, \(O(1)\) 時間）

---

◆解法2：数え上げ・二分探索の利用

例えば消費税率が \(10\%\) のとき、\(f(100) = 110\) です。また、異なる商品の税込み価格は異なるので、

• \(1, 2, \ldots, 110\) のうち税込み価格として現れる金額は \(100\) 通り
• したがって、\(1, 2, \ldots, 110\) のうち税込み価格として現れない金額は \(10\) 通り

であると分かります。このようにして、ある特定の税込み価格以下に、税込み価格として現れない金額が何通りあるのかを \(O(1)\) 時間で計算できます。税込み価格 \(f(A)\) 以下では、税込み価格として現れない金額は \(f(A) - A\) 通りです。

このことと二分探索を利用することで、次を満たす最大の \(A\) を計算できます。

• \(f(A)\) 以下の金額のうち、税込み価格として現れない金額は \(N\) 通り未満である

なお二分探索の上限として \(100N\) をとることができることも、上述の考察から分かります。このとき、答は \(f(A)\) より大きく \(f(A+1)\) より小さいです。\(t \leq 100\) という条件下で \(f(A+1) \leq f(A) + 2\) が成り立つので、\(f(A) + 1\) が答となります。

この解法の時間計算量は \(O(\log N)\) です。

【解答例 (Python)】 https://atcoder.jp/contests/arc118/submissions/22160677 （Python, \(O(\log N)\) 時間）

---

計算誤差について

\(f(A)\) を、

• 実数 \(x = (100+t) / 100 \times A\) を求める
• \(\lfloor x\rfloor\) を求める

というような手順で計算した場合、正しく \(f(A)\) が計算できない可能性があります。例えば

• Python で x = int(113 / 100 * 100)
• C++ で int x = 113 / 100.0 * 100;

といった計算を行うと、\(x = 112\) という「誤った計算結果」になっていることが確かめられます。

実数 \(x\) がぴったり整数であった場合には任意の正の実数 \(\varepsilon > 0\) に対して \(\lfloor x\rfloor \neq \lfloor x - \varepsilon\rfloor\) となるので、\(x\) を絶対誤差 \(\varepsilon\) 以下で計算した場合であっても \(\lfloor x \rfloor\) の値が誤って計算されてしまう可能性があります。この問題は、いくら計算精度を高くしても解消されません。切り捨て後の正確な値が必要なのであれば、計算の方法を改める必要があります。

今回の問題・制約では、

• 整数型の切り捨て除算を用いて、\((100+t)\times A\) を \(100\) で割る形で \(f(A)\) を計算する
• \(x = (100+t) / 100 \times A\) を小数で計算したあと、小さな値を加えてから切り捨てる（\(\lfloor x\rfloor\) の代わりに \(\lfloor x + 0.001\rfloor\) などを計算する）

のような形で \(f(A)\) を計算すると、正しく \(f(A)\) が計算できます。