InfiniteSequence

SRM 413 · 2008-08-05 · by yuhch123

SRM 413 · 2008-08-05 · by yuhch123 · Dynamic Programming

Show categories

Class Name: InfiniteSequence

Return Type: long

Method Name: calc

Arg Types: (long long, int, int)

Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Let's consider an infinite sequence A defined as follows:

A₀ = 1;
A_i = A_[i/p] + A_[i/q] for all i >= 1, where [x] denotes the floor function of x. (see Notes)

You will be given n, p and q. Return the n-th element of A (index is 0-based).

Notes

[x] denotes the floor function of x which returns the highest integer less than or equal to x. For example, [3.4] = 3, [0.6] = 0.

Constraints

n will be between 0 and 10^12, inclusive.
p and q will both be between 2 and 10^9, inclusive.

Examples

0
2
3
Returns: 1

A[0] = 1.

7
2
3
Returns: 7

A[0] = 1; A[1] = A[0] + A[0] = 2; A[2] = A[1] + A[0] = 2 + 1 = 3; A[3] = A[2] + A[1] = 3 + 2 = 5; A[7] = A[3] + A[2] = 5 + 3 = 8.

10000000
3
3
Returns: 32768

256
2
4
Returns: 89

1
1000000
1000000
Returns: 2

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

Coding Area

Language: C++17 · define a public class InfiniteSequence with a public method long long calc(long long n, int p, int q) · 80 test cases · 2 s / 256 MB per case