Un calculator trebuie să evalueze această expresie aducând-o la forma unui singur număr real. Pentru aceasta, el poate face următoarele calcule:
- Produs = produsul a doua numere reale în t1 unităţi de timp;
- Reducere = înlocuirea expresiei logxy*logyz cu logxz în t2 unităţi de timp;
- Calcul = calculul unui logaritm, rezultatul fiind un număr real; pentru a calcula logab îi sunt necesare t3*(a-b)2 unităţi de timp.
Cerinţă
Să se determine timpul minim pentru a calcula o expresie dată.
Date de intrare
Fişierul de intrare log.in conţine:
- pe prima linie o valoare numerică naturală n cu semnificaţia din enunţ;
- pe a doua linie trei valori numerice naturale t1 t2 t3 separate prin câte un spaţiu, cu semnificaţia din enunţ;
- pe fiecare din următoarele n linii câte două valori numerice naturale ai bi cu semnificaţiile din enunţ.
Date de ieşire
Fişierul de ieşire log.out va conţine o singură valoare reprezentând numărul de unităţi de timp necesare evaluării expresiei.
Restricţii
Pentru 70% din teste 0 < n ≤ 500; pentru celelalte 30% din teste n ≤ 10000; 1 < ai,bi < 100
1 ≤ t1,t2,t3 ≤ 100
Factorii expresiei iniţiale sau ai oricăreia dintre expresiile rezultate pe parcursul evaluării NU pot fi comutaţi între ei.
Exemple
log.in
log.out
Explicaţii
3
2 1 3
2 3
3 4
4 5
13
Se calculează fiecare din cei trei logaritmi, rezultă trei numere, fiecare calcul necesită 3 unităţi de timp; se înmulţesc primele două numere în 2 unităţi de timp, apoi rezultatul se înmulţeşte cu al treilea număr tot în 2 unităţi; în total: 3+3+3+2+2=13 unităţi.
4
2 1 2
2 2
3 4
4 4
4 5
9
Primul logaritm se calculează în 0 unităţi; al doilea şi al treilea se reduc la un logaritm în 1 unitate iar acest logaritm se calculează în 2 unităţi; al patrulea se calculează în 2 unităţi; au rezultat trei numere, care pot fi aduse la unul singur prin două înmulţiri, fiind necesare 1+2+2+2+2=9 unităţi de timp.