infoarena

Ce ati facut la locala ? Cum vi s-au parut problemele ? Bagati mare, s-auzim si noi :)

In Bucuresti... a fost super aiurea. Prima problema a fost pur si simplu penibila, o dinamica implementabila in 5 minute... pe care au facut-o cam toti. Si a doua a fost cu 3 cerinte (din care a 3-a s-a anulat), cam muncitoreasca. ;)

Per ansamblu... jeg! :D

Clasa dude ?

Eu am fost la clasele 11-12.  8)

Prima problema era asa: aveai o matrice in care erau numere intre 0 si 300 si trebuia mers de pe prima pe ultima linie, putandu-se trece la un moment dat numai pe linia imediat urmatoare, pe aceeasi coloana, sau in diagonala.

Trebuia afisata suma maxima si un drum.

Asta e pb. de 11-12?  :shock:

Lol.. daca e asa cum spui tu.. nu e de 11-12 !

E exact asa cum spun eu... iar problema a doua era cam asa:

In nu stiu ce ocean erau niste insule si niste locuri pe acele insule. Se dadeau lungimile drumurilor dintre locuri, locurile in care se putea debarca, locurile in care erau canibali si locurile in care erau comori.

In prima faza trebuiau afisate: numarul de insule, numarul de locuri din fiecare insula, locurile din fiecare insula... insulele tr. sortate descrescator in ordinea nr. de locuri si in caz de egalitate crescator lexicografic dupa locuri. La punctul b) trebuia spus care comori pot fi recuperate tinand cont ca nu se putea trece pe unde erau canibali si nici pe muchiile care apartin unui drum minim intre 2 locuri de canibali. Punctul c), care a fost anulat deoarece era prea neclar cerea sa se spuna in care dintre insule am fi fost mancati de canibali daca am fi incercat sa mergem "pe drumul minim de la orice loc de debarcare la locul comorilor (pentru fiecare comoara: cel mai scurt drum dintre drumurile minime de la fiecare loc de debarcare la comoara)" [am incheiat citatul].

Punctul a) avea 50% din punctaj, punctul b) 40% iar punctul c) 10%. Mie mi se pare total tampita si inutila aceasta problema... am scris 200 de randuri numai la punctele a) si b) si am avut 4 randuri de variabile.  :shock:

Jeg!  :roll:

cls: a X-a
Eu am luat 190/200 (un test cu 0 ratat), si mi s-au parut foarte simple!
Din 3 ore, dupa o ora jumate le facusem, le testatsem, nu mai aveam idei ce sa fac ca sa fiu sigur ca merg...

That's cul! Bravo Vali!

Am aflat rezultatele de aseara dar nu te-am gasit sa te felicit (telu tau era inchis cand am vrut sa te sun).

Silviu

PS: "Si la mai mare!"

Zi si tu problemele de la a 10-a (pe scurt), Vali. Sunt curios. :)

subiectele pe scurt:
Problema 1 (Vector):
ai un robot, care are 3 registrii (A,B,C)
singurele operatii care poate sa le facea sunt:
- cod J - injumatatirea valorii din A
- cod D - dublarea valorii din B
- cod A - adauga B in C
citesti din fisier A si B (nr maxim 50 de cifre), iar C e 0 initial
sa afisezi o secventa de operatii (J, D sau A), a.i. in C sa se gaseasca produsul nr initiale (ce ai citit in A si ce ai citit in B); secventa nu trebuie sa aiba mai mult de 1000 de caractere!
ex:
in:
2 -> lungimea nr din registru A
12 -> nr din registru A
1 -> lungimea nr din registrul B
9 -> nr din registrul B

out:
JDDJAJDA -> secventa de operatii
108 -> produsul nr

atentie la testul cand in A se da valoarea 0 (toata lumea, inclusiv eu, la ratat pe asta) ;)

