結果

問題 No.1152 10億ゲーム
ユーザー smallcopse
提出日時 2020-08-07 23:09:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,561 bytes
コンパイル時間 136 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 27,824 KB
平均クエリ数 24.08
最終ジャッジ日時 2024-07-17 05:12:29
合計ジャッジ時間 8,473 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def main():
    x1, x2 = map(int, input().split())
    # 素因数分解して2の数と5の数を数える
    y1 = prime_factorize(x1)
    y2 = prime_factorize(x2)
    my_n2 = y1.count(2)
    my_n5 = y1.count(5)
    kiri_n2 = y2.count(2)
    kiri_n5 = y2.count(5)
    # print(y1, my_n2, my_n5)
    # print(y2, kiri_n2, kiri_n5)
    # 戦略: 2の数と5の数が相手と一致するように数を選んでいく
    turn = 1
    while x1 != x2 and turn <= 35:
        # 自分の番
        # 2の数の差と5の数の差のうち、差の大きいほうの差を小さくする
        if abs(my_n2 - kiri_n2) > abs(my_n5 - kiri_n5):
            if my_n2 < kiri_n2:
                my_n2 += 1
                x1 *= 2
            elif my_n2 > kiri_n2:
                my_n2 -= 1
                x1 = x1 // 2
        else:
            if my_n5 < kiri_n5:
                my_n5 += 1
                x1 *= 5
            elif my_n5 > kiri_n5:
                my_n5 -= 1
                x1 = x1 // 5
        
        print(x1, flush=True)
        # 一致したら終了
        if x1 == x2:
            return

        x2 = int(input())
        y2 = prime_factorize(x2)
        kiri_n2 = y2.count(2)
        kiri_n5 = y2.count(5)

        turn += 1
if __name__ == '__main__':
    main()
0