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

The vectors may have negative coordinates.

|x|, |y| > 2^32

Я написал рекурсию которая каждый раз делила отрезок на два и брала максимальный среди ответа всех таких отрезков которых поделила.(типо Merge Sort). У меня был memory limit на 3 тесте. Это значить рекурсия берет память?

n,k = map(int,input().split())
if k==1 or n==1:
    print(2*n)
else:
    if 2*n%k==0:
        print(2*n//k)
    else:
        print(2*n//k+1)

N,M  = map(int,input().split())
k = []
for _ in range(M):
    m = int(input())
    k.append(m)
for i in range(1,N+1):
    print(f"{k.count(i)*100/M:.2f}%")
Time limit please help

What does it mean: "reach smth"?
It's a strict condition, but how should i understand it?)
In my opinion, this sample has two right answers:
4
0 0
0 1
0 5
0 8
2 * (1.5 * 1.5) * M_PI or (1 + 3 * 3) * M_PI.

input:
2 8
12 28 40 46
48 54 60 80
2 7
9 24
34 49
54 62
66 77
78 79
80 83
84 84

output:
6