Connection Status:
Competition Arena > StrangeElevator

StrangeElevator

SRM 495 · 2010-11-01 · by rng_58

SRM 495 · 2010-11-01 · by rng_58 · Dynamic Programming, Math
Class Name: StrangeElevator
Return Type: int
Method Name: theCount
Arg Types: (int, int)
Problem Statement

Problem Statement

When cat Taro went to an internship, he found a strange elevator in the office's skyscraper. The skyscraper contains 58 floors. The elevator is composed of 2 boxes and these 2 boxes move together. When the lower box stops at the x-th floor, the upper box always stops at the (x+1)-th floor. The lower box stops only on odd floors (1st, 3rd, 5th, ..., 57th). The upper box stops only on even floors (2nd, 4th, 6th, ..., 58th). He is very interested by this elevator, and he wants to compute the number of possible elevators composed of N boxes in a skyscraper of height H.

The elevators must satisfy the following conditions:
  • For each floor, exactly one box stops at that floor.
  • The distance between 2 boxes is an integer and never changes. More formally, for each pair of boxes (A,B), there must be some integer d such that box B always stops at the (x+d)-th floor when box A stops at the x-th floor. If the (x+d)-th floor doesn't exist, box A must not stop at the x-th floor.

Two elevators are different if the following is true. When the bottommost box is at the first floor, there exists an i such that a box is at the i-th floor in one elevator and no box is at the i-th floor in the other elevator. You are given two integers H and N. Return the number of possible elevators that have N boxes in a skyscraper of height H, modulo 1,000,000,007.

Constraints

  • H will be between 1 and 1,000,000,000, inclusive.
  • N will be between 1 and H, inclusive.
Examples
0)
58
2
Returns: 2

The following two elevators are possible: When the lower box stops at the 1st, 3rd, ..., 57th floor, the upper box stops at the 2nd, 4th, ..., 58th floor, respectively. When the lower box stops at the 1st, 2nd, ..., 29th floor, the upper box stops at the 30th, 31st, ..., 58th floor, respectively.

1)
1
1
Returns: 1

The only box always stops at the 1st floor.

2)
9
3
Returns: 2

The following two elevators are possible: When the lowest box stops at the 1st, the 4th and the 7th floor, the middle box stops at the 2nd, the 5th and the 8th floor, and the topmost box stops at the 3rd, the 6th and the 9th floor, respectively. When the lowest box stops at the 1st, the 2nd and the 3rd floor, the middle box stops at the 4th, the 5th and the 6th floor, and the topmost box stops at the 7th, the 8th and the 9th floor, respectively.

3)
120
12
Returns: 30
4)
58585858
495
Returns: 0

Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class StrangeElevator with a public method int theCount(int H, int N) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous