TrickyInequality
TCO13 Round 3A · 2013-02-19 · by blue.boy
Problem Statement
This problem statement contains superscripts and/or subscripts. These may not display properly outside the applet.
There are m positive integer variables: x1, x2, ..., xm. We do not know their exact values, we only know some inequalities they satisfy:- The sum of all our variables is at most s. Formally: x1 + x2 + ... + xm <= s.
- Each of the first n variables is less than or equal to t. Formally: for each i such that 1 <= i <= n we have xi <= t.
Constraints
- m will be between 1 and 10^9, inclusive.
- n will be between max(1,m-100) and m, inclusive.
- t will be between 1 and 10^5, inclusive.
- s will be between n*t and 10^18, inclusive.
3 1 1 2 Returns: 2
In this test case we have two variables, and we know that their sum is at most 3 and that the first variable is at most 1. Formally, we have x1 + x2 <= 3 and x1 <= 1. There are only two solutions in positive integers: (1,1) and (1,2).
5 2 2 3 Returns: 8
Here we are given the following inequalities: x1 + x2 + x3 <= 5 x1 <= 2 x2 <= 2 There are 8 solutions: (1,1,1), (1,1,2), (1,1,3), (1,2,1), (1,2,2), (2,1,1), (2,1,2) and (2,2,1).
30 1 1 10 Returns: 10015005
From the constraints we know that x1 must be 1. Therefore the sum of the nine positive integers x2 through x10 has to be at most 29. It's not hard to find that the answer is the binomial coefficient C(29,9) = 10015005.
2000 20 100 200 Returns: 35422605
999999999999999999 100000 999999900 1000000000 Returns: 90919453
Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TrickyInequality with a public method int countSolutions(long long s, int t, int n, int m) · 37 test cases · 2 s / 256 MB per case