結果

問題 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
コンパイル時間 178 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 27,880 KB
平均クエリ数 24.68
最終ジャッジ日時 2024-07-17 05:09:22
合計ジャッジ時間 8,443 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 110 ms
27,360 KB
testcase_01 AC 108 ms
27,232 KB
testcase_02 RE -
testcase_03 RE -
testcase_04 AC 108 ms
27,744 KB
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 AC 109 ms
27,360 KB
testcase_09 AC 108 ms
27,136 KB
testcase_10 AC 110 ms
27,488 KB
testcase_11 AC 110 ms
27,488 KB
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 AC 108 ms
27,360 KB
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 AC 110 ms
27,360 KB
testcase_21 AC 110 ms
27,232 KB
testcase_22 AC 111 ms
27,360 KB
testcase_23 AC 110 ms
27,232 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 110 ms
27,496 KB
testcase_39 AC 109 ms
27,488 KB
testcase_40 AC 110 ms
27,232 KB
testcase_41 AC 109 ms
27,104 KB
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 AC 111 ms
27,368 KB
testcase_47 AC 112 ms
27,240 KB
testcase_48 AC 111 ms
27,232 KB
testcase_49 AC 111 ms
27,616 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