Algoritmų sudėtingumas

Pradinių duomenų failas:
alg.in  
Rezultatų failas:
alg.out  
Laiko apribojimas:
1 s.  
Atminties apribojimas:
16 Mb.  

Užduotis

Algoritmo sudėtingumu vadiname reikalingų resursų kiekio priklausomybę nuo pradinių duomenų dydžio. Resursai gali būti laikas arba atmintis, ar dar kas nors, ko atžvilgiu kalbame apie sudėtingumą, tačiau toliau paprastumo dėlei kalbėsime apie laiką.

Pradiniai duomenys dažniausiai apibūdinami kokiais nors kintamaisiais, pavyzdžiui, N dėžių, M kėdžių, K kelių, ir taip toliau. Jei algoritmo veikimo laikas priklauso nuo kažkokių kintamųjų, tai to algoritmo sudėtingumas yra minėtų kintamųjų funkcija. Algoritmo sudėtingumui aprašyti naudojamas O-žymėjimas: parašymas O(f) reiškia, kad algoritmo veikimo laikas didėjant pradiniams duomenims auga negreičiau negu funkcija f.

 

Šiame uždavinyje nagrinėsime labai paprastas funkcijas f – tik tokias, kuriose kiekvienas kintamasis įeina kaip atskiras dėmuo, galbūt pakeltas kokiu nors laipsniu (konstanta). Algoritmus, kurių sudėtingumai yra tokio pavidalo funkcijos, lengva palyginti tarpusavyje.

Tarkime, yra trys skirtingi algoritmai A, B ir C tam pačiam uždaviniui spręsti, kurių sudėtingumai, atitinkamai:

  1. O(N + M)
  2. O(\(N^{2}\))
  3. O(\(N^{2}\) + M)

Algoritmas A yra geresnis už algoritmą C, kadangi veikimo laikas kintamojo N atžvilgiu auga lėčiau, o M atžvilgiu – taip pat kaip algoritmo C. Dėl tos pačios priežasties ir algoritmas B yra geresnis už algoritmą C. Algoritmai A ir B tarpusavyje yra nepalyginami: kintamojo N atžvilgiu greitesnis yra A, o kintamojo M atžvilgiu – B algoritmas.

Parašykite programą, kuri pagal duotus algoritmų sudėtingumus nustatytų, kuris algoritmas yra geriausias, arba kad tokio nėra.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas algoritmų skaičius N (1 <= N <= 100). Sekančiose N eilučių pateikiami algoritmų sudėtingumai O-žymėjimu, po vieną eilutėje. Galimi kintamieji yra didžiosios lotyniškos raidės. Kėlimas laipsniu žymimas X^d, kur d – sveikas skaičius tarp 2 ir 9 imtinai. Visi + simboliai iš abiejų pusių atskirti vienu tarpo simboliu. Daugiau tarpo simbolių eilutėje nėra. Nei vienas kintamasis du kartus į tą patį reiškinį neįeina. Suma gali būti ir tuščia – O() – tai reiškia, kad algoritmas visai nepriklauso nuo pradinių duomenų dydžio ir veikia per konstantinį laiką.

Rezultatai

Jei kuris nors (i-asis) algoritmas yra geresnis už visus kitus, į rezultatų failą jūsų programa turi išvesti eilutę „:) – i“. Priešingu atveju, programa turi išvesti eilutę „:(“. Nepamirškite eilutės pabaigos simbolio!

Pavyzdžiai

Pradiniai duomenys Rezultatai 
3
O(N + M)
O(N^2)
O(N^2 + M)
 
:(
 
3
O(N + M)
O(N^2 + M^3)
O(N^2 + M)
 
:) - 1
 
2
O(A)
O(B)
 
:(