結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 15:32:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,749 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,608 KB
実行使用メモリ 91,016 KB
最終ジャッジ日時 2025-06-12 15:34:03
合計ジャッジ時間 5,367 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from functools import lru_cache

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(stdin.readline())
    c = list(map(int, stdin.readline().split()))
    digits = [i+1 for i in range(9) for _ in range(c[i])]

    max_k = 46
    for k in range(max_k, -1, -1):
        s = min(k, N)
        required = 1 << k
        max_num = (10 ** s) - 1
        if required > max_num:
            continue

        even_digits = [d for d in digits if d % 2 == 0]
        if k >= 1 and len(even_digits) < 1:
            continue

        from collections import defaultdict
        counts = defaultdict(int)
        for d in digits:
            counts[d] += 1

        used = [False] * len(digits)
        target = required

        def backtrack(pos, rem, remaining_counts):
            if pos == s:
                return rem == 0
            for d in remaining_counts:
                if remaining_counts[d] == 0:
                    continue
                new_rem = (rem * 10 + d) % target
                new_counts = remaining_counts.copy()
                new_counts[d] -= 1
                if backtrack(pos + 1, new_rem, new_counts):
                    return True
            return False

        initial_counts = defaultdict(int)
        for d in digits:
            initial_counts[d] += 1

        success = False
        for d in initial_counts:
            if initial_counts[d] == 0:
                continue
            new_counts = initial_counts.copy()
            new_counts[d] -= 1
            if backtrack(1, d % target, new_counts):
                success = True
                break

        if success:
            print(k)
            return

    print(0)

if __name__ == '__main__':
    main()
0