Light OJ 1392 — Multi Round Matches

Revision en1, by amateurcoder, 2016-07-07 23:45:53

Problem link: Light OJ 1392.

Please give it a read. If I understood correctly, given R, T, N, it asks to find number of pairs (r, t) with 0 ≤ r < R, 0 ≤ t < T such that there exists integers a1, ..., ar whose sum is t and each of the numbers ai is between 1 and N (inclusive). Constraints are 1 ≤ R ≤ 108, 1 ≤ T ≤ 4 * 108, 2 ≤ N ≤ 20.

But then for a fixed r, all t between r and Nr should be reachable (others are not reachable because each of the r variables is at least 1 and at most N). So I ran a brute force, but they don't match the sample.

Code: here.

Interesting enough, the output of the brute force for each sample is exactly 26 more than actual answer. Where did I go wrong?

Tags lightoj, combinatorics, weird, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English amateurcoder 2016-07-07 23:48:17 11 Tiny change: 'rute force, but they' -> 'rute force (to check), but they'
en1 English amateurcoder 2016-07-07 23:45:53 861 Initial revision (published)