PROBLEM LINK:
Author: Vasya Antoniuk
Tester: Kevin Atienza
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Simple
PREREQUISITES:
Logic
PROBLEM:
There are ten balls and five colors. There are two balls for each color. Each ball weighs 1kg, except for two balls of the same color, which each weighs 2kg. Your task is to determine which colored balls are heavier. You can use a weighing scale which measures the exact difference in the weights of the objects between its pans. Your score is determined by the number of times you used the scale. (The fewer times, the higher score.)
QUICK EXPLANATION:
On the first pan, place two balls of color 5 and one ball of color 4.
On the second pan, place two balls of color 1 and one ball of color 2.
The answer is then the result of the scale, plus three.
EXPLANATION:
Scoring
What’s noteworthy in this problem is the atypical scoring method. Instead of the usual subtasks where each subtask has different constraints and point allocation, here the points depend on the number of times you used the scale. Specifically, the scoring looks more like a “challenge” problem:
- There are five test cases. (Each case corresponds to each color being the heaviest.)
- In each test case where you get the correct answer, if you used the scale K times, you get 100/K points. (If K = 0, then you get 100 points.)
- The total sum of these points will be your score. (This means that the maximum score is 500.)
- The score you get for this problem that will be counted in the leaderboard will be (\text{your score}) / (\text{best score in the contest}) \times 100.
As we can see, the fewer times we use the scale, the higher points we get, so we strive to minimize the number of times we use the scale.
Simple Solutions
Getting a positive score for this problem is actually quite easy. We can just guess that the heavier balls are of color 1, since this is true in one of the cases! This gives us 100 points for that case and 0 for the rest.
Another advantage of this is that this is very easy to implement. In Python, this just requires two “print” statements:
print 2
print 1
But some might think that this solution is not very honorable because we’re not guessing correctly for all problems. Thankfully, it’s also easy to come up with an algorithm that gives us positive points for all test cases. We can just check the exact weight of each color type using the scale! You can write a long if-then-else chain for this one:
import sys
def get_weight(color):
print 1
print 1, color
print 0
sys.stdout.flush() # we need to flush stdout
return input() # get the answer of the judge
def answer(color):
print 2
print color
sys.exit() # exit the program
if get_weight(1) == 2:
answer(1)
elif get_weight(2) == 2:
answer(2)
elif get_weight(3) == 2:
answer(3)
elif get_weight(4) == 2:
answer(4)
elif get_weight(5) == 2:
answer(5)
Alternatively, you can just use a loop:
import sys
def get_weight(color):
print 1
print 1, color
print 0
sys.stdout.flush() # we need to flush stdout
return input() # get the answer of the judge
def answer(color):
print 2
print color
sys.exit() # exit the program
for color in [1,2,3,4,5]:
if get_weight(color) == 2:
answer(color)
Here are some implementation notes:
- We made some auxiliary functions to make our program less error-prone: Writing the
get_weightcode multiple times gives more possibility of a human error and thus incorrect solutions. - Notice that we called
sys.stdout.flush()before taking the input usinginput(), which forces a “flush”. Other programming languages have similar functions. We need to flush because the output of programs is usually being buffered before being printed out (printing to the standard output is quite costly, so programs try to minimize the number of prints), so without forcing a flush, the judge program will be waiting for an indefinite amount of time. - Notice that we called
sys.exit()inside ouranswerfunction, so callinganswerautomatically ends the whole program.
For comparison, in C++, we can implement it this way:
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int get_weight(int color) {
cout << 1 << endl;
cout << 1 << " " << color << endl;
cout << 0 << endl; // note that 'endl' automatically does a flush
int result;
cin >> result;
return result;
}
void answer(int color) {
cout << 2 << endl;
cout << color << endl;
exit(EXIT_SUCCESS);
}
int main() {
for (int color = 1; color <= 5; color++) {
if (get_weight(color) == 2) {
answer(color);
}
}
}
Now, let’s see how many points we get for this solution. If the heavier balls have color c, then we will use the scale exactly c times, because we will have to use the scale for each color before c. Thus, we get 100/c points. Overall, we get 100/1 + 100/2 + 100/3 + 100/4 + 100/5 \approx 228.33 points, which is much better than our earlier 100 points!
We can slightly improve this by noting that if the heavier balls have color 5, then we don’t have to do the fifth usage of the scale. After using the scale four times and knowing that none of the first four colors are heavy, we can infer that color 5 must be the heavier balls! See the following implementation:
int main() {
for (int color = 1; color <= 4; color++) {
if (get_weight(color) == 2) {
answer(color);
}
}
answer(5);
}
The number of points we get is 100/1 + 100/2 + 100/3 + 100/4 + 100/4 \approx 233.33, which is a little better!
Better solutions
Let’s now try to reduce the number of uses of the scale some more.
Strategy 1: First, let’s place a ball of color 1 and color 2 on the first pan, and a ball of color 3 and color 4 on the second pan. What would happen then? There are five possibilities:
- If color 1 was heavy, then the result would be (2 + 1) - (1 + 1) = 1.
- If color 2 was heavy, then the result would be (1 + 2) - (1 + 1) = 1.
- If color 3 was heavy, then the result would be (1 + 1) - (2 + 1) = -1.
- If color 4 was heavy, then the result would be (1 + 1) - (1 + 2) = -1.
- If color 5 was heavy, then the result would be (1 + 1) - (1 + 1) = 0.
This means that if the result was 0, then we immediately know that color 5 was heavy. If the result was 1, then either color 1 or color 2 is heavy, and if the result was -1, then either color 3 or color 4 is heavy. In both cases, we can use just one more comparison to figure out which one it is! To summarize our algorithm:
- Compare [1,2] and [3,4].
- If the result is 1, then compare 1 and 2, and answer with the heavier one.
- If the result is -1, then compare 3 and 4, and answer with the heavier one.
- If the result is 0, then answer with color 5.
Here’s a possible implementation in Python:
import sys
def print_pan(pan):
print len(pan), ' '.join(str(color) for color in pan)
def compare(pan1, pan2):
print 1
print_pan(pan1)
print_pan(pan2)
sys.stdout.flush()
return input()
def answer(color):
print 2
print color
sys.exit()
result = compare([1,2], [3,4])
if result == 1:
if compare([1], [2]) > 0:
answer(1)
else:
answer(2)
elif result == -1:
if compare([3], [4]) > 0:
answer(3)
else:
answer(4)
else:
answer(5)
Let’s now figure out our score. In four out of five cases, we use the scale two times, but in the remaining case (color 5), we use it only once. This gives us a score of 100/2 + 100/2 + 100/2 + 100/2 + 100/1 = 300 points!
Strategy 2: Let’s try attacking the problem simplistically by comparing two balls at a time. First, try comparing color 1 and color 2. If one of them is heavier, then we already know the answer. Otherwise, we know that the answer must be either 3, 4, or 5. In that case, let’s try comparing color 3 and color 4. Again, if one is heavier, then we already know the answer. Otherwise, we know that the must be 5. Done!
Here’s a sample implementation:
... # 'compare' and 'answer' definitions here
result = compare([1], [2])
if result == 1:
answer(1)
elif result == -1:
answer(2)
else:
result = compare([3], [4])
if result == 1:
answer(3)
elif result == -1:
answer(4)
else:
answer(5)
Now, let’s see how many points this solution gets. If either color 1 or color 2 is heavy, then we only use the scale once. Otherwise, we use it twice. Therefore, the score is 100/1 + 100/1 + 100/2 + 100/2 + 100/2 = 350 points.
The best solution
In fact, a score of 500 points is achievable! To do so, however, we must figure out the correct answer within just one usage of the scale. To do that, we must find a usage of the scale with 5 distinct results, depending on the color of the heavy balls.
To begin, let’s take a look at our 300-point solution above, where we initially compare [1,2] and [3,4]. If color 5 was heavy, then we don’t need further usages of the scale. However, if color 5 wasn’t heavy, then we were left with two cases, each with two possibilities, and we were forced to use the scale another time to figure out which of these possibilities were the real one. For example, if the result of comparing [1,2] and [3,4] was -1, then we know that either ball 3 or ball 4 was heavy, but we don’t have any more information to figure out which one of them was heavier, based on the initial comparison alone! It would be great if we can distinguish these two cases somehow.
Thankfully, there’s a way to modify the initial comparison to do just that! Instead of comparing [1,2] and [3,4], we compare [1,2,2] and [3,4,4]; in other words, we put one ball of color 1 and two balls of color 2 in the first pan, and one ball of color 3 and two balls of color 4 in the second pan. This way, the five possibilities are:
- If color 1 was heavy, then the result would be (2 + 1 + 1) - (1 + 1 + 1) = 1.
- If color 2 was heavy, then the result would be (1 + 2 + 2) - (1 + 1 + 1) = 2.
- If color 3 was heavy, then the result would be (1 + 1 + 1) - (2 + 1 + 1) = -1.
- If color 4 was heavy, then the result would be (1 + 1 + 1) - (1 + 2 + 2) = -2.
- If color 5 was heavy, then the result would be (1 + 1 + 1) - (1 + 1 + 1) = 0.
Notice that each case results in a distinct result! This means that we can know the answer with just one usage of the scale.
Here’s an implementation:
result = compare([1,2,2], [3,4,4])
if result == 1:
answer(1)
if result == 2:
answer(2)
if result == -1:
answer(3)
if result == -2:
answer(4)
if result == 0:
answer(5)
Since we only used the scale once, our score is the maximum possible: 500 points!
We can slightly modify this so that the solution looks cleaner:
result = compare([4,5,5], [1,1,2])
answer(result + 3)
Or, more compactly,
answer(compare([4,5,5], [1,1,2]) + 3)
Time Complexity:
O(1)