95633


AtCoder の以下の問題 ([ABC248-B](https://atcoder.jp/contests/abc248/tasks/abc248_b))
について、ループを回して不等式を満たす最小の整数 `i` を求めることでACになりました。

> a*k^n≧bを満たす最小の非負整数nを求めよ。(a,b,kは自然数。k≧2)

それとは別に、直接、上の不等式を解くという方法も考えられます。  
それでやってみたのが以下のコードなのですが、一つだけWAになりました。原因がわかりません。

[code]

    a,b,k=gets.chomp.split(" ").to_a.map(&:to_i)
    puts Math::log((b/a.to_f),k).ceil
    
[/code]


CC BY-SA 4.0
2023-07-15T02:06:12.653
95625
2023-07-15T05:22:21.797
2023-07-15T05:22:21.797
3060
54984
question
ruby
Rubyで指数不等式を解く


AtCoderのテストケースは以下の場所で公開されています。  
<https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0>

WAになるテストケースを見てみると、以下のような入力となっています。

[code]

    1 536870912 2
    
[/code]

こちらの正しい出力は`29`ですが、ご提示のコードだと`30`が出力されます。

計算過程を追ってみると、`Math::log((b/a.to_f),k)`の結果が間違っていることが分かります。  
`536870912`が`2 ** 29`なので、`Math::log(536870912.0,2)` =
`29.0`となるべきなのに、実際に計算してみると誤差が入って`29.000000000000004`になってしまいます。こちらを切り上げて、`30`という誤った結果となっています。

浮動小数点数は誤差が入る可能性があるため、誤差が許容できない状況で使うのは避けるべきです。  
特に、競技プログラムでは、このような誤差は狙い撃ちされます。  
ケース名が「04_hack_log_01.txt」となっていることからも、`log`を使うとWAになるようにあえて追加されたテストケースであることは明白です。


CC BY-SA 4.0
2023-07-15T04:21:59.400
95633
2023-07-15T04:21:59.400
43506
95625
answer