11-12 Subiecte

[•ParrAzitU]

1 - Domino
Se considera n dominouri din care se pot construi siruri respectand urmatoarele reguli :
 - Prima piesa face obligatoriu parte din sir
 - Urmatoarele piese se iau in ordinea data (se decide dc o piesa se va pune sau nu in sir)
 - Fiecare piesa se pune la un capat al sirului deja format in pozitia in care a fost data sau invartita cu 180, sau se arunca si nu se mai revine la ea
 - O piesa poate fi pusa la un capat al sirului daca numarul de pe dominoul din capat (pe jum nealipita deja) si numarul de pe dominoul care se alipeste la pasul curent sunt egale.

Determinati cel mai lung sir de dominouri.

Domino.in : n si pe urm n linii xi, yi - fetele unui domino
Domino.out : lungimea

Restrictii : 1 <= n <= 100.000
  0 <= x,y <= 9

ex:
Domino.in
6
1 2
1 5
2 3
1 4
2 3
4 3
Domino.out
5

[•ParrAzitU]

2 - luna
Firmele de pe pamant doresc construirea unor cladiri de forma dreptunghiulara pe luna. Evident fiecare firma va putea construi doar pe teritoriul alocat ei.

Pe prima linie a fisierului de intrare luna.in se da n, m : dimensiunile suprafetei lunii (care e o matrice cu elemente naturale maxim 100, de dimensiuni maxim 50 x 50 )
Pe urmatoarele linii e descrisa matricea
Apoi pe urm linie se da k <= 100.000 (nr de cereri)
Pe urmatoarele k linii sunt 3 numere reprezentand numarul de ordine al tarii si dimensiunile l x c a cladirii drept. pe care vrea sa o construiasca firma.

Pe fiecare linie din fisierul de iesire luna.out(corespunzatoare unei cereri) se va scrie
Cererea poate fi satisfacuta! - dc tara poate construi cladirea
Cererea nu poate fi satisfacuta! - dc tara nu poate construi
Tara de provenienta nu exista! - dc tara nu are pe luna proprietate

ex :
luna.in
5 10
1 1 1 2 2 2 2 3 3 4
1 1 1 2 2 2 2 3 3 4
5 5 5 2 2 2 2 7 7 4
5 5 5 6 6 6 6 7 7 4
5 5 5 6 6 6 6 7 7 4
6
1 2 3
2 3 4
1 3 2
7 20 20
8 44

luna.out
Cererea poate fi satisfacuta!
Cererea poate fi satisfacuta!
Cererea nu poate fi satisfacuta!
Cererea poate fi satisfacuta!
Cererea nu poate fi satisfacuta!
Tara de provenienta nu exista!

Eu am facut 99 din 200 in total.. Busind    implementarile ... si am fost al 2-lea..

[•DeadStar]

Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic..

[•greco]

Mda.... si ce ai reusit sa busesti?  

[•ParrAzitU]

Pai nush sigur.. cred ca recurenta la prima..  
Si la a 2-a la precomputare..  

[P3riutz@]

Pt ParrAzitU.
 Ce ai facut la concurs? Cum ti so parut baia mare?

[•SleepyOverlord]

Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic..

...Totusi nu s-a luat nici un punctaj maxim, la nici una din ele...

Pe de alta parte, tratare superficiala rulez, gl hf la pd clasica pt n<=100000

[cristi8]

Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic..

...Totusi nu s-a luat nici un punctaj maxim, la nici una din ele...

Pe de alta parte, tratare superficiala rulez, gl hf la pd clasica pt n<=100000

...pai nu intra usor "pd clasic" cu n<=100000 si Xi,Yi <=9 ?

..poate am inteles eu gresit problema... dar pare O(n) ... cu o constanta destul d mare, dar ar trebui sa intre "lejer" in timp..

[•SleepyOverlord]

Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic..

...Totusi nu s-a luat nici un punctaj maxim, la nici una din ele...

Pe de alta parte, tratare superficiala rulez, gl hf la pd clasica pt n<=100000

...pai nu intra usor "pd clasic" cu n<=100000 si Xi,Yi <=9 ?

..poate am inteles eu gresit problema... dar pare O(n) ... cu o constanta destul d mare, dar ar trebui sa intre "lejer" in timp..

Prin "pd clasic" eu am inteles O(n^2)...

[•ParrAzitU]

Complexitatea oficiala la Domino era O(n).. bine O(40*n)
se parcurgeau domniourile, luand a[j] = best, pt prima piesa cu fata libera i si ultima piesa cu fata libera j..

[cristi8]

hmmm.. stau si ma gandesc... nu merge O(n) curat ? fara constante mari.. si doar cu un vector a[10] .. care se tot inbunatateste la fiecare pas.. (se parcurg dominourile de la sfarsit la inceput)

..intelegeti ce vreau sa spun ?

[•SleepyOverlord]

hmmm.. stau si ma gandesc... nu merge O(n) curat ? fara constante mari.. si doar cu un vector a[10] .. care se tot inbunatateste la fiecare pas.. (se parcurg dominourile de la sfarsit la inceput)

..intelegeti ce vreau sa spun ?

Poti pune la ambele capete asa ca ai nevoie de matrice

[•SleepyOverlord]

Complexitatea oficiala la Domino era O(n).. bine O(40*n)
se parcurgeau domniourile, luand a[j] = best, pt prima piesa cu fata libera i si ultima piesa cu fata libera j..

Am uitat sa zic, eu sunt autorul, banuiesc cu tine am vb pe coridor

[•domino]

Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred.  

[•SleepyOverlord]

Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred.  

Runda 10, cu limite mult mai mici.

[•domino]

Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred.  

Runda 10, cu limite mult mai mici.

Da, dar problema era cam aceeasi ca la GInfo n-au pus limita pt K deci trebuia sa faci cat mai bine...

[•Cosmin]

Mi-a zis sleepy acuma ca sursa oficiala mergea in O(n^2*m^2+k) , e nasol ca nu s-a luat maxim ... prima mea idee era de O(n^2*m + k) si e destul de banala ... O sa fie naspa pt ardeleni la ONI.

[•SleepyOverlord]

Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred.  

Runda 10, cu limite mult mai mici.

Da, dar problema era cam aceeasi ca la GInfo n-au pus limita pt K deci trebuia sa faci cat mai bine...

Banuiesc, ca ai vazut testele de la Ginfo... intra shi cu n^2*m^2 pt fiecare query...

[•Matrix]

hhyhyhy  acuma dupa ce  ati vazut   textele , toti spune-ti ca a fost  tare usor , ca a fost un fleac,  da  lasati-o mai moale,  ca  "dupa razboi multi viteji se arata "  si " poate mor de gripa "        

" everything that has a begining has an end "

[cristi8]

hhyhyhy  acuma dupa ce  ati vazut   textele , toti spune-ti ca a fost  tare usor , ca a fost un fleac,  da  lasati-o mai moale,  ca  "dupa razboi multi viteji se arata "  si " poate mor de gripa "        

" everything that has a begining has an end "

n-am citit prea atent postul, dar pare amuzant  :lol:  :lol:

[•Cosmin]

Stai linistit .. pt cineva care vrea premiu la nationala chiar au fost lejere, mai ales ca ai avut posibilitatea sa vezi o problema similara la ginfo si alta similara intr-o carte clasica.