結果

問題 No.1793 実数当てゲーム
ユーザー NyaanNyaanNyaanNyaan
提出日時 2021-12-22 01:09:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 907 bytes
コンパイル時間 1,657 ms
コンパイル使用メモリ 86,988 KB
実行使用メモリ 94,488 KB
平均クエリ数 2230.56
最終ジャッジ日時 2023-10-13 20:26:22
合計ジャッジ時間 6,585 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 105 ms
87,448 KB
testcase_01 AC 104 ms
87,236 KB
testcase_02 AC 274 ms
94,488 KB
testcase_03 AC 260 ms
94,044 KB
testcase_04 AC 258 ms
94,068 KB
testcase_05 AC 252 ms
94,204 KB
testcase_06 AC 257 ms
93,828 KB
testcase_07 AC 257 ms
94,160 KB
testcase_08 AC 255 ms
94,184 KB
testcase_09 AC 257 ms
94,112 KB
testcase_10 AC 258 ms
94,136 KB
testcase_11 AC 256 ms
94,396 KB
testcase_12 AC 258 ms
93,916 KB
testcase_13 AC 258 ms
94,040 KB
testcase_14 AC 263 ms
94,128 KB
testcase_15 AC 257 ms
93,912 KB
testcase_16 AC 261 ms
94,392 KB
testcase_17 AC 258 ms
93,612 KB
権限があれば一括ダウンロードができます

ソースコード

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