結果

問題 No.10 ＋か×か
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:52:38
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 308 ms / 5,000 ms
コード長 830 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 183 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 127,972 KB
最終ジャッジ日時 2025-12-06 15:05:05
合計ジャッジ時間 2,004 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

n = int(input())
total = int(input())
a = list(map(int, input().split()))

stack = []
stack.append((0, a[0], ""))
visited = set()
found = False

while stack:
    i, current, ops = stack.pop()
    if i == n - 1:
        if current == total:
            print(ops)
            found = True
            break
        continue
    if (i, current) in visited:
        continue
    visited.add((i, current))
    next_num = a[i + 1]
    # We want to try '+' first, so append '*' first then '+'
    # because stack is LIFO
    new_mult = current * next_num
    if new_mult <= total:
        stack.append((i + 1, new_mult, ops + "*"))
    new_plus = current + next_num
    if new_plus <= total:
        stack.append((i + 1, new_plus, ops + "+"))

# According to the problem statement, a solution exists, so no need to handle not found case
0