Fişierul intrare/ieşire:rollercoaster.in, rollercoaster.outSursăJunior Challenge 2021
AutorAlexandru Petrescu, Stefan Constantin-BuligaAdăugată dejc2021Comisia jc2021
Timp execuţie pe test1.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Rollercoaster

Î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 Hi.

Un roller-coaster este format dintr-o submulţime R = {i1, i2, ..., ik} din cele N turnuri şi pistele de roller-coaster care vor fi construite între perechile de turnuri (i1, i2), (i2, i3), ..., (ik-1, ik)

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?

Date de intrare

Î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.

Date de ieşire

Î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.

Restricţii si precizări

  • N ≤ 250.000
  • Hi ≤ 250.000, 1 ≤ i ≤ N
  • i1 < i2 < ... < ik
  • 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

Exemplu

rollercoaster.inrollercoaster.out
7
4 25 19 25 28 20 9
32 2

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(H1, H2) + cmmdc(H2, H4) + cmmdc(H4, H6) + cmmdc(H6, H7) = 1 + 25 + 5 + 1 = 32

Soluţia 2:
Daca alegem R = {1, 2, 4, 5, 6, 7} coeficientul de distractie total va fi:
cmmdc(H1, H2) + cmmdc(H2, H4) + cmmdc(H4, H5) + cmmdc(H5, H6) + cmmdc(H6, H7) = 1 + 25 + 1 + 4 + 1 = 32

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?