結果

問題 No.297 カードの数式
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:12:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,539 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 77,560 KB
最終ジャッジ日時 2025-04-15 22:13:48
合計ジャッジ時間 5,185 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools
from itertools import permutations, combinations

def generate_splits(digits, k):
    if k == 1:
        yield [digits]
        return
    seen = set()
    for i in range(1, len(digits) - k + 2):
        for indices in combinations(range(len(digits)), i):
            group = tuple(sorted([digits[j] for j in indices]))
            if group in seen:
                continue
            seen.add(group)
            remaining = [digits[j] for j in range(len(digits)) if j not in indices]
            for split in generate_splits(remaining, k-1):
                yield [list(group)] + split

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    cards = input[1:n+1]
    digits = []
    ops = []
    for c in cards:
        if c in '+-':
            ops.append(c)
        else:
            digits.append(c)
    O = len(ops)
    if O == 0:
        print(0, 0)
        return
    K = O + 1
    D = len(digits)
    if D < K:
        print(0, 0)
        return
    global_max = -float('inf')
    global_min = float('inf')
    split_count = 0
    for split in generate_splits(digits, K):
        group_max = []
        group_min = []
        for group in split:
            sorted_desc = sorted(group, reverse=True)
            max_num = int(''.join(sorted_desc))
            sorted_asc = sorted(group)
            min_num = int(''.join(sorted_asc))
            group_max.append(max_num)
            group_min.append(min_num)
        for group_order in permutations(range(K)):
            for op_perm in permutations(ops):
                current_max = group_max[group_order[0]]
                for i in range(O):
                    op = op_perm[i]
                    next_group = group_order[i+1]
                    if op == '+':
                        current_max += group_max[next_group]
                    else:
                        current_max -= group_min[next_group]
                if current_max > global_max:
                    global_max = current_max
                current_min = group_min[group_order[0]]
                for i in range(O):
                    op = op_perm[i]
                    next_group = group_order[i+1]
                    if op == '+':
                        current_min += group_min[next_group]
                    else:
                        current_min -= group_max[next_group]
                if current_min < global_min:
                    global_min = current_min
    print(global_max, global_min)

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