結果

問題 No.1633 Sorting Integers (Multiple of 2^K)
ユーザー gew1fw
提出日時 2025-06-12 20:42:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,470 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 81,944 KB
実行使用メモリ 99,940 KB
最終ジャッジ日時 2025-06-12 20:42:41
合計ジャッジ時間 5,958 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 3 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N = int(sys.stdin.readline().strip())
    c = list(map(int, sys.stdin.readline().split()))
    
    max_k = 30  # Since 2^30 is about 1e9, which is manageable
    for k in range(max_k, 0, -1):
        target = 1 << k  # 2^k
        m = min(k, N)
        if m < k:
            # Check if target has exactly N digits and matches the counts
            s = str(target)
            if len(s) != N:
                continue
            cnt = [0] * 9
            for ch in s:
                d = int(ch)
                cnt[d-1] += 1
            # Compare with c
            match = True
            for i in range(9):
                if cnt[i] != c[i]:
                    match = False
                    break
            if match:
                print(k)
                return
        else:
            # Perform BFS for m digits
            visited = set()
            initial_mod = 0
            initial_digits = tuple([0]*9)
            queue = deque()
            queue.append((initial_mod, initial_digits))
            visited.add((initial_mod, initial_digits))
            found = False
            for step in range(m):
                level_size = len(queue)
                for _ in range(level_size):
                    current_mod, digits_used = queue.popleft()
                    for d in range(1, 10):
                        if digits_used[d-1] >= c[d-1]:
                            continue
                        new_digits = list(digits_used)
                        new_digits[d-1] += 1
                        new_digits_tuple = tuple(new_digits)
                        new_mod = (current_mod * 10 + d) % target
                        if (new_mod, new_digits_tuple) not in visited:
                            visited.add((new_mod, new_digits_tuple))
                            queue.append((new_mod, new_digits_tuple))
            # Check if any state after m steps has mod 0
            for state in queue:
                mod, digits = state
                if mod == 0:
                    valid = True
                    for i in range(9):
                        if digits[i] > c[i]:
                            valid = False
                            break
                    if valid:
                        found = True
                        break
            if found:
                print(k)
                return
    print(0)

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