SRM 467, D2, 250-Pointer (ShorterSuperSum)

James S. Plank

Tue Nov 9 17:00:53 EST 2021

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
MD5 hash of tests.sh: cbaae2ca4a06f799f2b6f9dc6377cb35
MD5 hash of answers.txt: 2e56af24e1962e97ad97e8d09caaf915
Problem Given in Topcoder: 2010
Competitors who opened the problem: 679
Competitors who submitted a solution: 609
Number of correct solutions: 579
Accuracy (percentage correct vs those who opened): 85.3
Average Correct Time: 11 minutes, 52 seconds.

In case the Topcoder servers are down

Here is a summary of the problem:

You are given two positive integers k ≤ 11 and n ≤ 20.
We define a mathematical function, SS(k,n):
- SS(0,n) = n.
- Otherwise SS(k,n) = the sum for i = 1 to n of SS(k-1,n).
- Return SS(k,n)

Examples

These are all included in main.cpp. If you give the input "-" to main.cpp, then it will read its values from standard input.

  #   k   n   Answer
  0   1   3       6:  1 + 2 + 3 = 6
  1   2   3      10:  SS(1,1) + SS(1,2) + SS(1,3) = 1 + 3 + 6 = 10
  2   4  10    2002
  3  10  10  167960

Testing Yourself without Topcoder's Servers

Standard workflow. See the "Cryptography" problem.

Hints

Just use a brain-dead recursion. It will finish within the time limits (on my machine, all of tests.sh takes under 2 seconds).

For a Bigger Challenge

You can increase k and n to 1,000 and use dynamic programming.