Solutii probleme OJI 2010 – liceu
1In urma cu cateva zile s-a terminat si runda de calificari a olimpiadei judetene de informatica. Dupa aceasta runda are loc batalia intre creierele informaticii din Romania la Constanta, in vacanta de Pasti. Pentru cei care sunt curiosi de problemele care au fost propuse, mai jos veti avea solutiile la o parte dintre acestea : clasele a 9a(problema numar si livada) si a 10a (problema text si expozitie).
Clasa a 9a OJI 2010
1. Problema numar.
Aplicatie a numerelor mari si practic observatie pentru CMMDC. Problema se reduce la a determina CMMDC intre numarul mare „fara” punctul ce delimiteaza partea intreaga de cea zecimala si numarul mare format din valoarea 1 urmata de atatea zerouri cate are partea zecimala. S-ar putea folosi CMMDC pe numere mari pentru a face asta, dar din moment ce singura sansa ca al doilea numar sa se reduca este sa se divida la 2 si 5, nu ne ramane decat sa facem implementare pe numere mari pentru impartirea unui numar mare la un numar mic. 🙂
Solutia facuta de mine se foloseste de listele din STL pentru a implementa eficient numerele mari. Am ales sa folosesc aceasta structura deoarece ofera o dinamica mult mai mare ca restul structurilor existente. 🙂
2. Problema livada.
Problema livada nu este decat o aplicatie a vectorilor si a determinarii unor maxime. Ambele cerinte se pot face in timp liniar, folosindu-ne de aceeasi idee (comparand V[i] cu V[i-1] si pastrarea unui contor pentru egalitati), cea de-a doua avand nevoie de o sortare initiala.
Solutia mea are implementata sortarea din libraria STL. 🙂
Clasa a 10a OJI 2010
1. Problema text.
Problema joc reprezinta o aplicatie a programarii dinamica pe siruri de caractere. Initial se memoreaza si se numara cuvintele din intreg textul. Se va calcula pentru fiecare, folosind dinamica lungimea maxima unui subsir, determinandu-se la sfarsit valoarea maxima dintre lungimile calculate. Pentru a reconstitui solutia vom avea nevoie de un vector de legaturi.
Solutia abordata de mine incearca determinarea pentru fiecare litera in parte, lungimea maxima a unui subsir care se termine cu litera respectiva pe ultima pozitie din acel subsir. Implementarea duce la un algoritm liniar.
2. Problema expozitie.
O aplicatie a programarii dinamice si a combinatoricii. Datorita dimensiunii lui n si d din enunt, problema devine si o aplicatie a numerelor mari.
Eliminam initial din n scandurile pe care se afiseaza cate k desene de acelasi tip (k*d). Asadar, daca noul n este egal cu 0 avem un singur mod de aranjare. Daca noul n < 0 atunci nu avem nici un mod de aranjare (solutia este 0). In caz contrar determinam Comb(n-d*k,d-1), folosind triunghiul lui Pascal si operatii cu numere mari. Nu ne ramane decat sa implementam adunarea pe numere mari.
Si de aceasta data, solutia implementata de mine foloseste listele din STL.
Clasele 11-12 OJI 2010
1. Problema joc.
De completat.
2. Problema immortal.
De completat.
Daca ati reusit sa veniti cu solutii mai interesante sau doriti sa completati lista cu ultimile probleme ramase va rog lasati un comentariu valid (sa contina adresa de e-mail) si va voi contacta pe aceasta. Articolul va suferi modificari imediat ce vor fi necesare completarile.
Salut! Am vizualizat rezolvarea problemei text de la a 10a si am o rugaminte. Eu nu prea am lucrat cu stdio pana acum si, te rog, daca poti sa imi dai o varianta folosind fstream pt citirea din while-ul de mai jos:
void read(){
int LN=0;
char c;
freopen("text3.in","r",stdin);
freopen("text3.out","w",stdout);
while(scanf("%c",&c)!=-1)
{
......
}
}
Multumesc anticipat!
//scuze pt erorile de redactare 🙂