Diferente pentru problema/rollercoaster intre reviziile #4 si #32

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="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].
În vacanţa de vară, Phineas şi Ferb vor să construiască un roller-coaster. În oraşul Danville se 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)
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.
Este bine cunoscut faptul că o pistă care uneşte un turn cu înălţimea $A$ de un turn cu înălţimea $B$ are coeficientul de distracţie $cmmdc(A, B)$. 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?
!{width: 300px; float: right; margin: 10px}problema/rollercoaster?roller-coaster.jpg!
 
h2. 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.
În fişierul de intrare rollercoaster.in se află $N$, numărul de turnuri, iar pe linia a doua se află cele $N$ numere naturale nenule.
h2. Date de ieşire
În fişierul de ieşire $rollercoaster.out$ ...
În fişierul de ieşire rollercoaster.out se vor afla $2$ numere, reprezentând coeficientul maxim de distracţie ce poate fi obţinut de Marcel, precum şi numărul de roller-coastere prin care se obţine **modulo $1.000.000.007$**.
 
h2. Restricţii si precizari
h2. Restricţii si precizări
* 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
* $N ≤ 250.000$
* $H{~i~} ≤ 250.000, 1 ≤ i ≤ N$
* **i{~1~} < i{~2~} < ... < i{~k~}**
* $cmmdc(A, B)$ este cel mai mare divizor comun al lui $A$ si $B$
* *$Subtaskul 1 (20 de puncte):$* $N ≤ 15$
* *$Subtaskul 2 (20 de puncte):$* $N ≤ 1000$
* *$Subtaskul 3 (60 de puncte):$* restricţiile iniţiale
* **Numarul de roller-coastere trebuie afisat modulo 1.000.000.007**
h2. Exemplu
table(example). |_. rollercoaster.in |_. rollercoaster.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 7
4 25 19 25 28 20 9
| 32 2
|
h3. Explicaţie
...
Putem lua $R = {1, 2, 4, 6, 7}$ sau $R = {1, 2, 4, 5, 6, 7}$.
 
*Soluţia 1:*
Daca alegem $R = {1, 2, 4, 6, 7}$ coeficientul de distractie total va fi:
$cmmdc(H{~1~}, H{~2~}) + cmmdc(H{~2~}, H{~4~}) + cmmdc(H{~4~}, H{~6~}) + cmmdc(H{~6~}, H{~7~}) = 1 + 25 + 5 + 1 = 32$
 
*Soluţia 2:*
Daca alegem $R = {1, 2, 4, 5, 6, 7}$ coeficientul de distractie total va fi:
$cmmdc(H{~1~}, H{~2~}) + cmmdc(H{~2~}, H{~4~}) + cmmdc(H{~4~}, H{~5~}) + cmmdc(H{~5~}, H{~6~}) + cmmdc(H{~6~}, H{~7~}) = 1 + 25 + 1 + 4 + 1 = 32$
 
== include(page="template/taskfooter" task_id="rollercoaster") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.