Test 9 is about the possibility of the shoot. For example I just changed < on <=:
    if (4 * (pow(x1 - xc, 2) + pow(y1 - yc, 2) - pow(r, 2)) <= pow(x2 - x1, 2) + pow(y2 - y1, 2)) {

https://math.stackexchange.com/questions/2138051/how-many-squares-is-passing-the-diagonal

Edited by author 16.09.2020 22:50

I figured out that n == 8 in test 2.
It may be useful for somebody.

pls help, what is in test №14

            Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;

            var tokens = Console.ReadLine().Trim().
                Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);

            var a = int.Parse(tokens[0]);
            var b = int.Parse(tokens[1]);
            var c = int.Parse(tokens[2]);
            var d = int.Parse(tokens[3]);

            var min = a + (c - a) / (b + d) * b;
            var max = c - (c - a) / (b + d) * d;

            min = Math.Min(min + b, Math.Max(min, max));
            max = Math.Max(max - d, min);

            Console.WriteLine(max);

Some tests?

if u wanna break your programm type sys.exit() (don't forget to type import sys in the beginning of the programm)
_____________________
если вы хотите полностью прервать вашу программу, то импортируйте библиотеку sys и пропишите sys.exit()

Could anyone give a piece of advice if i have a time limit exceeded with binary search?

WHAT IS TEST 8

It's never endless fixing

Ok I understand now...It means in blue-red land you can either grab mana from blue or red.

Edited by author 11.09.2020 20:18

Edited by author 12.09.2020 17:07

Edited by author 12.09.2020 17:08

Hm. Seems there are no tests with small number of linear independent rows.
I have two solutions with different answers to such tests, but both got OK.

Admins, please, add some.

30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
...
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
x20

30 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0
x10

1. Stations may not all be connected. You may have to walk on foot between stations.
2. A and B may be one of the stations or may even be the same point. Maybe the best route is from A to B is on foot without using any stations. Consider all cases.
3. Coordinates are floating points, not integer.
4. Simple dijsktra will work.
5. Use a map to store the node number of the points. If A or B are not one of the stations then give them n and n+1 or n+1 and n+2 (depending on indexing).

It is said "Tags: dynamic programming"

But also there is math approach. In this case solution is simple math formula kind of \sum\sum C(x,y)*C(t,m). Complexity is O(n^2).

Good luck.

Test 1:
3
1 2 3

Answer 1:
1
3 1 2 3

Test 2:
3
1 3 3

Answer 2:
2
1 1
3 1 2 3

P.S. Statement is not understandable :(

Edited by author 28.12.2012 14:24

This question can be solved using the same logic in 1167(Bicolored horses), but it will give tle.

There can be multiple edges. For instance:
1 2
2 1

Using a set will give WA. Try multi-set or some other data structure in c++.

Edited by author 07.09.2020 15:22

Edited by author 07.09.2020 15:22

WA8
Please, explain, what is the reason? Is this just a problem of input/output or this is just such test case?

Let c[i][0] = a[i], i = 1..n
    c[i][1] = c[i+1][0] - c[i][0], i = 1..n-1
    c[i][2] = c[i+1][1] - c[i][1], i = 1..n-2
     ....
    c[i][d] = c[i+1][d-1] - c[i][d-1], i = 1..n-d.

   if hardness of a[i]  is d.  so all c[i][d] = const.

    1. Find minimum d, that  all c[i][d] - is const.  (example:  binary search).
    2. build b[n+i] from c[i][d].


There can calculate c[i][j] through a[i] sequences:

    c[i][1] = a[i+1] - a[i]
    c[i][2] = c[i+1][1] - c[i][1] = (a[i+2] - a[i+1]) - (a[i+1] - a[i]) = a[i+2] - a[i+1] - a[i+1] + a[i] = a[i+2] - 2*a[i+1] + a[i].

   c[i][3] = c[i+1][2] - c[i][2] = (a[i+3] - 2*a[i+2] + a[i+1]) - (a[i+2] - 2*a[i+1] + a[i]) = a[i+3] - 3* a[i+2] + 3*a[i+1] - a[i].

   ..
   c[i][d] = SUM( c[i + d - j ] * Binom(d, j) * (-1)^j, j = 0..d)

    where Binom(d, j) - Binominal coefficients , or  coefficients of (x+y)^d .

  if d - is known,

   c[1][d] = c[2][d] = ... = c[n-d][d] = W - constanta.

  b[n+1] = x

   c[n-d+1] = b[n+1] + SUM(a[n + 1- j] * binom(d,j)*(-1)^j, j = 1..d)  = W

   b[n+1] = W - SUM(a[n+1-j] * binom(d,j)*(-1)^j, j = 1..d)

   and so on.


  Only one problem,  how fastest calculate SUM(a[i + d - j] * binom(d,j)(-1)^j, j = 1..d)   ?