結果

問題 No.1793 実数当てゲーム
コンテスト
ユーザー NyaanNyaan
提出日時 2021-12-22 01:09:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 241 ms / 2,000 ms
コード長 907 bytes
コンパイル時間 458 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 93,928 KB
平均クエリ数 2230.56
最終ジャッジ日時 2024-09-28 13:28:28
合計ジャッジ時間 6,105 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
(解法)
L = 0.9e-6, R = 12.22e74 として、毎回 L, R の調和平均を取って適宜二分探索 & 解答を行えばよい。

(証明)
(i) x >= 10^{-5}
log R - log L = 184.5126...
1og (1 + 1e-5) * (2 ** 24) = 167.7713... なので
(log R - log L) / (2 ** 25) < log (1 + 1e-5) が成り立つ。
よって対数上で二分探索すれば相対誤差の範囲に収まる。
(ii) x < 10^{-5}
二分探索をすると exp(log L + (log R - log L) / 2^25) = 0.00000900004... が出力される。
よって絶対誤差の範囲に収まる。
"""

from math import sqrt

def sol():
  lo = 0.9e-5
  hi = 12.2200001e74
  for _ in range(24):
    me = sqrt(lo * hi)
    print("? {:.100f}".format(me), flush=True)
    res = input()
    if res == "Yes":
      lo = me
    else:
      hi = me
  me = sqrt(lo * hi)
  print("! {:.100f}".format(me), flush=True)


T = int(input())
for _ in range(T):
  sol()
0