結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:55:17
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,003 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 653,068 KB
最終ジャッジ日時 2025-03-20 20:56:07
合計ジャッジ時間 5,873 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 MLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    N = int(sys.stdin.readline().strip())
    c = list(map(int, sys.stdin.readline().split()))
    
    # Convert c_1 to c_9 to 1-based indexes (digits 1..9)
    # Index 0 is unused
    sum_even = sum([c[1], c[3], c[5], c[7]])
    if sum_even == 0:
        print(0)
        return
    
    max_num = 10 ** N - 1
    max_s = 0
    if max_num > 0:
        max_s = min((max_num).bit_length(), 60)  # Start from a reasonable upper bound
    else:
        max_s = 0
    
    found = False
    for s in range(max_s, -1, -1):
        mod_val = 1 << s  # 2^s
        if mod_val == 0:
            continue
        if mod_val > max_num:
            continue
        
        # Now check if any permutation of digits is divisible by mod_val
        # multipliers are 10^0, 10^1, ..., 10^(N-1) mod mod_val
        multipliers = [pow(10, i, mod_val) for i in range(N)]
        # We need to use exactly the counts in c, sum N digits
        
        from functools import lru_cache
        
        # We need to turn counts into a tuple for memoization
        initial_counts = c.copy()
        
        # Using LRU cache with limited size might help, but need to convert counts to a tuple
        @lru_cache(maxsize=None)
        def backtrack(pos, remainder, counts_tuple):
            if pos == N:
                return (remainder % mod_val) == 0
            counts = list(counts_tuple)
            for d in range(1, 10):
                if counts[d-1] <= 0:
                    continue
                new_counts = counts.copy()
                new_counts[d-1] -= 1
                new_remainder = (remainder + d * multipliers[pos]) % mod_val
                if backtrack(pos + 1, new_remainder, tuple(new_counts)):
                    return True
            return False
        
        if backtrack(0, 0, tuple(initial_counts)):
            print(s)
            found = True
            break
    
    if not found:
        print(0)

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