Fișierul intrare/ieșire	deedee.in, deedee.out	Sursă	Olimpiada locala 2012, Clasele 11-12
Autor	Carmen Mincă	Adăugată de	Ioana Bica • ioanab
Timp de execuție pe test	0.5 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Deedee

Deedee a descoperit în parc un șotron triunghiular construit din n*(n+1)/2 dale de piatră dintre care n au culoarea gri iar restul sunt albe. Dalele sunt numerotate cu numerele distincte de la 1 la și sunt dispuse pe n rânduri, una lângă alta:

• pe rândul 1, dala cu numărul 1
• pe rândul 2, dalele cu numerele: 2 și 3
• pe rândul 3, dalele cu numerele: 4, 5 și 6
  ..............
• pe rândul n, dalele cu numerele: n*(n-2)/2+1, n*(n-1)/2+2,....., n(n+1)/2

Pornind de pe dala inițială, adică dala cu numărul 1, sărind din dală în dală, Deedee trebuie să ajungă pe dala finală, adică dala cu numărul n*(n+1)/2, respectând regula următoare: de pe dala curentă, numerotată cu X și situată pe rândul Y, ea poate să sară doar pe o dală albă situată pe rândul Y și numerotată cu X + 1 (dacă aceasta există) sau pe rândul Y + 1 pe aceeași coloană cu dala curentă.

Nefiind o bună sportivă, Deedee vrea să descopere mai întâi dalele pe care ar trebui să sară pornind de la dala inițială astfel încât să execute un număr minim de sărituri până la dala finală, respectând la fiecare săritură regula.

Cerinta

Scrieți un program care să determine:

• a) numărul R al rândului care conține cele mai multe dale gri, iar dacă sunt mai multe rânduri cu această proprietate atunci R va fi egal cu numărul cel mai mic al unui astfel de rând;
• b) numărul minim D de dale pe care trebuie să sară Deedee pornind de la dala inițială astfel încât să ajungă pe dala finală, respectând la fiecare săritură regula din enunț.

Date de intrare

Fișierul de intrare deedee.in conține pe prima linie cele două numere naturale N și K, separate printr-un spațiu, cu semnificația din enunț. A doua linie a fișierului conține K numere naturale nenule: g1, g2, ..., gK, separate prin câte un spațiu, reprezentând numerele dalelor de culoare gri din șotron.

Date de ieșire

Fișierul de ieșire deedee.out va conține pe prima linie numărul natural R, iar pe a doua linie va conține numărul natural D.

Restricții

• 3 ≤ n ≤ 100000
• 1 ≤ k ≤ 100000
• 2 < g1 < g2 < ... < gk < n*(n+1)/2
• Dalele au formă pătratică, cu latura de aceeași lungime
• Dala inițială și dala finală sunt de culoare albă
• Pentru datele de test există întotdeauna soluție

Exemplu

Explicație

Rândurile 3 și 6 au numărul maxim de dale gri (2), deci R = 3
Deedee poate ajunge pe dala finală efectuând minimum D = 10 sărituri. De exemplu, poate urma traseul: 1->2->3->5->8->9->13->14->15->20->21.