Problema 2 (Garfield)
exista o strada cu n case; cele cu nr pare se afla pe o parte, cele cu nr impare se afla pe cealalta parte a strazii
se citeste din fisier n,t si n valori (a=nr de prajituri care le primeste daca viziteaza casa i)
t reprezinta EXACT de cate ori vrea sa treaca strada motanul
initial poate sa inceapa de pe ce parte vrea si poate termina pe ce parte vrea, dar intodeauna merge inainte (in ordine crescatoare a nr caselor)
sa se afseze nr maxim de prajituri care le poate manca Garfield, trecand de exact t ori strada si ce case a vizitat
ex:
in
6 1 -> n si t
7 5 3 8 9 6 -> casa 1 ii da 7 prajituri daca trece pe acolo, casa 2 ii da 5 si tot asa..

out:
26 -> nr maxim de prajituri care le poate obtine
1 2 4 6 -> casele pe care le viziteaza

explicatie: a vizitat casa 1, apoi a trecut strada si a vizitat casele 2, 4 si 6

LIMITE:
0<=T<N<=100
1<=a<=10.000.000, (nr de prajituri pentru casa i)

am mai taiat din ele, ca sa le fac mai mici; sper ca intelegeti voi...

ok. dar nu inteleg un lucru la problema 1: la C se poate adauga doar B si la final conteaza doar ce e in C. De ce mai e nevoie sa injumatatesti A-u, atat timp cat ce e in A nu se adauga in B sau in C?  :roll:
Secventa putea sa fie doar DDADA

da, ai dreptate, nu trebuie sa afisiezi neaparat J, asta e asa, mai mult de forma (eventual ca sa-ti dai seama cum merge algoritmul)

cand e OJI ?

Olimpiada de Informatica, faza judeteana va avea loc pe data de 26-27 februarie 2005. Pe 26 februarie clasele 5, 6, 9 si 10 iar pe 27 februarie clasele 11, 12, 7 si 8. Asta scrie la "stiri".

Primii cati se califica de la faza judeteana(Bucuresti)?

Vreo 30-31

Io vreau sa stiu cati se califica de a 12 pe faza urm(adik tara).
 Tu probabil ai spus totalul de elevi de liceu. Poate sa-mi dea cineva un raspuns mai in amanuntime.

Vali, stiu ca probabil sunt retardat dar, cum se rezolvau problemele de la voi d la locala , mai ales ca am avut una asemanatore cu "Garfield" la USACO si nici acolo n-am facut-o ??? Zi-mi ideea ca d-acolo ma descurc eu (Sper :P)

MS

iti zic dupa pre-oni2, asteapta putin...

Aia cu robotelul : trebuia sa descompui A in suma de puteri ale lui 2, shi sa scrii pentru fiecare putere din suma, 'D' de exponent ori +'A'in ordine crescatoare a exponentilor NU ? (cam nasol de implementat pe un vector)

La 'Garfield' as asocia un cost fiecarei case shi sa determin drumul de cost maxim, problema este ca nu shtiu cand sa 'trec strada' (daca incerc toate pos ib. => back shi nu ash rezolva nimik).

MS fain !!!

Scuze de intarziere...

Te complici prea mult!

Uite rezolvarile mele:
la aia cu Robotul pur si simplu imparteai A la 2 si dublai B, iar daca restul impartirii era 1, atunci si adaugai ce e in B in C! Desigur asta se reduce la ce ai zis tu, doar ca asta implementezi in maxim 30min

La Garfield este tot o chestie simpla: se rezolva cu programare dinamica.
Tii minte in vectorul D, in elem D[j] numarul maxim de prajituri cu care poti sa ajungi in casa i, cu j traversari.
Daca mai tin bine minte, D[j]=max(D[i-2][j]+C, D[i-1][j-1]+C), unde C este numarul de prajituri oferite daca vizitezi casa i
Raspunsul e valoarea maxima de pe D[k][T], cu k de la 1 la N. (N=nr de case, T=nr de traversari)
Iar reconstituirea se face pornind de la valoarea maxima gasita mai sus si verificand care dintre elem D[i-2][j] sau D[i-1][j-1] este egala cu D[j]-C. Apoi se reia, pana cand ajungi la D[j]=0 (sau D[j]=C). Astfel vei obtine ordinea inversa a caselor parcurse de Garfield!