3 4
0 2000 1000 3000 0 3000
0 0 3000 0 3000 3000 0 3000
ans: 647.1067811865

5 6
0 2000 500 2500 1000 3000 1500 3000 0 3000
0 0 1500 0 3000 0 1500 0 3000 3000 0 3000
ans: 647.1067811865

3 4
0 0 4000 0 2000 4000
0 0 4000 0 4000 4000 0 4000
ans: 3517.7087639997

4 4
0 0 3000 0 3000 3000 0 3000
2000 2000 5000 2000 5000 5000 2000 5000
ans: 940

4 4
0 0 3000 0 3000 3000 0 3000
1000 1000 -2000 1000 -2000 -2000 1000 -2000
ans: 940

4 3
0 0 30000 0 30000 30000 0 30000
10000 40000 40000 10000 40000 40000
ans: 7011.0678118655

4 4
0 0 3000 0 3000 3000 0 3000
-1000 1000 5000 1000 5000 2000 -1000 2000
ans: 1940

4 4
0 0 3000 0 3000 3000 0 3000
-1000 2000 1000 -1000 2000 -1000 -1000 2000
ans: 647.1067811865

3 3
0 0 4000 2000 0 4000
3000 2000 7000 0 7000 4000
ans: 387.2135955000

Also, WA6 = integer overflow

I believe there might be some precision issues with the tests. Here is why:

My AC solution (ID = 11182582) has a parameter STEPS set to 1000. As I set it higher, the accuracy increases.

On this input:
54 46 -161
-82 -150 -33
100 127 -175

My AC program gets:
48.217529

But when I set STEPS to 10000, the improved AC program gets:
38.806852

In addition, I have another program (ID 11182578 - WA #22) outputting:
37.855475851615

I believe test #22 is wrong (as well as my AC solution) while my WA #22 solution is in fact correct.

To strenghten that conviction, when I set STEPS to 30000, the improved AC program gets:
38.191302

Thus, the two answers are within a relative error of less than 10^-2.

Please look into this issue.
Thank you!

input : ABCDLKOIKJTFIDCBA

ouput is a single letter such as A K and I
NOT “ABCD” or what have you .

I passed WA #10 by printing 90 decimals and using custom decimal computations accurate up to 45 digits.

What is the test 4?

This test was failing on my solution. Other similar (symetric) tests could fail other similar (symetric) solutions.

Input:
2 1
-999999999 0
-999999999 1

What's wrong with this test?

Before you look at the solution I have to clear up some confusion.

If we are talking about the lowest bound it takes for the program to complete, then it is O(N^2), because you have to evaluate each table cell no matter what and print the value. This is also considering that by N we denote the side of the table.

On the other hand, the function that takes in i and j and spits out the correct number in O(1) **is possible** without any lookup, which can be also be parallelized and be ported as fragment shader. You can see it below, it's the `eval` function and all calls are independent of their neighbors.

The core challenge is to figure out how to calculate which diagonal are you on -- I call it level -- and what is your local index on that diagonal line. For example, for N=3, we have:
4 2 1
7 5 3
9 8 6

where, "1" is on the first level, "2,3" are on the second level, "4,5,6" are on the third level and so on. Furthermore, 6 is the third number on that line.


```cpp
#include <stdio.h>

int abs( int x )
{
    return x >= 0 ? x : -x;
}

int sum( int n )
{
    return ( n + 1 ) * n / 2;
}

static int n;
static int totalLevels;
static int topRight[2];

int eval(int i, int j)
{
    const int level = abs( topRight[ 0 ] - i ) + abs( topRight[ 1 ] - j );
    if( level < n )
    {
        const int origin = n - 1 - level;
        const int index = i - origin;
        return 1 + sum( level ) + index;
    }
    else
    {
        const int index = i;
        return 1 + n * n - sum( totalLevels - level ) + index;
    }
}

int main()
{
    scanf("%d", &n);
    totalLevels = n * 2 - 1;

    topRight[0] = n - 1;
    topRight[1] = 0;

    for( int j = 0; j < n; ++j )
    {
        for( int i = 0; i < n; ++i )
            printf("%d ", eval( i,j ));

        printf("\n");
    }

    return 0;
}
```

try this test:
1 1 3 100 3000

ans: 1000

take sample output and
map it affinly to data triangle and you will have AC

Edited by author 24.03.2026 20:05

Please tell me this test and tell me if the three-time repetition of the position by the king is taken into account (in chess, in this situation there is a draw)

I use 'set' in python. Very simple. But I have WA3. Don't know why. Please help.

Hi!

I believe test #3 is invalid - there is no way to get from floor 1 to floor N.

Can you please check?

Thank you!

Tricky test case (even can't find its analogue). It contains such placement of draughts that you should precisely touch one or several other draughts by your move, and almost identical angles (+/- 1e-8 radians) will not give correct answer. When allow precisely touch got AC.

P.S.
Seems like one enemy draught you touch on the left side and other one - on the right side simultaneously.

Edited by author 23.04.2023 18:44

Is this a rounding issue in the output?

input:
804289384 2
36 94
795951522 804289383

output:
8556270

631 8
902 694
854 198
479 378
808 647
53 134
77 91
493 13
597 802
ans: 22

86 15
27 93
95 30
85 88
26 17
78 66
49 60
52 21
96 85
55 45
2 69
1 47
18 20
96 80
66 8
70 51
ans: 22

75 3
49 97
16 10
10 36
ans: 8

be more careful about formulas

If the middle nail was hammered, then the left and right become adjacent?
Answer: NO

Edited by author 10.03.2026 13:47

just overrated