AC with max travel dist = 6

My Accepted solution 8202681 for problem 1050 gives incorrect answer on my test (test contains command '\endinputany' in the middle of text).
Please add my test to test package.

     TEST:
There is no "q in this sentence. \par
"Talk child," said the unicorn.

\endinputany
She s\"aid, "\thinspace `Enough!', he said."
\endinput

     INCORRECT ANSWER:
There is no q in this sentence. \par
``Talk child,'' said the unicorn.

\endinputany

     CORRECT ANSWER:
There is no q in this sentence. \par
``Talk child,'' said the unicorn.

\endinputany
She s\"aid, ``\thinspace `Enough!', he said.''
\endinput

New tests added to the problem. Accepted solutions were rejudged. 125 authors lost Accepted status for this problem.

New tests added to the problem. Accepted solutions were rejudged. 144 authors lost Accepted status for this problem.

My AC program prints wrong answer on this test:
9
6 7 1 6
1 8 2 6 5 1
1 2
1 3
2 4
2 5
3 4
4 6
5 6

Correct answer is NO

Hi, Admins.
Please, add these case:
N > 5*10^4
a[i] = 1, for i = 1.. N-1, and
a[N] = 10^9

Q = N
p[i] = i,  x[i] = i

For example:
77888
1 1 1 1 1 1 .... 1 1 77888
77888
1 1
2 2
3 3
4 4
5 5
...
77888 77888

> The student’s home is located at the coordinates (1, 1), and the university is at the coordinates (N, M).
It means, for example, if N == 1 && M == 1 then university have same coordinates as home. Of course we can not use any roads in such case. But according to the sentence:
> There are a total of N streets running from north to south and M streets running from west to east.
there are some roads that can not be used. I think there should be N - 1 streets running from north to south and M - 1 streets running from west to east.

Input Values is not in a range [3, 9]

First of all, we need to understand which number of teams x (from 2 to k) we need to pick to distribute our fighters into.

Through intuition we might get the idea that the bigger the K **the more the fights** (which is what is required).
It can be proven that our intuition is correct; the more you divide n the better the result, therefore we will need to divide n by k.
Proof: assuming we have n = 3, now let us assume we will distribute them to 1 team where the first team is of 3 fighters, there will be 0 fights, let us now assume we will distribute them to 2 teams where the first is of 2 and second is of 1 fighters, there will be 2 fights, lastly let us assume that we will distribute them to 3 teams where each team has a fighter, there will be 3 fights, we can then deduce that for each fighter you divide into a new group more fights are formed.
Conclusion: It is always the best choice to divide by the biggest possible number you can divide by, thus we will always divide by K.


To solve the problem we can then deduce that there will always be two cases:
Case 1 (k divides n): here we simply divide fighters into k groups, each group (composed of (n/k) fighters) will fight some other group (composed of (n/k) fighters) thus the equation for the first case is simply:
(k * (k - 1) / 2) * (n / k)^2

Case 2 (k doesn't divide n): here we notice that n will be composed of x count of floor(n / k) and y count of ceil(n / k) meaning floor(n/k)*x + ceil(n/k)*y = n, and that obviously, x + y = k, through these equations we can deduce algebraically the values of x and y, and from it form our equation.
Our equation will have x groups of floor (n / k) fighters which within them will form a specific number of fights, we will also have y groups of ceil (n / k) fighters which within them will form a specific number of fights, then we will also need an to find an equation that calculates the number of fights that happens between the x groups and the y groups, through observation and deduction you will find that this will be the equation of the second case:
((x * (x - 1) / 2) * (floor(n/k))^2) +
((y * (y - 1) / 2) * (ceil(n/k))^2) +
(floor(n/k) * ceil(n/k)) * x * y



Code:
```
#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;    std::cin >> t;
    while (t--) {
        int n, k;    std::cin >> n >> k;
        if (n % k == 0) {
            int count = k * (k - 1) / 2;
            std::cout << count * (n / k) * (n / k) << '\n';
        } else {
            int x = n - ((n + k - 1) / k) * k;
            x = x / ((n / k) - ((n + k - 1) / k));
            int y = k - x;

            int part1 = (x * (x - 1) / 2) * (n / k) * (n / k);
            int part2 = (y * (y - 1) / 2) * ((n + k - 1) / k) * ((n + k - 1) / k);
            int part3 = (n / k) * ((n + k - 1) / k) * x * y;
            std::cout << part1 + part2 + part3 << '\n';
        }
    }

    return 0;
}
```

Edited by author 18.10.2025 15:04

Edited by author 18.10.2025 15:06

Edited by author 30.10.2025 12:18

if u use rational, use int128

-476 -612
-487 -615
-478 -616

ans: 66

Where am i wrong? It should be obvious :) because it is WA2

#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <fstream>
#include <iterator>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <sstream>

using namespace std;
const double eps=1e-6;

struct R{
    int x;
    int y;
    double r;
};

R r[1111];
int a[55][55];
bool s[55][55];
int n,m,k,x,y;

int main(){
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    for(int i=0;i<k;i++){
        cin>>r[i].x>>r[i].y>>r[i].r;
        r[i].x--;r[i].y--;
        s[r[i].x][r[i].y]=true;
    }
    long res=0;
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            if(!s[i][j]){
                bool possible=true;
                double d;
                int mina=a[i][j];
                int maxa=32000;
                int _mna,_mxa;
                for(int q=0;q<k;q++){
                    d=r[q].r*r[q].r-(i-r[q].x)*(i-r[q].x)-(j-r[q].y)*(j-r[q].y);
                    if(d<-eps) {possible=false;break;}
                    d=floor(sqrt(d+eps))+eps;
                    _mna=d;_mna=a[r[q].x][r[q].y]-_mna;
                    _mxa=d;_mxa=a[r[q].x][r[q].y]+_mxa;
                    if(mina<_mna) mina=_mna;
                    if(maxa>_mxa) maxa=_mxa;
                    if(mina>maxa) {possible=false;break;}
                }
                if(possible)
                    res+=(maxa-mina+1);
            }

    cout<<res<<endl;
    return 0;
}

Edited by author 01.07.2007 04:19

Clarifications added to the problem statement regarding river basin definition, river intersection restrictions and input precision.

Tests that were invalid according to the clarifications have been fixed or replaced. Tests 9 and 13 contained overlapping segments making the river flow the same path back and forth; the tests have been replaced with new tests. Tests 15, 16, 18, 19 contained rivers with self-intersections; the tests have been corrected. Test 23 contained a river with a mouth lying on the segment of the other river and didn’t count as tributary; the test has been corrected, this situation is no longer allowed in the tests.

New tests have been added. In particular, tests with more than 2 rivers in a basin have been introduced.

All solutions have been rejudged. 106 authors lost, and 12 other authors gained the solved status for the problem.

Test 47 is some number from 1e14 to 1e18 with correct answer "No".

not N.....

use long long integer and mod operator....... fuck the double.