but Kosaraju + scanf + MS compiler may help here

1) 11 !!!! - 231
2) 13 !! - 135135
3) 36 !!!!!! - 33592320
4) 7 !!!!! - 14
5) 21 !!!!!!! - 2058

and DONT forget that (n mod k) or k is not the last multiplayer
rus: не путайте, (n mod k) или k не являются последним множителем!!

If you got problems with WA 20 (new test), just know - it is because of precision issue. Not use double or long double - only long integer arithmetic   or   integer modular arithmetic.

P.S.
   authors of new tests - it is not good to add tests to the OLD task after 23 years of time passed. It is so strange. Why authors of solutions must return to the OLD task and resolve it again???????

New tests were added. All accepted solutions were rejudged, ~60% of them lost their Accepted status.

So I was checking if the 2 vertices of the graph already connected, but didn't consider the test below and wasted a lot of time looking for a mistake and rewriting the code

4 3
1 2 1
3 4 2
2 3 3

Correct output:
3
3
1 2
3 4
2 3

My output:
2
2
1 2
3 4

Check 524288, should be NO.
Test other cases where you have 19 factors, and the last one remaining is 1.

Try your generated //CPP code with MSVC to check if there's any compile error.
If you don't have MSVC installed, just submit the *generated* code.

You have to make one more "if"
######################################################################################
d = math.sin(p1) * math.sin(p2) + math.cos(p1) * math.cos(p2) * math.cos(abs(l1 - l2))
if str(d) == '-1.0000000000000002':
    d = int(d)
d = math.acos(d) * 3437.5
######################################################################################
there is a test where '-1.0000000000000002' in d so thats why acos gives error, you have to change '-1.0000000000000002' to -1

Edited by author 20.04.2023 21:49

Edited by author 20.04.2023 21:49

//URAL-1100-FINAL STANDINGS

//---------------------------------
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'


bool comp(pair<int,int>a,pair<int,int>b)
{
    return a.second>b.second;
}
void sortt(map<int,int>mp)
{
    vector<pair<int,int>>v;
    for(auto it:mp)
    {
        v.push_back(it);
    }

    stable_sort(v.begin(),v.end(),comp);
    for(auto it:v)
    {
        cout<<it.first<<" "<<it.second<<endl;

    }
}
int main()
{
    map<int,int>mp;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
        mp[x]=y;
    }
    sortt(mp);


    return 0;
}

In my AC solution I didn't use the fact that "there is no substrings in the form xyxyx" anywhere. My program even assumes the answer in this problem can be "-1", but I guess there are no such testcases in this problem because of this advanced condition.

So, could anybody tell me how this fact helps to simplify the solution? Or, maybe, anybody can prove or deny my hypotesis about "-1"? Thanks in advance!

I have always been interested in applied programming (since 9th grade), but less than an year ago I discovered a great hobby - solving competitive programming problems.

After the 200th AC, I would say This Online Judge is great, and I wish everyone motivation and good luck!

I've used this formula to solve this problem:
a(n) = 2^(b(n)-1) + a(n - c(1+b(n)))
b(n) = -1+floor(log(((n+0.2)*sqrt(5)))/log((1+sqrt(5))/2));
c(0) = 0, c(1) = 1, c(n) = c(n-1) + c(n-2)

Why this problem has 175 difficulty?
I thought it has very hard to implement solution, but to sovle it you should do what exactly said in staitment...

New tricky tests have been added to the problem.
All solutions have been rejudged. 152 authors (62% of all) lost their solved status for the problem.

import java.util.Scanner;

public class Task_2100 {
    public static void main(String[] args){
        Scanner scr1 = new Scanner(System.in);
        Scanner scr2 = new Scanner(System.in);

        int n, counter;
        n = scr1.nextInt();
        counter = n+2;
        while(n-- > 0){
            String guest = scr2.nextLine();
            String substring = "+";
            if(guest.contains(substring)){
                counter++;
            }
        }
        if(counter==13) {
            counter++;
        }
        System.out.print(counter*100);
    }
}

If you sort segments according to INCREASING length.  Then you can consider all segments one by one consecutively.  Find points belong to the current segment.  For those points current segment is the answer.
Because of the segments are sorted.

Unexpected result: the solution using z-function is O(n) but gives TLA on the 8th test. The solution doesn't pass so I will leave the code with it here. I'm wondering if it really doesn't pass the 8th test because it is too slow though is O(n), or if there's just some kind of error in my algorithm.

vi ZFunction(string &p, string &s) {
  int n = (int) p.size();
  vector<int> z(n + 1);
  for (int i = 0, l = 0, r = 0; i < n; ++i) {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && p[z[i]] == s[i + z[i]])
      ++z[i];
    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return z;
}

  ....
  vector<int> z_func = ZFunction(s1, s2);
  vector<int> z_func2 = ZFunction(s2, s1);
  for (int i = 0; i < n; ++i) {
    if (z_func[i] == n - i && z_func2[n - i] == i) {
      cout << i;
      return;
    }
  }
  cout << "-1";

Edited by author 13.04.2023 23:25

Edited by author 13.04.2023 23:25

Edited by author 13.04.2023 23:27

Check your "MAXN" constant

I`m using vector of segments.
Everything is pretty fast, All the tests I could think of work correctly.

EDIT:
Finally, got a pretty good AC - Time: 0.234, Memory: 5 032 KB.
(The problem was that I was not monitoring for segments getting empty)

Edited by author 12.04.2023 23:40