JOIN
 Match Editorials
TCHS SRM 15
Monday, September 25, 2006

## Match summary

In this problem set coders faced an easy first problem, an easy second -- which had the same number of correct submissions as the first problem-- and a not very difficult third, though it did require some accuracy in coding.

After the coding phase, Weiqi was the first, but challenge phase made him fourth, and after system tests he finished in third place. fatit finished second, getting 100 points during the challenge phase. YuJieLu took first place with 175 challenge points, racking up his second first-place finish in only his second High School SRM.

# The Problems

NumbersLine
Used as: Division One - Level One:
 Value 250 Submission Rate 133 / 143 (93.01%) Success Rate 112 / 133 (84.21%) High Score Zuza for 249.40 points (1 mins 23 secs) Average Score 234.38 (for 112 correct submissions)

In this problem, the main thing was to parse integers from a string, but to do it carefully. The sample code can be as follows:

```   public int getLeast(String line, int givenNumber) {
line += " ";
int curr = 0, mn = 10000;
for(int i = 0; i < line.length(); i++) {
if (line.charAt(i) == ' ') { if ((curr != 0) && (curr > givenNumber) && (mn > curr)) mn = curr; curr = 0; } else
curr = 10*curr + line.charAt(i) - '0';
}
if (mn == 10000) return -1; else return mn;
}
```

ShootingGallery
Used as: Division One - Level Two:
 Value 500 Submission Rate 117 / 143 (81.82%) Success Rate 112 / 117 (95.73%) High Score Zuza for 496.00 points (2 mins 33 secs) Average Score 416.96 (for 112 correct submissions)

The second problem didn't take long time for competitors to solve it and, since it had only five wrong solutions, there weren't many possibilities for challenge.

In this problem, the simplest approach was to count the probability that your friend will not hit the target in n or less shots. For each shot he misses with probability (1-accuracy/100.0), and shots are independent, so you may count it as (1-accuracy/100.0)^n. And when this probability becomes less than or equal to 0.5, you should break and return current n.

From examples you can see that the answer will never be greater than 68, so you didn't need to worry about time limit or double precision.

Java code follows:

```   public int profitableBet(int accuracy) {
double p = 1-(accuracy/100.0),w = 1;
for(int n=0;;n++) {
w *= p;
if (w <= 0.5) return n;
}
}
```

SetOfBoxes
Used as: Division One - Level Three:
 Value 1000 Submission Rate 47 / 143 (32.87%) Success Rate 29 / 47 (61.70%) High Score Weiqi for 844.93 points (12 mins 39 secs) Average Score 530.16 (for 29 correct submissions)

In this problem, you were asked to count the probability that a point will be contained in some number K of boxes. You can say it as follows: it is the probability that a point will be contained in at least K boxes minus the probability that a point will be contained in at least K+1 boxes. For each box, you may count the number of boxes it is contained in. Then the probability that a point will be contained in at least K boxes will be equal to the sum of the areas of the boxes, contained in K-1 other boxes (which represents the favourable outcomes), divided by 10,000 - the area of the large square box (all possible outcomes).

In other words, you could solve this problem using these steps:

• Parse the coordinates of triangles
• For each pair of triangles, determine if the first one lies in the second one
• For each triangle, determine the number of triangles in which it is contained
• For each triangle that is contained in inBox triangles, add its area to the answer
• For each triangle that is contained in inBox+1 triangles, substract its area from the answer