Cod sursa(job #1002007)

Utilizator yololy97Olaru Bogdan-Ioan yololy97 Data 26 septembrie 2013 18:23:06
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.05 kb
#include <cstdio>
#include <algorithm>
#define N 101
using namespace std;
int n, S, h;//o trimit?da
struct nod{
    int i, j, k;//mai trebuie vreo variabila? nu neaparat pt ca daca ai indicii, poti afla suma 
};
nod x[N * N * N];
int v[N];
struct comp{
    bool operator()(const nod &a, const nod &b) const {
        return v[a.i] + v[a.j] + v[a.k] < v[b.i] + v[b.j] + v[b.k];
    }
};
int bsearch(int l, int r, int sum){// returneaza ceva fctia asta?//da..int sau long long?

    // daca tot i-ai pus, fa recursiv :D :)) 
    if (l >= r) {
        if (v[ x[l].i ] + v[ x[l].j ] + v[ x[l].k ] == sum){
           return l;
        }
        else return 0;
    }
    // nu iti mai trebuie else ca oricum ai return mai sus
    int m = (l + r)/2;
    int val = v[ x[m].i ] + v[ x[m].j ] + v[ x[m].k ];
    // te duci pe stanga sau pe dreapta infctie de sum (daca sum < val sau >=)
    // daca sum == val ?
    if (sum == val)
        // apropo, daca poti elimina else-urile e mai bine , e mai rapid codul
        return m;//bun
    if(sum < val)
        return bsearch(l, m, sum);
    else
        return bsearch(m + 1, r, sum);//?!? mai trebuie ceva la fctie
        //si pt sum ce pun? pai ce pui?:)) val? de ce ai pune val? sum e suma pe care o cauti binar... se schimba? nu :D
        /// n-am zis ca facem recursiv? ma dau cu capu de pereti ca n-am inteles ce sa fac..:-??

        // aci recursiv? nu:(( pai atunci de ce ai pus l si r ca parametri? scuze..
}
int bsearch2(int sum) {
    //care aia smechera? aia in care incerci i + 2^k? :O, ti-am arat-o data trecuta cand am facut bsearch la problema tri
    int i, cnt;
    for (i = 1, cnt = (1 << 20); cnt; cnt >>= 1)
        if (i + cnt <= h && v[ x[i + cnt].i ] + v[ x[i + cnt].j ] + v[ x[i + cnt] .k] <= sum)
            i += cnt;
    if (v[ x[i].i ] + v[ x[i].j ] + v[ x[i].k ] == sum)
        return i;
    return 0;
}
void solve(){
    int i, j, k;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <=n ; ++j)
            for(k = 1; k <= n; ++k)
                x[++h].i = i,
                x[h].j = j,
                x[h].k = k;
    // acum trebuie sa sortezi dupa suma vectorul x cum fac asta..?
    // cum ai facut si la problema int:| nu imi amintesc..:-??
    // pai intai trebuie sa faci o structura si un comparator in el
    sort (x + 1, x + h + 1, comp());
    // acum iei din nou oricare 3 si cauti binar suma S - v[i] - v[j] - v[k]//pai si ce obtin daca am s- v[i]-v[j]-v[k]? daca gasesti obtii solutia ca ai deja 3 indici i j si k si inca 3 pe care ii gasesti deci in total 6 cu suma S
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= n; ++j)
            for(k = 1; k <= n; ++k){
            // fa fctie separata pt bsearch
                // acum foloseste-o aici //bun?da
                int p = bsearch2(S - v[i] - v[j] - v[k]);// apropo, sigur apelezi bine bsearch?
                if (p > 0) {
                    printf("%d %d %d %d %d %d\n", v[i], v[j], v[k], v[ x[p].i ], v[ x[p].j ], v[ x[p].k]); //pai si celelalte de unde stiu care sunt?
                    return;
               }
               // ai 2 optiuni: prima e sa cauti din nou cu 3 foruri si sa vezi suma S - v[i] - v[j] - v[k]
               // sau modifici bsearch sa iti dea indicele din x ca sa poti sa iei elementele de acolo
               // a doua e mai buna:)) de ce emai buna? pentru ca nu trebuie sa mai caut odata?= aSa si? complexitatea ramane tot n^3...
               // defapt nu, tot n^3 logn, daca faci inca n^3 inseamna n^3 (log n + 1) deci tot aia e...
               // intelegi ce zic? da dar tot pe a doua o aleg..:)) ok
            }
    
    printf ("-1\n");// aici ajunge cand nu gaseste solutie pt ca nu iese cu return din solve()ok
}//altceva? cum ai facut tu o sa-ti afiseze toate solutiile pai asta urma sa mai intreb nu trebuie sa ii dau sa se opreasca dupa ce a gasit solutia..?
// poti sa-i dai return; ca sa iasa din fctie si mai trebuei aia cu -1; pai pui la final -1
int main(){
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    scanf("%d %d ", &n, &S);
    for(int i = 1; i <= n; ++i)
        scanf("%d ", &v[i]);
    solve();
}