［補助］DFS/BFS演算子の挿入

🔔 質問する

N個の数からなる数列A 1、A 2、…ANを提供します.数と数の間に挿入できるN-1演算子もあります.演算子は、加算(+)、減算(-)、乗算(x)、および除算(%)のみから構成されます.数と数の間に演算子を追加して式を生成することができますが、与えられた数の順序を変更することはできません.たとえば、6つの数列が1、2、3、4、5、6の場合、与えられた演算子が2つの加算(+)、1つの減算(-)、1つの乗算(x)、1つの除算(%)の場合、合計60の式を作成できます.たとえば、次のフォーマットを作成できます.
1 + 2 + 3 - 4 x 5 % 6
1 % 2 + 3 + 4 - 5 x 6
1 + 2 % 3 x 4 - 5 + 6
1 % 2 x 3 - 4 + 5 + 6
式の計算は、演算子の優先度を無視し、前から開始する必要があります.なお、除算は整数除算の一部のみをとる.負の値を正の値で割った場合、C+14の条件に従います.正数に変えて1部取って、負数に変えます.したがって、上記の4つの式を計算した結果は、次のようになります.
1 + 2 + 3 - 4 x 5 % 6 = 1
1 % 2 + 3 + 4 - 5 x 6 = 12
1 + 2 % 3 x 4 - 5 + 6 = 5
1 % 2 x 3 - 4 + 5 + 6 = 7
N個の数とN-1個の演算子を指定する場合は、生成できる結果の最大値と最小値を求めるプログラムを作成します.

入力

の1行目の数字N(2<=N<=11).

の2行目はA 1、A 2、...ANを提供します.(1<=Ai<=100)

行目には4つの整数があり、その和はN−1であり、加算(+)、減算(-)、乗算(x)、除算(%)の順である.

しゅつりょく

第1行は、生成可能な式の最上位値を出力する.

行目は最大値を出力します.

最高値

および最高値は、常に−10億以上であり、10億未満の入力のみである.前から計算を開始すると、中間計算の結果は常に−10億以上、10億以下である.

🎯 解答方法

この問題は、最大11個の数が与えられると、各数と個数の間に
4則演算のいずれかを挿入した場合には,発生可能な結果の最値および最切り上げを求めることができる.したがって、(完全ナビゲーション)DFSまたはBFSを使用して、全ての場合の数を計算することができる.この問題では各準則演算を繰り返し使用できるため,この問題を解決するには繰返しシーケンスを計算する必要がある.たとえば、n=4の場合、4つの演算で3つのリストを抽出するために繰り返しを許可することを考慮する必要があります.これはPythonの繰り返しシーケンスライブラリでも見つけることができます.ただし,本問題の解答ソースコードはitertoolsの繰返しシーケンスクラスではなくDFSを用いて解決する.

💻 Pythonコード

n = int(input())
# 연산을 수행하고자 하는 수 리스트
data = list(map(int, input().split()))
# 더하기, 빼기, 곱하기, 나누기 연산자 개수
add, sub, mul, div = map(int, input().split())

# 최솟값과 최댓값 초기화
min_value = 1e9
max_value = -1e9

# 깊이 우선 탐색(dfs) 메서드
def dfs(i, now):
    global min_value, max_value, add, sub, mul, div

    # 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
    if i == n:
        min_value = min(min_value, now)
        max_value = max(max_value, now)
    else:
        # 각 연산자에 대하여 재귀적으로 호출
        if add > 0:
            add -= 1
            dfs(i+1, now+data[i])
            add += 1
        if sub > 0:
            sub -= 1
            dfs(i+1, now-data[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i+1, now*data[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i+1, int(now/data[i]))
            div += 1

dfs(1, data[0])

print(max_value)
print(min_value)