NeverAskHerAge

SRM 630 · 2014-07-26 · by cgy4ever

SRM 630 · 2014-07-26 · by cgy4ever · Graph Theory, Math

Show categories

Class Name: NeverAskHerAge

Return Type: int[]

Method Name: possibleSolution

Arg Types: (int, vector<int>, vector<int>, vector<string>, vector<string>, vector<int>)

Problem Statement

Fox Jiro is attending a dancing party. There are n girls at the party. Being a geek, Jiro immediately numbered the girls 1 through n. We will use x[i] to denote the age of girl i. We will assume that each x[i] is an integer between 1 and 100, inclusive.

In Jiro's culture, asking a girl's age is taboo. Luckily, it is acceptable to ask about arithmetic expressions that contain the girls' ages. Jiro has been asking such questions for a while. For example, he may now know that x[1] + x[2] is exactly 10 and that x[3] / x[8] is at least 2.500.

Formally, each information Jiro has about the ages has the following form: "x[girl1] operation x[girl2] relation value".

You are given Jiro's information encoded into five sequences: int[]s id1 and id2, String[]s op and rl, and a int[] val. For each valid i, the i-th elements of these sequences encode one information as follows:

id1[i] and id2[i] are the numbers of two different girls. (These are girl1 and girl2 in the above expression.)
op[i] is one of "+", "-", "*", and "/". (This is the operation in the above expression.)
rl[i] is one of "&lt", "&lt=", "&gt", "&gt=", and "=". (This is the relation in the above expression.)
val[i] is an integer between -10,000,000 and 10,000,000, inclusive. (The value in the above expression is computed as val[i]/1000.)

Find one possible solution for the ages of all n girls, and return them as a int[] with n elements (element i being the age of girl i+1, for all i). If there are multiple valid solutions, you may return any of them. If there are no valid solutions, return an empty int[] instead.

Constraints

n will be between 2 and 100, inclusive.
id1 will contain between 1 and 1,000 elements, inclusive.
id1, id2, op, rl and val will each contain the same number of elements.
Each element in id1 will be between 1 and n, inclusive.
Each element in id2 will be between 1 and n, inclusive.
For each i, id1[i] and id2[i] will be different.
Each element in op will be one of "+", "-", "*" and "/".
Each element in rl will be one of "<", "<=", ">", ">=" and "=".
Each element in val will be between -10,000,000 and 10,000,000, inclusive.

Examples

2
{1,1}
{2,2}
{"+","*"}
{"=","="}
{10000,21000}
Returns: {3, 7 }

We have two constraints: "x[1]+x[2]=10.0" and "x[1]*x[2]=21.0". We can solve this quadratic system to get x[1] = 3 and x[2] = 7 or x[1] = 7 and x[2] = 3.

7
{1,2,3,4,5,6}
{2,3,4,5,6,7}
{"/","/","/","/","/","/"}
{"=","=","=","=","=","="}
{2000,2000,2000,2000,2000,2000}
Returns: {64, 32, 16, 8, 4, 2, 1 }

This time we have: x[1]/x[2] = x[2]/x[3] = x[3]/x[4] = x[4]/x[5] = x[5]/x[6] = x[6]/x[7]=2. Since x[i] is between 1 and 100, we have only 1 solution.

2
{1,1}
{2,2}
{"/","/"}
{">","<"}
{2621,2622}
Returns: {97, 37 }

From the given constraints we know that x[1]/x[2] must be strictly between 2.621 and 2.622. There is only one solution: 97/37 = 2.621621...

2
{1,1}
{2,2}
{"*","+"}
{">","<="}
{6000,5000}
Returns: { }

We have x[1]*x[2]> 6 and x[1]+x[2] <= 5. It has solutions like x[1]=x[2]=2.5, but there is no integer solution.

8
{1,3,5,7}
{2,4,6,8}
{"+","-","*","/"}
{">=","<=","=","<="}
{200000,-99000,3589000,10}
Returns: {100, 100, 1, 100, 97, 37, 1, 100 }

We have x[1]+x[2]>=200.0, x[3]-x[4]<=-99.0, x[5]*x[6]=3589.0, x[7]/x[8]<=0.01.

Submissions are judged against all 154 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NeverAskHerAge with a public method vector<int> possibleSolution(int n, vector<int> id1, vector<int> id2, vector<string> op, vector<string> rl, vector<int> val) · 154 test cases · 2 s / 256 MB per case