結果

問題 No.1152 10億ゲーム
ユーザー smallcopsesmallcopse
提出日時 2020-08-07 23:03:07
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,452 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 10,736 KB
実行使用メモリ 24,560 KB
平均クエリ数 24.68
最終ジャッジ日時 2023-09-24 04:54:59
合計ジャッジ時間 6,239 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 69 ms
23,888 KB
testcase_01 AC 67 ms
23,940 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 AC 69 ms
24,240 KB
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 AC 65 ms
24,388 KB
testcase_09 AC 66 ms
24,092 KB
testcase_10 AC 67 ms
23,900 KB
testcase_11 AC 67 ms
23,640 KB
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 AC 68 ms
24,192 KB
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 AC 66 ms
23,880 KB
testcase_21 AC 65 ms
23,848 KB
testcase_22 AC 77 ms
23,460 KB
testcase_23 AC 70 ms
23,704 KB
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 AC 66 ms
24,080 KB
testcase_39 AC 68 ms
24,560 KB
testcase_40 AC 67 ms
23,768 KB
testcase_41 AC 68 ms
24,044 KB
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 AC 64 ms
24,120 KB
testcase_47 AC 67 ms
24,392 KB
testcase_48 AC 80 ms
24,412 KB
testcase_49 AC 84 ms
24,000 KB
権限があれば一括ダウンロードができます

ソースコード

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)
    # 戦略: 2の数と5の数が相手と一致するように数を選んでいく

    while x1 != x2:
        # 自分の番
        # 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)

if __name__ == '__main__':
    main()
0