log

Time limit: 0.25s
Memory limit: 32MB
Input: log.in
Output: log.out

Fie expresia: loga1b1loga2b2loganbnlog_{a_1}b_1 \cdot log_{a_2}b_2 \cdot … \cdot log_{a_n}b_n

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 t1t_1 unităţi de timp;
  • Reducere = înlocuirea expresiei logablogbclog_ab \cdot log_bc cu logaclog_ac în t2t_2 unităţi de timp;
  • Calcul = calculul unui logaritm, rezultatul fiind un număr real; pentru a calcula logablog_ab îi sunt necesare t3(ab)2t_3 \cdot (a-b)^2 unităţi de timp.

Cerinţă

Să se determine timpul minim pentru a calcula o expresie dată.

Date de intrare

Fişierul 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 t1t2t3t_1 t_2 t_3 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 aibia_i b_i cu semnificaţiile din enunţ.

Date de ieşire

Fişierul log.out va contine o singură valoare reprezentând numărul de unităţi de timp necesare evaluării expresiei.

Restricţii şi precizări

  • Pentru 70% din teste 0 < n ≤ 500; pentru celelalte 30% din teste n ≤ 10000;
  • 1<ai,bi<1001 < a_i,b_i < 100
  • 1t1,t2,t31001 ≤ t_1,t_2,t_3 ≤ 100
  • Factorii expresiei iniţiale sau ai oricăreia dintre expresiile rezultate pe parcursul evaluării NU pot fi comutaţi între ei.

Exemplu

log.in

3		
2 1 3
2 3
3 4
4 5

log.out

13

Explicaţii

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.

log.in

4		
2 1 2
2 2
3 4
4 4
4 5

log.out

9

Explicaţii

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.

Problem info

ID: 156

Editor: liviu

Author:

Source: ONI 2007 XI-XII: Ziua 1 Problema 1

Tags:

ONI 2007 XI-XII

Log in or sign up to be able to send submissions!