結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
コンテスト
ユーザー H3PO4
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 10 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

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