HopscotchCounting
SRM 824 · 2022-02-17 · by misof
Problem Statement
A hopscotch is a well-known playground game. When preparing the game, kids will take some chalk and draw a figure consisting of some squares onto the pavement. The game is then played by hopping into those squares according to some rules that are not important here.
Here is a sample plan for the hopscotch game:
+-+-+
| |
+-+-+-+-+
| | |
+-+-+-+-+
| |
+-+-+
| |
+-+-+-+-+
| | |
+-+-+-+-+
| |
+-+-+
| |
+-+-+
When drawing a plan for the game, the kids follow several simple rules:
- The plan must consist of one or more consecutive rows of squares.
- Each row of squares must contain either one square (in the middle) or two squares next to each other.
- There can never be two consecutive rows that both contain two squares.
Zuzka wants to draw a plan that will consist of exactly N squares. Count all possible ways in which she can do so. Return that count modulo 10^9 + 7.
Constraints
- N will be between 1 and 10^6, inclusive.
2 Returns: 2
Two possible plans: either one row with two squares, or two rows with one square each.
4 Returns: 4
All four plans are shown below. Remember that two consecutive rows with two squares are not allowed. +-+-+ | | +-+-+-+-+ +-+-+ +-+-+ +-+-+ | | | | | | | | | +-+-+-+-+ +-+-+-+-+ +-+-+ +-+-+ | | | | | | | | | +-+-+ +-+-+-+-+ +-+-+-+-+ +-+-+ | | | | | | | | | +-+-+ +-+-+ +-+-+-+-+ +-+-+
1 Returns: 1
3 Returns: 3
5 Returns: 6
70 Returns: 9736691
Don't forget to compute the answer modulo 1,000,000,007.
Submissions are judged against all 18 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HopscotchCounting with a public method int count(int N) · 18 test cases · 2 s / 256 MB per case