You guys have to sort the roads to be the same sequence as the input
means first input,first output

Edited by author 04.07.2018 23:18

Edited by author 04.07.2018 23:18

Edited by author 04.07.2018 19:52

I have an O(n*log(n)) algorithm, which works successfull on all test
cases at my Celeron 300. The time of working is incredible low (I
used test with 15000 stars), but timus gives me Time limit exceeded.
If anyone here has an idea where is the matter, I am ready to share
my program with him.

Thanks a lot if anyone can give me some help!

1 17
a 100 8

            long min = n;
            for (int i = 0; i < k; i++)
                for (int j = i + 1; j < k; j++) {
                    long diff = (data[i] + data[j] - n);
                    if (diff < min)
                        min = diff;
                }
            Console.WriteLine(min < 0 ? 0 : min);

Just use __int64 instead of long long. That helped me.

the original answer of fskdkskylp is ansthisone but my accepted code give this answer aêsthisone.


my accepted code


#include<bits/stdc++.h>
using namespace std;
int main()
{
    char c[104];
    scanf("%s",c);
    int l=strlen(c);
    int a[l+5];
    int b[l+5];
    for(int i=0; i<l; i++)
    {
        a[i]=c[i]-'a';
    }
    b[0]=a[0];
    if(a[0]<5)
    {
        b[0]=b[0]+26;
    }
    for(int i=1; i<l; i++)
    {
        int j=1;
        while((b[i]=a[i]+j*26))
        {
            if(b[i]%26==a[i]&& b[i]>=b[i-1])
                break;
            j++;
        }
    }
    printf("%c",b[0]-5+'a');
    for(int i=1; i<l; i++)
    {
        int j=abs(b[i]-b[i-1]);
        printf("%c",j+'a');
    }
    printf("\n");
    return 0;
}

9 8
1 2
1 6
1 8
1 3
1 4
4 5
1 7
7 9
Answer:
3
7 9
1 2
4 5

If you've got WA #11 then your program deals bad with repeatative queries.

Try this test:
--------------------
2
acm 10000
acmicpc 10000
2
ac
ac
---------------------
Correct answer is:
---------------------
acm
acmicpc

acm
acmicpc
---------------------

Is it true that k=f(n), where f(n) is Euler function?

Edited by author 13.02.2009 22:03

Answers for big tests is very big. For example, for test "50 500" answer is "854559745684320697549060368131279814466643179689928095831053239604130293492672614469791533133321".
Don't use long long or int64! Use long numbers (long arithmetic)! (Длинная арифметика)

It's really very easy problem! Just shuffle!

#include<bits/stdc++.h>
using namespace std;
int arr[15000],newarr[15000];
void sieve()
{
    arr[0]=1;
    arr[1]=1;
    newarr[1]=2;
    for(int i=4; i<15000; i+=2)
        arr[i]=1;
    for(int i=3; i<15000; i+=2){
        if(arr[i]!=1){
            for(int j=i*2; j<15000; j+=i){
                arr[j]=1;
            }
        }
    }
}

int main()
{
    int n, t, k=1;
    sieve();
    //cin>>n;
    for(int i=1; i<15000; i++){
        if(arr[i]!=1){
            newarr[k]=i;
            k++;
        }
    }
    cin>>t;
    while(t--){
        cin>>n;
        cout<<newarr[n]<<endl;
    }

    return 0;
}

Calculate the signed area of the polygon...

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define re return
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define pi (3.14159265358979323846264338327950288419716939937510)
#define fo(i, n) for(int i = 0; i < n; ++i)
#define ro(i, n) for(int i = n - 1; i >= 0; --i)
#define unique(v) v.resize(unique(all(v)) - v.begin())

template <class T> T abs (T x) { re x > 0 ? x : -x; }
template <class T> T sqr (T x) { re x * x; }
template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; }
template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef double D;
typedef long double ld;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree;

vector< tuple <int, int, string> > v;
vs ans;

int calc() {
    string ans;
    cin >> ans;
    re (ans[0] - '0') * 6000 + (ans[1] - '0') * 600 + (ans[3] - '0') * 100 + (ans[4] - '0') * 10 + (ans[6] - '0');
}

int main() {
    int best = (int) 1e9, n, cur;
    cin >> n;
    string str;
    fo(i, n) {
        cin >> str;
        cur = calc();
        v.pb(make_tuple(cur + i * 300, cur, str));
    }
    sort(all(v));
    int finish, res;
    fo(i, v.size()) {
        tie(finish, res, str) = v[i];
        if (res < best) {
            best = res;
            ans.pb(str);
        }
    }
    sort(all(ans));
    cout << ans.size() << endl;
    for (auto &j : ans) cout << j << '\n';
    re 0;
}

Edited by author 22.06.2018 17:22

I wrote suffix automaton, and with it's help i found solution in 5 lines.

It's unbelieveable, how couldn't I solve it during the contest.
Just brute-force for finding answers for smalls n...