結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
ユーザー H3PO4H3PO4
提出日時 2024-04-14 10:27:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,526 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 90,508 KB
最終ジャッジ日時 2024-10-03 07:25:33
合計ジャッジ時間 8,046 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 180 ms
83,420 KB
testcase_01 AC 137 ms
76,236 KB
testcase_02 AC 175 ms
76,240 KB
testcase_03 WA -
testcase_04 AC 170 ms
76,572 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 175 ms
76,332 KB
testcase_08 WA -
testcase_09 AC 139 ms
76,072 KB
testcase_10 WA -
testcase_11 AC 166 ms
76,496 KB
testcase_12 WA -
testcase_13 AC 177 ms
76,480 KB
testcase_14 AC 169 ms
76,460 KB
testcase_15 WA -
testcase_16 AC 180 ms
76,768 KB
testcase_17 AC 127 ms
76,092 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 185 ms
76,460 KB
testcase_22 AC 131 ms
76,188 KB
testcase_23 TLE -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import permutations


def int2digits(n):
    digits = [0] * 10
    while n:
        digits[n % 10] += 1
        n //= 10
    return digits


def f(n):
    ct = 0
    while not n & 1:
        ct += 1
        n >>= 1
    return ct


def solve(N, C):
    # step 1. 下8桁で2^8の倍数になっているものが存在するか？
    X = 8
    cands = []
    for n in range(1 << X, 10**X, 1 << X):
        ct = int2digits(n)
        if all(ct[i] <= C[i] for i in range(10)):
            cands.append((n, ct))

    if cands:
        # 下8桁で2^8の倍数になっているものが存在する場合: 下8桁を固定して全探索
        ans = 0
        for n, ct in cands:
            rest_digits = []
            for i in range(10):
                rest_digits.extend([i] * (C[i] - ct[i]))
            for perm in permutations(rest_digits):
                m = n
                for i, p in enumerate(perm, start=sum(ct)):
                    m += p * 10**i
                ans = max(ans, f(m))
        return ans

    else:
        # 下8桁で2^8の倍数になっているものが存在しない場合: 桁数を減らしていく
        for x in range(X - 1, 0, -1):
            for n in range(1 << x, 10**x, 1 << x):
                ct = int2digits(n)
                if N > sum(ct):
                    continue
                if all(ct[i] <= C[i] for i in range(10)):
                    return x
        return 0


N = int(input())
C = [0] + list(map(int, input().split()))
print(solve(N, C))
0