結果

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

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    counts = list(map(int, sys.stdin.readline().split()))
    max_k = 46
    for k in range(max_k, -1, -1):
        mod_value = 1 << k
        s = str(mod_value)
        len_s = len(s)
        if len_s > N:
            continue
        elif len_s == N:
            temp_counts = [0] * 10
            for ch in s:
                d = int(ch)
                temp_counts[d] += 1
            match = True
            for i in range(1, 10):
                if temp_counts[i] != counts[i - 1]:
                    match = False
                    break
            if match:
                print(k)
                return
        else:
            if can_form_suffix(k, mod_value, counts):
                print(k)
                return
    print(0)

def can_form_suffix(k, mod_value, counts):
    available = counts.copy()
    
    def backtrack(pos, remainder):
        if pos == k:
            return remainder == 0
        for d in range(1, 10):
            if available[d - 1] == 0:
                continue
            available[d - 1] -= 1
            new_remainder = (remainder * 10 + d) % mod_value
            if backtrack(pos + 1, new_remainder):
                available[d - 1] += 1
                return True
            available[d - 1] += 1
        return False
    
    return backtrack(0, 0)

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