白準-挿入演算子(14888)

Brute Force + DFS

質問する

N個の数からなる数列A 1、A 2、…、ANが与えられた.さらに、数と数の間に埋め込むことができるN−1演算子が与えられる.演算子には、加算(+)、減算(-)、乗算(×), 除算だけで構成されています.
数と数の間に演算子を加えて、式を作ることができます.この場合,与えられた数の順序を変えることはできない.
例えば、6個の数列は1、2、3、4、5、6であり、与えられた演算子は2個の加算(+)、1個の減算(-)、および1個の乗算(×) 1つ、1つを除くと、全部で60種類の儀式ができます.たとえば、次のフォーマットを作成できます.
• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6
式の計算は、演算子の優先度を無視して前から行います.また、除法は整数除法で、商のみを取ります.負数を正数で割った場合、C+14の基準に従います.つまり、正数に変えて1部取り、それを負数に変えます.したがって,上記4つの式を計算した結果は以下の通りである.
• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7
N個の数とN-1個の演算子を指定する場合は、生成できる結果の最大値と最小値を求めるプログラムを作成します.

入力

第1行は、数の個数N(2≦N≦11)を与える.2行目はA 1,A 2,...,ANが与えられた.(1≦Ai≦100)3行目には4つの整数があり、その和はN−1であり、加算(+)個数、減算(-)個数、乗算(×)を選択します.

しゅつりょく

1行目に生成された結果の最値、2行目の出力が最上位になります.いずれにしても、演算子を挿入するには、-10億以上、10億以下の結果のみを入力します.また,先に計算を開始したときも,中間計算式の結果は常に−10億以上,10億以下であった.

import sys

input = sys.stdin.readline
N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

min_, max_ = 1e9, -1e9

def dfs(i, res, add, sub, mul, div): # res => 단계별 연산결과(현재 연산하는 위치)
    global max_, min_
    if i == N: # 주어진 숫자 배열의 인덱스 범위를 넘어서면 연산을 멈추고 최대, 최소를 구한다.
        max_ = max(res, max_)
        min_ = min(res, min_)
        return
    else: # 해당 연산을 하면 연산에 할당된 숫자를 1씩 차감.
        if add: # 주어진 각 연산의 횟수가 0 이상일 떄
            dfs(i + 1, res + nums[i], add - 1, sub, mul, div)
        if sub:
            dfs(i + 1, res - nums[i], add, sub - 1, mul, div)
        if mul:
            dfs(i + 1, res * nums[i], add, sub, mul - 1, div)
        if div: 
            dfs(i + 1, int(res / nums[i]), add, sub, mul, div - 1)
            # int()는 나누기의 몫만 남겨준다.
            
dfs(1, nums[0], add, sub, mul, div) # 인덱스 0번째 수에 주어진 numsi = 1부터 연산을 시작한다.
print(max_)
print(min_)

参照)
https://ihatecucumber.tistory.com/20
https://pacific-ocean.tistory.com/366