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
In rollercoaster.in se afla N, numarul de turnuri, iar pe linia a doua se afla cele N numere naturale nenule.
Date de ieşire
În rollercoaster.out se vor afla 2 numere, reprezentand suma maxima pe care o poate obtine Marcel insumand cei mai mari divizori comuni numerelor aflate pe pozitii consecutive in subsirul ales, cat si restul impartirii numarului de subsiruri optime la 10^9+7.
Restricţii si precizari
- Un subsir al sirului de numere de pe f oaie este un sir pe care il putem obtine inlaturand cateva numere din sirul mare.
- N<=250.000
- numerele din sir <=250.000
- pentru 20% din punctaj, N<=15
- pentru 40% din punctaj, N<=1000
Exemplu
| rollercoaster.in | rollercoaster.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
