AtCoderABC146 CでWAになる原因

Question

問題はこちらです
ソースコードを提出した際に、2つWA判定がついてしまい、自分では原因が特定できませんでした。

a, b, x = list(map(int, input().split()))

k = 0
for i in range(1, 10):
    kN = (x / a) - (b * i / a)
    if kN < 1: # 買えるものがない
        k = 0
        break
    if len(str(int(kN))) == i:
        k = int(kN) # 切り捨て
        break
else:
    k = 1000000000

print(k)

していることは、
x >= a * n + b * d(N)より、
n <= x / a - b * d(N) / Aと変形し、この条件を満たす最大のnを求めます。
この際に、d(N)の桁数をiと置き、仮定しkNの整数部分の桁数がiと一致するか否かで判定しています。

何かお気づきになられた点がありましたら、よろしくお願いいたします。

Answer 1

おそらく割り算の計算を浮動小数点でやってることで誤差が出ています。
この問題ではxの値が10 ** 18と相当大きいので倍精度の浮動小数点でも精度が足りません。

byFloat = int((10 ** 18 - 1) / 10 ** 9)
byInt = (10 ** 18 - 1) // 10 ** 9
print(byFloat) #=> 1000000000
print(byInt) #=> 999999999

#もっとわかりやすい例でいえば
print(int(999999999999999999.0)) #=> 1000000000000000000

式を変形して整数の割り算として書き直せば回避できます。

Comments

[sub_machida]

助かりました、ありがとうございます