In this problem one must divide all natural numbers from 1 to n2 to groups size of n with the same sums.
Lets divide all this numbers to pairs . We can to do it since n is even and therefore n2 is even too. Then we can just make n groups consists of of these pairs.
In this problem you must to do only what's written — you must to define does this set of points sutisfies to decribed conditions.
There are many ways to define it. For instance:
- Check if there are exactly 3 discinct x's and y's. One can put all x's to set and then get it size to find amount of distinct x's (as well as y's). Then print ``ugly'' if this amount isn't equals to 3.
- Finally we have x1, x2 и x3 as well as y1, y2 и y3. Now lets check if for every pair (xi, yj) (except (x2, y2)) such point exist in given set of points.
But I think that to read editoral of this problem is not good idea. It is better to just look at the implementation.
Actually we are looking for longest sequence of natural number a1, a2, ..., ak, so that every number in it sequence is the power of three, sum of all numbers is more then n and if we remove any number sum will be less then n. To be precise we are looking for length of this sequence.
Consider minimal number ai = A in the sequence. All this numbers are divides to A since them all are powers of 3. And then, sum S of all this number is divides to A too. Suppose that n is divide to A too. Then, since S > n, then S - A ≥ n. And then if we remove A from sequence, sum of other number not less then n — contradist with second condition.
Well, we now that n is not divide to none element in sequence. Now lets find minimal k so that , and answer is .
At first lets make two remarks:
- On every (vertical of horizontal) line we can put only one chip.
- If there is at least one forbidden cell on the line then we can't put chip on this line.
Follow last remark we will avoid hits chip on forbidden cells. Lets avoid ``collisions'' of chips.
Lets consider these four line: vertical lines number i and n + 1 - i and horizontal lines with the same numbers. Chips on these lines can collides together, but con't collides to another chip. Therefore we can solve the problem for these four line independently. And finally lets observe that we can put the chip on each of these lines without cillisions as well as on the picture.
So, we can iterate all possible fours and put chip on every possible line. And don't fogot about case of two middle line in case of n is odd.
In this problem we can find the right amount of lucky tickets.
Lets consider amount of different numbers we can get from one four-digit ticket number. It is easy to iterate all this tickets, since it amount only 104. It happened that we can get almost 60 numbers from ticket on the average.
Suppose we can get number x from ticket n. It is clearly that either x - k ≥ 0 or k - x ≥ 0. If k - x ≥ 0 we can write eight-digit ticket number who will have k - x in the first four digits and n in the last four digits. It is clearly that such ticket is k-lucky. This method allows us to get almost 600 000 lucky tickets and it is enough.
In this problem we must to find maximal value of minimum of values on four intersections of two rows and two columns of table.
In another words, we are looking for maximum value of min(ai1, j1, ai1, j2, ai2, j1, ai2, j2) for all i1, i2, j1, j2 such that 1 ≤ i1, i2 ≤ n, 1 ≤ j1, j2 ≤ m, i1 ≠ i2, j1 ≠ j2. Lets us binary search of the answer. For us it we must can define is there two rows and two colums with ones on all four its intersections; in other words, integers i1, i2, j1, j2 so that ai1, j1 = ai1, j2 = ai2, j1 = ai2, j2 = 1.
Lets consider all pair of natural numbers (i1, i2) so that there exist nutural number j so that ai1, j = ai2, j = 1. Existence of two equals such pairs is equals to existence of above four numbers. But it is can be only such pairs. Therefore we can make the array where we will mark pair who were meets. Lets iterate all pairs in any order until we meet repeated pair or pairs are ends. So we have solution of time .
In this problem it is need to draw three circle equals together with maximum possible radius with centers in given points. In another words it is need to find triangle wich minimum side is maximal.
Unfortunately solution with bit optimize is not expected for us.
Lets call to memory two simple geometric facts. Firstly, sum of alnges of trianle is equals to . Secondly, minimal angle is opposit to minimal side of triangle.
Since, at leats one side of angles of triangle not less then and this anlge is not least one. And side opposite to it is not least side. Therefore, if in then min(|AB|, |BC|, |CA|) = min(|AB|, |BC|).
And then lets do the follows. Lets iterate apex B and for each B lets find triangle with maximal minimum of sides when B is the apex of triangle and . For it lets sort all other points by the angle relative to B, and for each point A lets find point C most distant to B among such points that . We have to use segment tree for maximum and two pointers or binary searsh to now left and right bound of possible points C during iterating A.
Finally, we have solution of time .