I was wondering if there was a greedy solution to this problem help please.

Solved with O(n * (m+max("filling value")) * 10^3). Anyone better?
Strange thing: seems like in tests 15-16 max("filling value") is good deal smaller than 10.0, because O(n * (m+10) * 10^3) failed.

when it may be «It is a lie!».

Does anybody have an idea ?

Edited by author 04.04.2010 08:24

Solution is pretty straightforward based on parity and bit position, but to avoid all those position reflections in your head during coding, generate codes for say N=5 and look at value of "k XOR x"

i found mistake :)


Edited by author 07.08.2022 13:48

Are there beautifull solution? The one other from bruteforce

My solution is O(tl^3logn) , but its performance is good.

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
    int N, sum = 0;
    cin>> N;

    if(N > 0)
    {
        for(int i = 1; i <= N; i++)
        {
            sum = sum + i;
        }
    }
    else if(N <= 0)
    {
        for(int i = N; i <= 1; i++)
        {
            sum = sum + i;
        }
    }

    cout<< sum << endl;

    return 0;
}

a=int(input())
b=0
for i in range(a):
    n,l=map(int, input().split())
    b=b*10+n+l
print('0'*(a-len(str(b))),b, sep='')

If you calculate with formulas, then long long is not enough. You can use __int128. You can't read and write it, but you can cast it to and from other integer types.

Bruteforcing in range [0, 4e7] gives WA9, bruteforcing in range [1e8-4e7,1e8] gives AC

Edited by author 28.07.2022 20:34

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n1,n2;
    int a[n1],b[n2];
    cin>>n1;
    for(int k=0;k<n1;k++) cin>>a[k];
    cin>>n2;
    for(int k=0;k<n2;k++) cin>>b[k];
    sort(a,a+n1);
    sort(b,b+n2);
    int i=0,j=n2-1;
    bool ans=false;
    while(i<n1&&j>=0){
        if(a[i]+b[j]==10000){
            ans=true;
            break;
        }
        else if(a[i]+b[j]>10000){
            j--;
        }
        else{
            i++;
        }
    }
    if(ans) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

/*
::::
author:@DEANNOS at CODEFORCES 2022
::::
*/



#include <bits/stdc++.h>
//using policy based stl
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
#define endl "\n"
#define mod 1000000007
#define ll long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ld  long double
#define ff  first
#define ss  second
#define vs  vector<string>
#define vpll vector<pll>
#define vb  vector<bool>
#define pb push_back
#define bg begin()
#define mp make_pair
#define ed end()
#define gi greater<int> ()
#define srt(v) (sort(all())
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;i<n;i++)
const int INF = 1000000000;
const int MAX_N = 2e5;



/*
int fastpower(int x, int y, int mod)
{
    int res = 1;
    x = x % mod;
    if (x == 0)
    {
     return 0;
    }
    while (y > 0)
    {
        if (y & 1)
        {
         res = (res*x) % mod;
        }
        y = y>>1;
        x = (x*x) % mod;
    }
    return res;
}
*/

/*
int GCD(int a,int b)
{
 while(b!=0)
 {
  int rem=a%b;
  a=b;
  b=rem;
 }
 return a;
}
*/

ll integer(ll a)
{
    return a >= 0 ? a : -a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    ll ans1 = 1, ans2 = 2, mx = 0;
    ll a;
    cin >> a;
    for (int i = 1; i < n; i++)
    {
        ll b;
        cin >> b;
        if (integr(a - b) > mx)
        {
            mx = integer(a - b);
            ans1 = i;
            ans2 = i + 1;
        }
        a = b;
    }
    cout << ans1 << ans2 << endl;
    return 0;

}

1. Вы пишите:найти для экскурсии кратчайший маршрут, начинающийся и заканчивающийся в одном и том же месте, т.е. количество перекрестков в маршруте должно быть N+1?. в след. абзаце: Все числа x1, …, xk должны быть различны. т.е.  либо маршрут не должен заканчиваться на том же перекресте где начался либо должно быть дополнительное условие Х1=Хк. это принципиальная ошибка в условии.
2. пример который вы привели:
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
4 3
1 2 10
1 3 20
1 4 30
-1
дает результат:
1 3 5 2
No solution.
а куда вы в первом тесте дели перекрестов №4?
3. Исходя из примера маршрут не должен содержать в себе все перекрестки?

Ошибки очевидны. те решения, что вы приняли - частные, случайно полученные.
Уточняйте условия и проверяйте свое решение.

Edited by author 07.11.2014 13:33

Что-то я не совсем понял условие задачи.
"M двусторонних дорог" - т.е. вроде как не ор. граф.
Но пример и решение говорят, о том, что скорее это все таки ор. граф.

1 3 300
3 1 10

Так есть ориентация у ребер или нету?

6 6
1 2 1
1 3 1
2 3 10
4 5 2
4 6 2
6 5 2
-1

ANS:
4 5 6

Don't calculate second probability, instead calculate probability that sergey will come to the cafe in the same time both on the first path and on the second. Using this probability you can easily calculate second answer