結果

問題 No.2357 Guess the Function
ユーザー navel_tosnavel_tos
提出日時 2023-06-23 22:13:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,267 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,616 KB
実行使用メモリ 88,916 KB
平均クエリ数 2.82
最終ジャッジ日時 2024-07-01 01:57:27
合計ジャッジ時間 2,169 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder394A

'''
xを選ぶ。x+A % B を訊ねる。

中国剰余定理に持ち込みたいが、さてどうする。

x=0 とすればAが割れないか？そんなことないか。x=1でよさそうか。
0が返ってきた場合、A+1=B が保障される。えー　詰みか？

わからないのでバカ全探索しておく。
'''

'''
■全探索: x=50 のときにうまくいくらしい

for x in range(1,101):  #1個目の質問
    C=[set() for _ in range(101)]  #質問xの余りごとに分類
    for A in range(1,100):
        for B in range(A+1,101):
            C[(x+A)%B].add((A,B))
    #2個目の質問を行う 分類ごとに質問を変えて良い
    for St in C:
        for y in range(1,101):
            if x==y: continue
            Z=set(); hantei=1
            for now in St:
                A,B=now
                t=(y+A)%B
                if t in Z: hantei=0
                else: Z.add(t)
            if not hantei: continue
            else: break
        else: break
    else: print(x); break
'''

#x=50 のときの分類を行う
C=[set() for _ in range(101)]; x=50
for A in range(1,100):
    for B in range(A+1,101):
        C[(50+A)%B].add((A,B))

#余りごとに対応を考える
print('?',50)
N=int(input()); Candidate=C[N]
if len(Candidate)==1:
    for A,B in Candidate: print('!',A,B); exit()

#残り候補から絞り込みを行う
for y in range(1,101):
    Z=set()
    for A,B in Candidate:
        Z.add((y+A)%B)
    if len(Z)!=len(Candidate): continue
    else: break

print('?',y); M=int(input())

#候補を全探索し、余りがMになるものを探す
for A,B in Candidate:
    if (y+A)%B==M: print('!',A,B)

#バグ探索
C=[set() for _ in range(101)]; x=50; ZZ=[0]*101
for A in range(1,100):
    for B in range(A+1,101):
        C[(50+A)%B].add((A,B))

for i in range(101):
    Cndd=C[i]
    for y in range(1,101):
        Z=set()
        for A,B in Cndd:
            Z.add((y+A)%B)
        if len(Z)!=len(Cndd): continue
        else: break
    ZZ[i]=y

def check(A,B):
    N=(50+A)%B; M=(ZZ[N]+A)%B
    return (N,M)

def solve(N,M):
    Candidate=C[N]
    if len(Candidate)==1:
        for A,B in Candidate: return (A,B)
    for A,B in Candidate:
        if (ZZ[N]+A)%B==M: return (A,B)
0