BTCODE_C - Fun With Inequalities
You are given 'n' inequalities. Each inequality is of one of the following 4 types:
Type 1: x > v
Type 2: x < v
Type 3: x = v
Type 4: x != v
where 'x' is a variable which can only take non-negative integral values.
Your task is to find the maximum number of inequalities which are satisfied for some value of 'x'. You are also required to find the minimum value of 'x' for which the maximum number of inequalities are satisfied.
The first line of input contains a single integer 'n', denoting the total number of inequalities.
Each of the next 'n' lines contain 2 space separated integers ti and vi. ti denotes the type of inequality and vi denotes the value on the right hand side of the inequality.
Output two space separated integers, the first integer denoting the maximum number of inequalities which are satisfied for some value of 'x', and the second integer denoting the minimum value of 'x' for which the maximum number of inequalities are satisfied.
Input: 4 1 10 2 9 3 7 4 4 Output: 3 7 Constraints: 1 <= n <= 100000 1 <= ti <= 4 1 <= vi <= 10^18
The given inequalities are: 1) x > 10, 2) x < 9, 3) x = 7, 4) x != 4. For x=7, the inequalities 2), 3) and 4) are satisfied.
Can a specific inequality be repeated more than once?
Last edit: 2011-06-28 19:00:32
.....Last edit: 2011-03-20 05:19:19