問題一覧 > 通常問題

No.44 DP Sugoroku

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 762
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 76 / 自分の提出
問題文最終更新日: 2026-06-25 09:12:30
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

Problem Statement

You are playing a sugoroku (board game) with N squares.
Each turn, you can move forward by "1" or "2".
You start at the start square, square "0".

How many ways are there to reach exactly square N?


Input

N

The number of squares of the sugoroku, an integer \( N (2 \le N \le 50) \), is given.

Output

Output the number of ways to reach exactly square N.
Note that the answer may not fit within \(2^{32} \).
It does fit in a 64-bit integer type.

Sample

Sample 1
Input
2
Output
2

There are 2 ways to reach 2: "1, 1" and "2".

Sample 2
Input
3
Output
3

There are 3 ways to reach 3: "1, 1, 1", "2, 1", and "1, 2".

Note that "2, 1" and "1, 2" are treated as distinct.

Sample 3
Input
5
Output
8

"1, 1, 1, 1, 1"
"2, 1, 1, 1"
"1, 2, 1, 1"
"1, 1, 2, 1"
"1, 1, 1, 2"
"1, 2, 2"
"2, 1, 2"
"2, 2, 1"
These are the 8 ways.

Sample 4
Input
50
Output
20365011074

The answer exceeds \(2^{32} \), so it does not fit in an int.

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