Edited by author 26.03.2009 23:03

Edited by author 26.03.2009 23:03

There is full solution!!! Try thinking yourself or using hints before watching it
and use visual c++ 2017
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
#define pb push_back

using namespace std;
const int N = 50000;

pair<int, int> dp[N], right_end[N];
vector<pair<int, int> > v;
vector<int> ans;
unsigned main()
{
    for(int i = 0; i < N; i++)
    {
        right_end[i].first = -50001;
        right_end[i].second = -50001;
    }
    int m;
    cin >> m;
    int l, r;
    int k = 0;
    while(true)
    {
        cin >> l >> r;

        if(l > m || r < 0) continue;

        if(l == 0 && r == 0) break;

        v.pb({l, r});

        if(r > right_end[l].first)
        {
            right_end[l].first = r;
            right_end[l].second = k;
        }
        k++;
    }

    int i = 0;
    for(auto it: v)
    {
        if(it.first <= 0 && it.second > 0)
        {
            if(it.second > dp[0].first)
            {
                dp[0].first = it.second;
                dp[0].second = i;
            }
        }
        i++;
    }
    for(int i = 1; i <= m; i++)
    {
        if(dp[i - 1].first >= right_end[i].first)
        {
            dp[i].first = dp[i - 1].first;
            dp[i].second = dp[i - 1].second;
        } else
        {
            dp[i].first = right_end[i].first;
            dp[i].second = right_end[i].second;
        }
    }
    for(int i = 0; i <= m; i++)
    {
        if(dp[i].first < i)
        {
            cout << "No solution" << endl;
            return 0;
        }
    }
    int pos = 0;
    while(pos < m)
    {
        ans.pb(dp[pos].second);
        if(dp[pos].first == pos)
        {
            cout << "No solution" << endl;
            return 0;
        }
        pos = dp[pos].first;
    }
    cout << ans.size() << endl;
    for(auto it: ans)
    {
        cout << v[(int)it].first << " " << v[(int)it].second << endl;
    }
}

Edited by author 09.02.2020 01:50

#include<iostream>
using namespace std;
float sqrt(long long2 n,int p)
{
    int start = 0;
    int end = n;
    float ans;
    int mid;
    while(start <= end)
    {
        mid = (start+end)/2;
        if(mid*mid < n)
            start = mid + 1;
        else if(mid*mid > n)
            end = mid - 1;
        else
        {
            ans = mid;
            break;
        }
    }
    float increment = 0.1;
    for(int i = 0; i < p;i++)
    {
        while(ans * ans <= n)
        {
            ans += increment;
        }
        ans -= increment;
        increment /= 10;
    }
    return ans;
}
int main()
{
    long long int n;
    while(cin >> n)
    {
        cout << sqrt(n,4) << endl;
    }
}

Please, help with this test. I am always getting WA on it.
I did 2 assumptions:
1. If after any iteration the radius becomes irrational - then the answer will be irrational too.
2. The numerator and denominator of resulting fraction both don't exceed 2^64.
Are these assumptions wrong? If so, please, give me some useful tests. The one interesting test I found is:
1 1 30 34785346
3131185849/1170753394542713625
But it doesn't help me much...

Edited by author 04.02.2011 02:56

I have WA in the 9th test, please tell me this test.

Test case #6:

9 40
10 10 10 10 10 10 10 10 10 10
0 5 6 1 0 0 0 0 0 0
12 20

Answer: 158882255


Test case #12:

10 20
52 4 2 3 6 7 6 3 6 5 6
6 0 0 0 0 1 0 0 0 0 1
10 50


Answer: 978217740

PyCharm calculates n=2000 in 0.55 sec while here I got exceed time limit with 2.020 sec. I don't get it.

Can't find the error, because it gives the same answers as those stupid precalc solutions:

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int soma[40] = {0};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, i, lim;
  ll ans = 0;
  cin >> n;
  lim = pow(10, n/2);
  for(i=0; i<lim; ++i){
      soma[i%10 + (i/10)%10 + (i/100)%10 + (i/1000)%10]++;
  }
  for(i=0; i<=n*9; ++i){
      ans += soma[i]*soma[i];
  }
  cout << ans << '\n';
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,q,a[100003],b[100003],c[100003];
vector<pair<int,int> >v;
vector<int>g[100003];
bool vis[100003];
int qq[100003];
map<int,int>mp;
void dfs(int x,int cc){
    vis[x]=1;
    for(int i=0;i<g[x].size();i++)
        if(!vis[g[x][i]])
            dfs(g[x][i],cc);
    qq[x]=cc;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>a[i]>>b[i],
        a[i]--,
        b[i]--;
    cin>>q;
    for(int i=0;i<q;i++)cin>>c[i],c[i]--,v.push_back(make_pair(a[c[i]],b[c[i]])),a[c[i]]=b[c[i]]=-1;
    reverse(c,c+n);reverse(v.begin(),v.end());
    for(int i=0;i<m;i++)
        if(a[i]!=-1)
            g[a[i]].push_back(b[i]),
            g[b[i]].push_back(a[i]);
    int cnt=0;
    for(int i=0;i<n;i++)
        if(!vis[i])
            mp[cnt]=cnt,
            dfs(i,cnt++);
    vector<int>ans;
    for(int i=0;i<q;i++){
        ans.push_back(cnt);
        if(mp[qq[v[i].first]]!=mp[qq[v[i].second]])
            mp[qq[v[i].first]]=mp[qq[v[i].second]],
            qq[v[i].first]=qq[v[i].second],
            cnt--;
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<' ';
}

JavaEntryPointWrapper.java:10: error: cannot access Oppa
            Oppa.main(args);
            ^
  bad source file: .\Oppa.java
    file does not contain class Oppa
    Please remove or make sure it appears in the correct subdirectory of the sourcepath.
1 error
Выходит такая ошибка, почему?

Please give this test!
lifanov@mail.ru

Please, delete my account. I don't need it anymore.

Please, delete my account. I don't need it anymore.

but I couldn't find any way to delete the post

Edited by author 27.01.2020 01:24

Edited by author 27.01.2020 01:24

Edited by author 27.01.2020 01:24

I've passed all the tests the forum had. Can someone give me more

Try the following 2 tests:

2
0
10000
2
20000
10000

and

2
0
10000
2
0
-10000

What answer is issued by your program?

Edited by author 14.02.2013 20:37

Very easy:)

*first if k>n/2 make it smaller n/2: k=n-k+1

*then the answer is (n-k-2)

 (......[Vasya].......[n-1][n]
  if [n-1] and [n] sit,then all people between
  [Vasya] and [n-1] will stumble at Vasya.
  And this will be the maximal answer )

*special case: n=2 => answer is 0

n = 1

Hello

My solution failed on test 21. Passed next cases:

5 5
2 2 2 3 4
0 0

5 4
4 1 4 1 2
3 2

5 4
2 2 1 1 1
5 2

5 7
4 1 4 1 2
3 1

10 18
2 2 2 2 2 2 2 2 2 2
0 0

If you have any idea please let me know. Thank you

Edited by author 21.08.2015 10:49