027 Loto

[•pauldb]

Da.

[•zeroblitz36]

Incredibil dar aceasta problema am rezolvato in O(n*log n + n^6) cu 100p.
Daca nu ma credeti, uitativa la algoritmul postat de mine.

[•silidragos]

Trebuie sa aiba cel putin un numar de fiecare?

[•ctlin04]

Poate sugera cineva vreo optimizare?
http://infoarena.ro/job_detail/630272

[•pauldb]

Daca folosesti hashing ai complexitate O(N^3), in loc de O(N^3logN).

[•wefgef]

Treci pe C++

[•dutzul]

LOL  la naiba ma uitam si nu stiam unde imi greseste programu.. eu foloseam cautare binara dar uitam sa sortez vectoru))

[•dutzul]

apropo mia dat tle pe 5 teste cand declaram variabililele long long in loc de int  hmm nu stiam ca merge mai incet

[•fhandrei]

Are cineva vreo idee de ce iau doar 95p pe sursa asta? http://infoarena.ro/job_detail/780132
Sau vreo propunere de eficientizare?

[•tzipleatud]

Are cineva vreo idee de ce iau doar 95p pe sursa asta? http://infoarena.ro/job_detail/780132
Sau vreo propunere de eficientizare?

Salut! Incearca sa implementezi cu hash-uri sau pur si simplu sa folosesti un vector, pe care mai apoi il sortezi, in detrimentul Set-ului din STL. Bafta!

[•Schumi]

Nu e nevoie de hashuri. Eu am luat 100 fara. Cred ca trebuie doar sa scapi de set

[•fhandrei]

Mersi, am luat 100 cu vectori... Dar nu inteleg de ce ar fi mai eficienti decat seturile, ca ele ma scapau de sumele duble si in plus sorteaza cu complexitate mai buna decat sort-ul pe vectori, fiind log1 + log2 + ... pana la lungimea finala a setului, ceea ce e mai putin decat nlogn

[•klamathix]

Set-ul are constanta mare. Fiind arbore de cautare, sunt ceva operatii acolo sa-l tina echilibrat. In general daca aveti nevoie doar sa sortati lucruri/extrageti cateva minime folositi sortari efective sau priority_queue care sunt dedicate si nu fac munca-n plus.

[•wefgef]

Mersi, am luat 100 cu vectori... Dar nu inteleg de ce ar fi mai eficienti decat seturile, ca ele ma scapau de sumele duble si in plus sorteaza cu complexitate mai buna decat sort-ul pe vectori, fiind log1 + log2 + ... pana la lungimea finala a setului, ceea ce e mai putin decat nlogn

Setul nu "sorteaza" intr-o complexitate mai buna decat algoritmii clasici de sortare (inclusiv cel implementat in STL), este tot O(N log N). Poti citi mai multe despre complexitati in Cormen.

[•valentinradu]

Are cineva vreo idee de ce iau numai 5 puncte pe asa ceva?

Cod:

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int n, S, a[101], i, b[7];
int descresc(int a, int b)
{
    return a > b;
}
int cresc(int a, int b)
{
    return a < b;
}
int vt = 0;
int term = 1;
void proc(int k, int Sx, int pos)
{
    if (term)
    {
        if (b[1] != 0 && b[2] != 0 && b[3] != 0 && b[4] != 0 && b[5] != 0 && b[6] != 0)
        {
            term = 0;
            sort(b + 1, b + 7, cresc);
            int v = 0;
            for (i = 1; i <= 6; i++) v += b[i];
            if (v == S)
            {
                for (i = 1; i <= 5; i++) g << b[i] << " ";
                g << b[6];
                vt = 1;
                f.close();
                g.close();
                exit(0);
            }
            else vt = 0;
        }
        for (int i = k + 1; i <= n; i++)
        {
            if (a[i] <= Sx)
            {
                if (Sx - a[i] >= 0)
                {
                    b[pos] = a[i];
                    proc(i - 1, Sx - a[i], pos + 1);
                }
                else
                {
                    proc(i, Sx, pos + 1);
                }
            }
        }
    }

}
int main()
{
    f >> n >> S;
    for (i = 1; i <= n; i++) f >> a[i];
    sort(a + 1, a + n + 1, descresc);
    for (int t = 0; t < n; t++)
    {
        proc(t, S, 1);
        for (int l = 1; l <= 6; l++) b[l] = 0;
    }
    if (vt == 0) g << "-1";
    return 0;
}

[•iulius312]

Este obligatoriu ca cele N numere sa fie toate prezente pe biletul loto? De ex. avem 4 numere: 1,2,3,4 si suma 13. Biletul loto poate fi:  1,1,2,3,3,3 ?

[•theprdv]

nu, nu este obligatoriu sa ai toate cele N nr.. de ex daca ai N = 43 poti alege de 6 ori numarul de pe pozitia 1
si inca ceva: testele nu verifica situatia prezentata mai sus, cazul in care se ia de 6 ori acelasi nr. Solutia care verifica acest lucru ( http://www.infoarena.ro/job_detail/1514247 ) ia tot 100 ca cea care nu verifica: http://www.infoarena.ro/job_detail/1514257 (verifica doar pt ultima pozitie)

Cod:

Ex test:
3 12
10 2 50