結果

問題 No.10 ＋か×か
ユーザー lam6er
提出日時 2025-03-31 17:52:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 263 ms / 5,000 ms
コード長 830 bytes
コンパイル時間 181 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 127,996 KB
最終ジャッジ日時 2025-03-31 17:53:48
合計ジャッジ時間 1,870 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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