FibonacciStringSum
SRM 701 · 2016-10-02 · by Arterm
SRM 701 · 2016-10-02 · by Arterm · Advanced Math, Dynamic Programming
Problem Statement
Problem Statement
A string is called a Fibonacci string if it satisfies the following constraints:
int n.
In this problem we will consider Fibonacci strings of length n.
You are also given two nonnegative int s a and b.
These are used to define the weight of a string.
The weight w(s) of a Fibonacci string s is calculated as follows:
- Each character of the string is either a '0' or a '1'.
- There are no two consecutive '1's in the string.
- Let x be the number of '0's in s.
- Let y be the number of '1's in s.
- The weight of s is (x^a) * (y^b).
Constraints
- n will be between 1 and 1,000,000,000, inclusive.
- a will be between 0 and 25, inclusive.
- b will be between 0 and 25, inclusive.
Examples
0)
1000000000 25 25 Returns: 572727199
1)
536870911 25 25 Returns: 449528631
2)
158260522 6 23 Returns: 640706797
3)
745344240 18 9 Returns: 894154618
4)
118642159 2 10 Returns: 36301786
27)
3 0 0 Returns: 5
We have five Fibonacci strings of length 3: "000", "001", "010", "100", "101". As a=b=0, the weight of each Fibonacci string is 1. Hence, the sum of weights of our five strings is 5.
28)
3 0 1 Returns: 5
With a=0 and b=1, the weight of a string is the number of ones it contains. The correct return value is w("000") + w("001") + w("010") + w("100") + w("101") = 0 + 1 + 1 + 1 + 2 = 5.
29)
10 10 10 Returns: 518500021
Watch out for integer overflow.
Submissions are judged against all 35 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FibonacciStringSum with a public method int get(int n, int a, int b) · 35 test cases · 2 s / 256 MB per case