Problem Statement |
| |
You have n steel balls each with a weight of 1001,
1002 or 1003 grams. Your task consists of indentifying the exact weight
of each one of them. You can make use of two different types
of balances, but you want to minimize the overall cost of all the weighings you make before you finally guess the weight of each ball. You have:
- A digital balance that gives you the total weight for any set of balls.
- A plate balance that tells you which of two disjoint sets of balls weighs more (or if the two sets weigh the same amount).
Each use of the plate balance costs 100, while the cost per use of the digital balance will be
given by digitalCost. You are to write two methods: init and next. First, init will be
called with n and digitalCost. This method should return
a int[] representing your first use of a balance or a guess of the
balls' weights.
Subsequently, the method next will be called with a
single int giving the result
of the previous guess. This method should return either a new use of a balance
or a guess of the balls' weights. After
you make a guess, no extra calls to any of your methods will be made.
The int[] returned from init or next must have exactly n elements,
and one of the following forms:
- If all elements are between 1001 and 1003,
inclusive, it will mean a guess of the weights.
- If all elements are either 0 or 1, it will
mean you are using the digital balance with all balls that have a 1
in their position being weighed. The next call to next will be given
the exact weight of that set of balls.
- If all elements are -1, 0 or +1 and there is at least one -1 and one +1,
it will mean that you are using the plate balance where -1 indicates a ball on the right plate,
while +1 indicates the left plate. The next call to
next will be given -1 if the set of
balls in the right plate weighs more, 0 if the sets have equal
weight and 1 if the set of balls in the left plate weighs more.
The score you will get for each test case is 0 if the final guess is
incorrect or in any call the returned int[] does not
follow the protocol above. Otherwise, if your final guess is correct, your score will be
10*n*sqrt(digitalCost) / totalCost, where totalCost is your cost of using the balances (or 1 if you don't use the balances at all). Your final score is simply the sum of your
scores on the individual test cases.
In 75% of the test cases n will be chosen uniformly between 10 and 100, inclusive, and it will be exactly 100 in the other 25%. digitalCost will be chosen uniformly between 80 and 250, inclusive.
The weight of each ball will be chosen independently and uniformly among the three possible weights. If after doing that there is at least one ball that
weighs 1000+k for each k between 1 and 3, inclusive, that test case
is accepted. If there is not, all weights are chosen again (n and digitalCost are not).
The time limit for each test case is 20 seconds (adding up all the
calls of both methods), and the memory limit is 64 megabytes. The maximum number of
balance uses is n*n, which means your next method will be called
at most n*n times with a result. If the last of those calls does not contain
a guess, you will get 0 points for the test case.
|
| |
Definition |
| | | Class: | WeighingBalls | | Method: | init | | Parameters: | int, int | | Returns: | int[] | | Method signature: | int[] init(int n, int digitalCost) | | | | Method: | next | | Parameters: | int | | Returns: | int[] | | Method signature: | int[] next(int lastResult) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | In the first 5 examples n was not chosen randomly to facilitate testing. In the rest of the examples it was. In all system test cases it will be chosen as explained in the problem statement. |
| - | There are 100 non-example test cases. |
| |
Examples |
| 0) | |
| | | Returns:
"n = 10<br/>
digitalCost = 150<br/>
weights = <br>
{1003,1002,1001,1001,1003,1002,1003,1001,1003,1002}<br/>
" | This could be one possible and correct sequence of calls and their returns:
init(10,150) returns {0,0,1,1,0,0,0,1,0,0}
Here you put balls 2, 3 and 7 in the digital balance. They all weigh 1001,
so the next call to next is given 1001*3=3003.
next(3003)
You can deduce that each of the 3 weighed
balls weights 1001, because is the only way to achieve 3003.
returns {1,1,1,1,1,1,1,1,1,1}
Now you put all balls in the digital balance, the total
weight given in the next call to next is 10021.
next(10021) returns {1,-1,0,0,0,0,0,0,0,0}
Ball 1 is in the right plate and weighs 1002, ball 0 is in the left plate
and weights 1003, so the left plate weighs more and next call to next
is given 1.
next(1) returns {1,1,0,0,1,0,1,0,1,0}
Here you weigh balls 0, 1, 4, 6 and 8 in the digital balance.
next(5014)
The only way to achieve 5014 with 5 balls is to have 4 of them
with weight 1003 and 1 with weight 1002. Since ball 1 is lighter
than ball 0, we can deduce that balls 0, 4, 6 and 8 weigh 1003 and
ball 1 weighs 1002.
returns {0,0,0,0,0,1,0,0,0,-1}
Now we ask for the relative weights of the 2 balls we can't deduce
yet (5 and 9). Since they weigh the same we are given 0 as result.
next(0)
By the total weight of 10021 given in an early balance use we can deduce
that the sum of weights of balls 5 and 9 is 2004 (since we know the
exact weight of all the other balls, we can just substract them
from the total weight). If they weigh the same, each one weighs 2004/2 = 1002.
Now we have the exact weight for all the balls, so we guess.
returns {1003,1002,1001,1001,1003,1002,1003,1001,1003,1002}
The score in this case is 10*10*sqrt(150)/(3*150+2*100) because we used the digital balance three times, each with a cost of 150 and twice the plate balance, each with a cost of 100. |
|
|
| 1) | |
| | | Returns:
"n = 10<br/>
digitalCost = 138<br/>
weights = <br>
{1001,1003,1002,1002,1001,1003,1002,1002,1001,1001}<br/>
" | This could be one possible and correct sequence of calls and their returns:
init(10,138) returns {1,0, 0,0,0,0,0,0,0,0}
next(1001) returns {0,1, 0,0,0,0,0,0,0,0}
next(1003) returns {0,0, 1,0,0,0,0,0,0,0}
next(1002) returns {0,0,-1,1,0,0,0,0,0,0}
next(0) returns {0,0,-1,0,1,0,0,0,0,0}
next(-1) returns {0,0,-1,0,0,1,0,0,0,0}
next(1) returns {0,0,-1,0,0,0,1,0,0,0}
next(0) returns {0,0,-1,0,0,0,0,1,0,0}
next(0) returns {0,0,-1,0,0,0,0,0,1,0}
next(-1) returns {0,0,-1,0,0,0,0,0,0,1}
next(-1) returns {1001,1003,1002,1002,1001,1003,1002,1002,1001,1001}
Here we find out the first 3 weights using the digital balance. As soon as we find a ball with 1002 weight, we can decide each individual weight using the plate balance that is cheaper.
In this case the score is 10*10*sqrt(138)/(3*138+7*100), with 3 uses of the digital balance and 7 uses of the plate balance.
|
|
|
| 2) | |
| | | Returns:
"n = 11<br/>
digitalCost = 250<br/>
weights = <br>
{1001,1002,1002,1003,1001,1003,1002,1002,1002,1002,1003}<br/>
" | |
|
| 3) | |
| | | Returns:
"n = 14<br/>
digitalCost = 108<br/>
weights = <br>
{1003,1001,1003,1001,1001,1003,1003,1002,1002,1001,1001,1001,1001,1002}<br/>
" | |
|
| 4) | |
| | | Returns:
"n = 20<br/>
digitalCost = 226<br/>
weights = <br>
{1001,1001,1001,1003,1003,1003,1002,1002,1002,1002,1003,1002,1003,1003,1003,<br>
1001,1001,1002,1001,1001}<br/>
" | |
|
| 5) | |
| | | Returns:
"n = 57<br/>
digitalCost = 187<br/>
weights = <br>
{1001,1002,1003,1003,1002,1002,1003,1001,1001,1003,1003,1003,1003,1002,1001,<br>
1003,1002,1002,1002,1003,1001,1002,1003,1003,1003,1003,1001,1002,1001,1001,<br>
1001,1001,1002,1001,1001,1002,1001,1003,1001,1003,1002,1002,1003,1002,1001,<br>
1002,1003,1002,1001,1002,1002,1002,1002,1001,1001,1001,1002}<br/>
" | |
|
| 6) | |
| | | Returns:
"n = 30<br/>
digitalCost = 197<br/>
weights = <br>
{1002,1003,1003,1002,1001,1002,1002,1003,1002,1001,1003,1003,1002,1001,1001,<br>
1002,1003,1003,1001,1002,1001,1003,1001,1002,1001,1001,1001,1001,1001,1003}<br/>
" | |
|
| 7) | |
| | | Returns:
"n = 93<br/>
digitalCost = 87<br/>
weights = <br>
{1003,1002,1003,1002,1003,1001,1003,1002,1002,1003,1003,1003,1002,1003,1003,<br>
1001,1003,1001,1003,1001,1002,1001,1002,1002,1001,1003,1003,1002,1003,1002,<br>
1001,1002,1003,1001,1001,1001,1001,1001,1001,1002,1003,1003,1001,1002,1001,<br>
1001,1002,1003,1001,1002,1002,1003,1002,1001,1002,1001,1002,1003,1002,1001,<br>
1003,1001,1002,1001,1002,1001,1002,1003,1002,1002,1003,1003,1003,1003,1003,<br>
1002,1002,1001,1001,1002,1002,1003,1001,1003,1001,1002,1003,1002,1001,1001,<br>
1001,1001,1002}<br/>
" | |
|
| 8) | |
| | | Returns:
"n = 14<br/>
digitalCost = 119<br/>
weights = <br>
{1001,1003,1002,1001,1003,1001,1002,1003,1002,1003,1001,1001,1003,1002}<br/>
" | |
|
| 9) | |
| | | Returns:
"n = 100<br/>
digitalCost = 201<br/>
weights = <br>
{1003,1002,1003,1002,1002,1002,1002,1002,1002,1003,1002,1003,1002,1003,1003,<br>
1001,1002,1003,1002,1003,1001,1002,1002,1002,1003,1002,1001,1003,1003,1001,<br>
1001,1002,1002,1002,1002,1002,1001,1001,1003,1003,1002,1002,1002,1001,1001,<br>
1002,1003,1003,1002,1002,1002,1002,1003,1003,1003,1001,1003,1001,1001,1003,<br>
1001,1001,1003,1003,1003,1002,1001,1002,1003,1001,1003,1003,1002,1003,1002,<br>
1003,1003,1002,1001,1001,1001,1003,1001,1002,1001,1003,1001,1002,1002,1002,<br>
1003,1003,1003,1003,1001,1001,1002,1002,1002,1003}<br/>
" | |
|
