問題一覧 > 通常問題

No.2057 Ising Model

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : nok0nok0 👑 ygussanyygussany
4 ProblemId : 8341 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-25 22:24:36

問題文

正整数 $N,A,B$ が与えられます。 また長さ $N$ の数列 $S$ のうち $1 \le i \le N$ を満たす全ての整数 $i$ に対して $S_i \in \lbrace -1,1 \rbrace$ が成り立つものを良い数列と呼ぶこととします。良い数列 $S$ に対して $f(S)$ を次のように定めます。

　　$f(S)= A \displaystyle \sum_{i=1}^{N-1} S_iS_{i+1}-B \displaystyle \sum_{i=1}^N S_i$

$f(S)$ の最小値を求めてください。

入力

$N$ $A$ $B$

  • $2 \le N \le 10^{10}$
  • $1 \le A \le 1000$
  • $1 \le B \le 1000$
  • 与えられる入力は全て整数

    • 出力

    $f(S)$ の最小値を出力してください。

    サンプル

    サンプル1
    入力
    3 2 1
    出力
    -5

    $S=(1,-1,1)$とするのが最適です。

    サンプル2
    入力
    10 3 6
    出力
    -33

    サンプル3
    入力
    666 222 999
    出力
    -517704

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。