Alex are de rezolvat un exercitiu si poate apela, contra cost, la N modele IA. Modelul i rezolva exercitiul cu probabilitatea p_i% (independent de celelalte) si costa c_i lei pentru o incercare. Alex plateste costul de fiecare data cand cere unui model sa incerce, indiferent de rezultat. Daca modelul reuseste, Alex se opreste; daca nu reuseste, poate incerca urmatorul model, in orice ordine alege, dar niciodata acelasi model de doua ori.
Se garanteaza ca cel putin unul dintre modele are probabilitate de succes 100%, deci procesul se termina mereu.
Cerinta: determinati costul mediu minim pe care il plateste Alex, alegand ordinea optima de incercare a modelelor. Raspunsul se afiseaza ca fractie ireductibila p/q.
- Date de intrare
- Pe prima linie: N. Urmeaza N linii, fiecare continand costul c_i (lei) si probabilitatea p_i (numar intreg intre 1 si 100, reprezentand procente) a modelului i.
- Date de iesire
- Se afiseaza costul mediu minim, ca fractie ireductibila p/q.
- Restrictii
- 2 <= N <= 6 1 <= c_i <= 100 1 <= p_i <= 100 cel putin un model are p_i = 100
Exemple
Exemplul 1
Intrare
5 4 30 10 40 15 70 20 80 25 100
Iesire
79/4
Exemplul 2
Intrare
3 5 50 10 100 3 20
Iesire
10/1