== include(page="template/taskheader" task_id="log") ==
Poveste si cerinta...
Fie expresia:
$log{~a{~1~}~}b{~1~}{@*@}log{~a{~2~}~}b{~2~}{@*@}...{@*@}log{~a{~n~}~}b{~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{~1~}$ unitati de timp;
* Reducere = inlocuirea expresiei {$log{~a~}b*log{~b~}c$} cu {$log{~a~}c$} in {$t{~2~}$} unitati de timp;
* Calcul = calculul unui logaritm, rezultatul fiind un numar real; pentru a calcula $log{~a~}b$ ii sunt necesare {$t{~3~}*(a-b)^2^$} unitati de timp.
h2. Cerinta
Sa se determine timpul minim pentru a calcula o expresie data.
h2. 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{~1~}$} {$t{~2~}$} {$t{~3~}$} 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.
h2. Date de iesire
...
Fisierul $log.out$ va contine o singura valoare reprezentand numarul de unitati de timp necesare evaluarii expresiei.
h2. Restrictii
* $... ≤ ... ≤ ...$
* Pentru $70%$ din teste {$1 ≤ n ≤ 500$}; pentru celelalte $30%$ din teste {$n ≤ 10 000$};
* {$1 ≤ a{~i~},b{~i~} ≤ 100$}
* {$1 ≤ t{~1~},t{~2~},t{~3~} ≤ 100$}
* Factorii expresiei initiale sau ai oricareia dintre expresiile rezultate pe parcursul evaluarii NU pot fi comutati intre ei.
h2. Exemplu
table(example). |_. log.in |_. log.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
2 1 3
2 3
3 4
4 5
| 13
|
| 4
2 1 2
2 2
3 4
4 4
4 5
| 9
|
h3. Explicatie
...
# 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.
# 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.
== include(page="template/taskfooter" task_id="log") ==
== SmfTopic(topic_id="...") ==
