結果

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

ソースコード

diff # 

import sys
import re
from itertools import permutations
from itertools import groupby

def evaluate_expression(s):
    tokens = re.findall(r'(\d+|[\+|-])', s)
    if not tokens:
        return 0
    current = int(tokens[0])
    for i in range(1, len(tokens), 2):
        op = tokens[i]
        next_num = int(tokens[i+1])
        if op == '+':
            current += next_num
        elif op == '-':
            current -= next_num
        else:
            raise ValueError("Invalid operator")
    return current

def generate_group_sizes(d, k):
    if k == 1:
        yield (d,)
        return
    for first in range(1, d - (k-1) + 1):
        for rest in generate_group_sizes(d - first, k-1):
            yield (first,) + rest

def main():
    n = int(sys.stdin.readline())
    cards = sys.stdin.readline().split()
    digits = []
    operators = []
    for c in cards:
        if c in '+-':
            operators.append(c)
        else:
            digits.append(c)
    o = len(operators)
    k = o + 1
    d = len(digits)
    if d < k:
        print(0, 0)
        return

    seen = set()
    unique_perms = []
    for perm in permutations(digits):
        if perm not in seen:
            seen.add(perm)
            unique_perms.append(perm)

    group_size_gen = list(generate_group_sizes(d, k))

    max_val = -float('inf')
    min_val = float('inf')

    for perm in unique_perms:
        for group_sizes in group_size_gen:
            current = 0
            groups = []
            valid = True
            for size in group_sizes:
                if current + size > len(perm):
                    valid = False
                    break
                group = perm[current:current+size]
                current += size
                groups.append(group)
            if not valid:
                continue

            numbers = []
            for group in groups:
                num_str = ''.join(group)
                num = int(num_str)
                numbers.append(num)

            unique_op_perms = set(permutations(operators))
            for op_perm in unique_op_perms:
                expr_parts = [str(numbers[0])]
                for i in range(len(op_perm)):
                    expr_parts.append(op_perm[i])
                    expr_parts.append(str(numbers[i+1]))
                expr = ''.join(expr_parts)
                try:
                    value = evaluate_expression(expr)
                except:
                    continue
                if value > max_val:
                    max_val = value
                if value < min_val:
                    min_val = value

    print(max_val, min_val)

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