Good evening.

Today's round is mine, as the previous one. This round will be for participants of the second division. Participants of the first division can take part in the round out of competition.

RAD, Connector, it4.kp and MikeMirzayanov helped me to prepare this round. Delinur translated statements into English.

Contest will be in the good old tradition of Codeforces. No any innovations, pretty short and clear statements.

Points for problems are standard: 500-1000-1500-2000-2500.

Good luck everyone!

UPD. Round was ended, ratings was updated.

Winners:

1. tsundere

2. jte

3. abacadaea

4. ltaravilse

Editorial.
She isn't a coder (as far as I know), but she is great translator for texts such as statements on CF, so she usually translates contests into English.

It seems inconsistent. If it told be TL with the initial hack message, I would know what to fix straight away... :(

andthe test casebeforeend of contest?I had an idea, but I'm not quite sure if it works.

Let C be the optimal point, R be the maximum distance from C to any other point in the input and S be the sphere with center at C and radius R. We have 3 cases:

1 - S has 2 points from the input on its surface in which case C is the center of the line connecting these 2 points.

2 - S has 3 points from the input on its surface in which case C is the center of the circle connecting these 3 points.

3 - S has 4 or more points from the input on its surface and we can determine the center easily given 4 points.

Nice contest BTW, but problems A to D are a bit easier than usual I think.

I think the intended solution is Hill climbing

However, I have never seen it used in any kind of algorithm competition before. I would also be grateful if somebody could give me some more examples of problems with solutions like these.

min_z = min. z coordinate in given set of points

max_z = max. z_coordinate in given set of points

Though, it might be inefficient as answer can be real number instead of integer value.

Upd:actually, the final version works faster without it =) ).There are quite a few solutions with nested ternary searches accepted, too.

But I doubt this was the expected solution to implement, as it took like more than a century since the smallest enclosing circle problem was posed by Sylvester in 1857 for a linear algorithm to be found ...

edit: never mind. I guess I wanted apply a trick in practice like in here, but it doesn't seem to help.

Here is an approach:

- Isolate a center point. Call it C. Separate it from the others. We search for a minimum sphere that contains C.

- Invert with respect to C. A sphere that contains C is inverted to a plane that does not contain C. A point inside the sphere is inverted to a point on the other side of the plane.

In particular, the minimal enclosing sphere is inverted to a plane that is as far as possible from C, and such that all points are on the other side from C.

- Find the 3d convex hull, in O(N lg(N)), deduce the farthest plane in O(N).

- Invert again, to get the minimum sphere.

a_{i}grams left of thei-th stuffinga_{i}grams left of thei-th stuffing. It takes exactlyb_{i}grams of stuffingiandc_{i}grams of dough to cook a bun with thei-th stuffing.With

b_{i}ofi-th stuffing (andc_{i}of dough) baker can make a bun. So if he hasa_{i}grams, he can make at mosta_{i}/b_{i}(integer division) buns withi-th stuffing.a_{i}grams ofdoughleftafter usingthei-th stuffing. It takes exactlyb_{i}grams of stuffingiandc_{i}grams of dough to cook a bun with thei-th stuffing.I guess the following formulation would have been less prone to misinterpretation : « Lavrenty knows that he possesses

a_{i}grams of stuffingi. It takes exaclty ... ».But part of solving a problem is understanding its statement =)

nmiles in theydirection" is the form of instructions and i see that accepted solution just jump directly n miles and dont check all the blocks in between. Isnt this wrong? Tell me.Then, for example, the way from (x, y) to (x+dx, y) is clear if a[x][y] + ... + a[x+dx][y] = 0.

These sums can be precalculated just after reading the matrix and then obtained in O(1) time.

Isn't getting a problem accepted, algorithm dependent and language independent?

but my point is if an algorithm isn't good and takes much time, it should get TLE in both java and c++ , not just java.

otherwise I think it would be good to set Time Limit for java twice long as other languages. like some of other online judges.

BTW, you used Thread, how much faster is it than using a simple class?