ShorterSuperSum
SRM 467 · 2009-11-12 · by vexorian
SRM 467 · 2009-11-12 · by vexorian · Dynamic Programming, Math
Problem Statement
Problem Statement
SuperSum is a function defined as:
- SuperSum(0 , n) = n, for all positive n.
- SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n.
Given k and n, return the value for SuperSum(k , n).
Constraints
- k will be between 1 and 14, inclusive.
- n will be between 1 and 14, inclusive.
Examples
0)
1 3 Returns: 6
When k = 1, SuperSum is equal to the sum of the first n = 3 numbers: 1 + 2 + 3 = 6.
1)
2 3 Returns: 10
SuperSum(2 , 3) = SuperSum(1 , 1) + SuperSum(1 , 2) + SuperSum(1 , 3) = 1 + 3 + 6 = 10.
2)
4 10 Returns: 2002
3)
10 10 Returns: 167960
4)
14 14 Returns: 37442160
Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ShorterSuperSum with a public method int calculate(int k, int n) · 109 test cases · 2 s / 256 MB per case