NeverAskHerAge | Topcoder Archive

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.

Definition

Class:: NeverAskHerAge
Method:: possibleSolution
Parameters:: int, int[], int[], String[], String[], int[]
Returns:: int[]
Method signature:: int[] possibleSolution(int n, int[] id1, int[] id2, String[] op, String[] rl, int[] val)
(be sure your method is public)

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.

{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.

{7,1,3,4,4,3,7,2,3,6,4,4,6,5,2,8,2,2,7,6,2,2,8,6,5,6,5,4,4,8,6,1,3,5,5,4,3,7,4,8}

{2,7,6,6,1,2,4,7,4,4,8,3,8,2,4,1,7,7,6,2,5,7,6,5,8,2,8,1,8,1,3,2,7,1,2,2,1,8,3,3}

{"/","*","/","-","*","+","*","+","/","+","-","+","*","+","/","*","-","/","-","*","/","/","/","*","/","+","+","*","*","-","-","*","+","+","+","-","+","/","+","*"}

{"<","<","<=",">","<","<=","<",">","<","<=","<=",">",">",">=","<",">","<","<",">",">=","<=","<","<=",">=","<=",">=",">=",">=","<=",">=","<=",">","<=","<",">","<=",">=","<","<=","<="}

{47636,5754558,3307,-41496,7043286,144246,5048203,72315,85384,182630,50604,9802,3843942,152392,60035,149684,94234,31209,-73898,195742,8383,71993,98477,4859384,74619,146266,60163,377564,5357728,-80040,72545,1088942,87517,192354,18629,45785,44151,95334,140360,1063484}

Returns: {56, 77, 19, 59, 77, 87, 43, 51 }

{7,1,3,4,4,3,7,2,3,6,4,4,6,5,2,8,2,2,7,6,2,2,8,6,5,6,5,4,4,8,6,1,3,5,5,4,3,7,4,8}

{2,7,6,6,1,2,4,7,4,4,8,3,8,2,4,1,7,7,6,2,5,7,6,5,8,2,8,1,8,1,3,2,7,1,2,2,1,8,3,3}

{"/","*","/","-","*","+","*","+","/","+","-","+","*","+","/","*","-","/","-","*","/","/","/","*","/","+","+","*","*","-","-","*","+","+","+","-","+","/","+","*"}

{"=","<","<=",">","<","<=","<",">","<","<=","<=",">",">",">=","<",">","<","<",">",">=","<=","<","<=",">=","<=",">=",">=",">=","<=",">=","<=",">","<=","<",">","<=",">=","<","<=","<="}

{2000,5754558,3307,-41496,7043286,144246,5048203,72315,85384,182630,50604,9802,3843942,152392,60035,149684,94234,31209,-73898,195742,8383,71993,98477,4859384,74619,146266,60163,377564,5357728,-80040,72545,1088942,87517,192354,18629,45785,44151,95334,140360,1063484}

Returns: { }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.