問題一覧 > 通常問題

No.1598 4×4 Grid

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 67
作問者 : e869120 / テスター : kaage ygussany
お気に入りにしたユーザー ProblemId : 6420 / 自分の提出
問題文最終更新日: 2021-07-08 23:25:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
競プロ典型 90 問 期末試験 (順位表) の他の問題:

Problem Statement

There is a grid with $4$ rows and $4$ columns. As shown in the figure below, consider writing distinct integers between $1$ and $16$, inclusive, in the cells.

2


Now, define the score of the grid as "the sum of the differences between the written integers, over all pairs of cells that are adjacent in the $4$-neighborhood".
More formally, letting the integer written in the $i$-th row from the top and the $j$-th column from the left be $P_{i, j}$, the score $\mathrm{Score}$ is as follows. $$ \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}| $$

There are $16! = 20 \ 922 \ 789 \ 888 \ 000$ ways to write the integers. How many of them have a score of exactly $K$?

Input

$K$

Output

Output the answer.

Constraints

  • $1 \leq K \leq 216$
  • $K$ is an integer

Sample

Sample 1
Input
1
Output
0

There is no way of writing the integers that gives a score of $1$.

Sample 2
Input
60
Output
576

For example, writing the integers as follows gives a score of $60$.

3
Sample 3
Input
148
Output
395006790760

The answer may not fit in a $32$-bit integer.

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