問題一覧 > 通常問題

No.2057 Ising Model

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

問題文

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

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

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

入力

NN AA BB

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

    • 出力

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

    サンプル

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

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

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

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

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