問題一覧 > 通常問題

No.1598 4×4 Grid

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : e869120e869120 / テスター : kaagekaage 👑 ygussanyygussany
10 ProblemId : 6420 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-08 23:25:57

問題文

$4$ 行 $4$ 列のマス目があります。下図のように、各マスに $1$ 以上 $16$ 以下の相異なる整数を書き込むことを考えます。

2


そこで、マス目のスコアを「すべての $4$ 近傍に隣り合うマスの組について、書かれた整数の差を合計した値」と定義します。
より厳密に書くと、上から $i$ 行目・左から $j$ 列目に書かれた整数を $P_{i, j}$ とするとき、スコア $\mathrm{Score}$ は次のようになります。 $$ \mathrm{Score} = \sum_{i=1}^{3} \sum_{j=1}^{4} |P_{i, j} - P_{i+1, j}| + \sum_{i=1}^{4} \sum_{j=1}^{3} |P_{i, j} - P_{i, j+1}| $$

整数の書き込み方は $16! = 20 \ 922 \ 789 \ 888 \ 000$ 通りありますが、そのうちスコアがちょうど $K$ であるものはいくつありますか?

入力

$K$

出力

答えを出力してください。

制約

  • $1 \leq K \leq 216$
  • $K$ は整数

サンプル

サンプル1
入力
1
出力
0

スコアが $1$ となるような書き込み方は存在しません。

サンプル2
入力
60
出力
576

例えば次のような書き込み方をすると、スコアが $60$ となります。

3
サンプル3
入力
148
出力
395006790760

答えは $32$ ビット整数に収まらない場合があります。

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