結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
ユーザー H3PO4H3PO4
提出日時 2024-04-14 10:22:13
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,625 bytes
コンパイル時間 183 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 85,876 KB
最終ジャッジ日時 2024-04-14 10:22:28
合計ジャッジ時間 13,396 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 243 ms
76,876 KB
testcase_01 AC 175 ms
76,548 KB
testcase_02 AC 237 ms
76,656 KB
testcase_03 AC 298 ms
76,592 KB
testcase_04 AC 239 ms
76,524 KB
testcase_05 AC 235 ms
76,384 KB
testcase_06 AC 233 ms
76,844 KB
testcase_07 AC 235 ms
76,724 KB
testcase_08 AC 258 ms
76,636 KB
testcase_09 AC 227 ms
76,024 KB
testcase_10 AC 243 ms
76,592 KB
testcase_11 AC 230 ms
76,648 KB
testcase_12 AC 230 ms
76,572 KB
testcase_13 AC 238 ms
76,684 KB
testcase_14 WA -
testcase_15 AC 243 ms
76,700 KB
testcase_16 WA -
testcase_17 AC 177 ms
76,188 KB
testcase_18 AC 234 ms
76,652 KB
testcase_19 AC 239 ms
76,484 KB
testcase_20 AC 314 ms
76,716 KB
testcase_21 AC 236 ms
76,540 KB
testcase_22 AC 171 ms
76,308 KB
testcase_23 RE -
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 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 AC 234 ms
76,524 KB
権限があれば一括ダウンロードができます

ソースコード

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(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[i] * 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 x != sum(ct):
                    # nの十進表記がx桁未満のため，0が必要になってしまう場合
                    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(C))
0