Fişierul intrare/ieşire:	log.in, log.out	Sursă	ONI 2007, clasele 11-12
Autor	Stelian Ciurea	Adăugată de	Theodor Moroianu •theodor.moroianu
Timp execuţie pe test	0.4 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Log

Fie expresia:

log_a1b₁*log_a2b₂*...*log_anb_n

Un calculator trebuie sa evalueze aceasta expresie aducand-o la forma unui singur numar real. Pentru aceasta, el poate face urmatoarele calcule:

• Produs = produsul a doua numere reale in t₁ unitati de timp;
• Reducere = inlocuirea expresiei log_ab*log_bc cu log_ac in t₂ unitati de timp;
• Calcul = calculul unui logaritm, rezultatul fiind un numar real; pentru a calcula log_ab ii sunt necesare t₃*(a-b)² unitati de timp.

Cerinta

Sa se determine timpul minim pentru a calcula o expresie data.

Date de intrare

Fisierul log.in contine:

• pe prima linie o valoare numerica naturala n cu semnificatia din enunt;
• pe a doua linie trei valori numerice naturale t₁ t₂ t₃ separate prin cate un spatiu, cu semnificatia din enunt;
• pe fiecare din urmatoarele n linii cate doua valori numerice naturale a_i b_i cu semnificatiile din enunt.

Date de iesire

Fisierul log.out va contine o singura valoare reprezentand numarul de unitati de timp necesare evaluarii expresiei.

Restrictii

• Pentru 70% din teste 1 ≤ n ≤ 500; pentru celelalte 30% din teste n ≤ 10 000;
• 2 ≤ a_i,b_i ≤ 100
• 1 ≤ t₁,t₂,t₃ ≤ 100
• Factorii expresiei initiale sau ai oricareia dintre expresiile rezultate pe parcursul evaluarii NU pot fi comutati intre ei.

Exemplu

Explicatie

1. Se calculeaza fiecare din cei trei logaritmi, rezulta trei numere, fiecare calcul necesita 3 unitati de timp; se inmultesc primele doua numere in 2 unitati de timp, apoi rezultatul se inmulteste cu al treilea numar tot in 2 unitati; in total: 3+3+3+2+2=13 unitati.
2. Primul logaritm se calculeaza in 0 unitati; al doilea si al treilea se reduc la un logaritm in 1 unitate iar acest logaritm se calculeaza in 2 unitati; al patrulea se calculeaza in 2 unitati; au rezultat trei numere, care pot fi aduse la unul singur prin doua inmultiri, fiind necesare 1+2+2+2+2=9 unitati de timp.

Cum se trimit solutii?