Fişierul intrare/ieşire:log.in, log.outSursăONI 2007, clasele 11-12
AutorStelian CiureaAdăugată detheodor.moroianuTheodor Moroianu theodor.moroianu
Timp execuţie pe test0.8 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Log

Fie expresia:

loga1b1*loga2b2*...*loganbn

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 t1 unitati de timp;
  • Reducere = inlocuirea expresiei logab*logbc cu logac in t2 unitati de timp;
  • Calcul = calculul unui logaritm, rezultatul fiind un numar real; pentru a calcula logab ii sunt necesare t3*(a-b)2 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 t1 t2 t3 separate prin cate un spatiu, cu semnificatia din enunt;
  • pe fiecare din urmatoarele n linii cate doua valori numerice naturale ai bi 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;
  • 1 ≤ ai,bi ≤ 100
  • 1 ≤ t1,t2,t3 ≤ 100
  • Factorii expresiei initiale sau ai oricareia dintre expresiile rezultate pe parcursul evaluarii NU pot fi comutati intre ei.

Exemplu

log.inlog.out
3
2 1 3
2 3
3 4
4 5
13
4
2 1 2
2 2
3 4
4 4
4 5
9

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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content