Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rollercoaster.in, rollercoaster.out | Sursă | Junior Challenge 2021 |
| Autor | Alexandru Petrescu, Stefan Constantin-Buliga | Adăugată de |  Comisia •jc2021 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Rollercoaster
În vacanţa de vară, Phineas şi Ferb vor să construiască un roller-coaster. În oraşul Danville de află N turnuri în linie dreaptă. Cel de-al i-lea turn de la stânga la dreapta are înălţimea h[i].
Un roller-coaster este format dintr-o submulţime R = {i_1, i_2, ... i_k} din cele N turnuri şi pistele de roller-coaster care vor fi construite între perechile de turnuri (i_1,i_2), (i_2,i_3), ..., (i_k-1, i_k)
Este bine cunoscut faptul că o pistă care uneşte un turn cu înălţimea h_1 de un turn cu înălţimea h_2 are coeficientul de distracţie cmmdc(h_1,h_2). Coeficientul de distracţie al unui roller-coaster este egal cu suma coeficienţilor pistelor care îl alcătuiesc.
Marcel a promis că îi ajută pe Phineas şi Ferb să îşi pună planul în aplicare cu speranţa de a apărea şi el într-un episod.
Care este coeficientul maxim de distracţie ce poate fi obţinut şi pentru câte roller-coastere se obţine?
Date de intrare
Fişierul de intrare rollercoaster.in contine N, numarul de turnuri, iar pe linia a doua se afla cele N numere naturale nenule.
Date de ieşire
În fişierul de ieşire rollercoaster.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| rollercoaster.in | rollercoaster.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
