結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 230 ms
76,640 KB
testcase_01 AC 177 ms
75,968 KB
testcase_02 AC 233 ms
76,580 KB
testcase_03 AC 235 ms
76,688 KB
testcase_04 AC 230 ms
76,776 KB
testcase_05 AC 229 ms
76,400 KB
testcase_06 AC 226 ms
76,564 KB
testcase_07 AC 233 ms
76,828 KB
testcase_08 AC 233 ms
76,612 KB
testcase_09 AC 177 ms
76,040 KB
testcase_10 AC 242 ms
76,528 KB
testcase_11 AC 228 ms
76,336 KB
testcase_12 AC 225 ms
76,424 KB
testcase_13 AC 231 ms
76,828 KB
testcase_14 WA -
testcase_15 AC 227 ms
76,748 KB
testcase_16 WA -
testcase_17 AC 168 ms
76,076 KB
testcase_18 AC 226 ms
76,524 KB
testcase_19 AC 232 ms
76,684 KB
testcase_20 AC 221 ms
76,728 KB
testcase_21 AC 237 ms
76,580 KB
testcase_22 AC 169 ms
76,128 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 229 ms
76,624 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