????a
4

answer: zayba

Edited by author 26.01.2022 08:53

Instead of writing this: vector<int> g[2001];

write this: vector<vector<int>> g;............g.resize(n + 1);

Edited by author 09.06.2022 23:22

I do here according to the test case description. But I need some hint what actually wanted in this problem.

        if(a[i]<k){
       ans+=k-a[i];
        }
        else{
       ans1+=a[i]-k;
        }

Problem description is very unclear on what to do when N=0.

I believe that either
 * test case N=0 must be clarified or
 * lower bound of N must be set to 1.

Hint: In current test suite the correct answer for N=0 is empty output.

If using recursive algorithm increase recursion depth limit at least 4000. For my algo 2000 was not enough

import sys
sys.setrecursionlimit(4000)

>>> print(round(0.0))
>>> 0.0
But
"The output should contain the required distance in meters rounded to two fractional digits"
So don't forget to use string formatting to provide 2 digits after comma

Real test case:
5 90 2.50
0.00

This is proof of why answer < 3.

Suppose, we have 3 elements x, y, z, with gcd(x, y, z) != 1. Then, after first transformation array will contain elements: gcd(x, y), gcd(x, z), gcd(y, z), Let's call them a = gcd(x, y), b = gcd(x, z), c = gcd(y, z). After second tranformation array will contain elements: gcd(a, b), gcd(a, c), gcd(b, c), we can notice, that:
gcd(a, b) = gcd(gcd(x, y), gcd(x, z)) = gcd(x, y, x, z) = gcd(x, y, z). Doing similar things with gcd(a, c) and gcd(b, c), it turns out, that gcd(a, b) = gcd(a, c) = gcd(b, c) = gcd(x, y, z). That means, that after 2nd transformation array will contain 3 equal numbers greater than 1. I think it's obvious, that answer will be infinity, if array contains 3 equal numbers greater than 1.


Now, if gcd of any tripple of numbers equals one, that means, that we will end in less than 2 transformations (Proof this by yourself)

Edited by author 22.01.2022 15:49

var
  a: array[1..2000] of string;
  i: integer;
begin

  for i := 1 to 2000 do
  begin
    if (i >= 1) and (i < 5) then a[i] := 'few';
    if (i >= 5) and (i < 10) then a[i] := 'several';
    if (i >= 10) and (i < 20) then a[i] := 'pack';
    if (i >= 20) and (i < 50) then a[i] := 'lots';
    if (i >= 50) and (i < 100) then a[i] := 'horde';
    if (i >= 100) and (i < 250) then a[i] := 'throng';
    if (i >= 250) and (i < 500) then a[i] := 'swarm';
    if (i >= 500) and (i < 1000) then a[i] := 'zounds';
    if i >= 1000 then a[i] := 'legion';
  end;

  readln(i);
  writeln(a[i]);

end.

Edited by author 05.12.2007 18:27

Your memory limits are too tight for 64-bit compilers and using 32-bit Visual C++ instead is not such a good idea because of its weird behavior.

Rust releases new version every 6 weeks. Even if this is too frequent please update it at least every half year

Test #10 contains some non utf-8 characters.
That could be the reason of panic if you use Go or Rust languages.

Just pay attention when Conviviality rating < 0.

floor(x) or round(x) - wa7
(int)x - OK

Can anybody describe the solution please ?

I noticed a lot of people complain about WA2. Just wanted to share my experience, since I got WA2 several times. Don't forget that after you read the number, you haven't read the newline after it. So cin.getchar + cin.ignore and getline(cin, ...) get that exact newline.

So we must try to make teams have equal size. Why?
Consider two teams with x and y members respectively, and consider x > y. Sending a member from first team to second team will only affect matches between these two teams. At first we have x*y different matches between the teams. If we send a player to the second team, there are now x-1 and y+1 members in each team. The matches are now
(x-1)*(y+1) = x*y + (x-y) - 1
As we said x > y, x-y > 0, so x-y-1 >= 0 and our change can't reduce the total number of matches, so it is an optimal change.
This also shows that nothing changes when x = y+1, so if we can't make all teams equal size, just add each of the ones remaining into a different team, making a difference of at most 1 in the sizes of teams.

Now it's your job to compute the number of matches, I won't show that, but it can be done with a one line formula. Good luck :)

I have solved this problem by using an easy greedy algorithm.

MAIN: you need to use an idea of 2 pointers(of course you need to sort array) and take the rightest segment. Left part of segment need to be <= x(another pointer)

The solution below:

void solve() {
    int m;
    cin >> m;
    vector< pair<int, int> > pi;
    int a, b;
    cin >> a >> b;
    while (a || b) {
        pi.pb({a, b});
        cin >> a >> b;
    }
    sort(all(pi));
    int cnt = 0, j = 0;
    vector< pair<int, int> > ans;
    j = 0;
    int x = 0;
    for (; j < sz(pi) && x < m; j++) {
        int k = j;
        int mx = x;
        pair<int, int> par = {-INF, -INF};
        while (k < sz(pi) && pi[k].ff <= x) {
            if (mx < pi[k].ss) {
                mx = pi[k].ss;
                par = pi[k];
            }
            k++;
        }
        if (par.ff == -INF) {
            cout << "No solution\n";
            return;
        }
        x = mx;
        ans.pb(par);
        if (k > j)
            j = k - 1;
    }
    if (x < m) {
        cout << "No solution\n";
        return;
    }
    cout << sz(ans) << '\n';
    for (auto &i : ans) {
        cout << i.ff << ' ' << i.ss << '\n';
    }
}

I dont understand why difficulty is 121, i think it's easy problem