Fişierul intrare/ieşire:	telefon3.in, telefon3.out	Sursă	ONI 2019, clasa a 9-a, ziua 2
Autor	Alexandru Turdean	Adăugată de	Pop Alex-Nicolae •AlexPop28
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Telefon3

Dorel, plictisit de puzzle-ul pe care l-a upgradat ieri, a decis să meargă afară cu ceilalţi copii. El îi priveşte pe cei N copii cum joacă “telefonul fără fir”.
Jocul decurge în felul următor:

• Iniţial, copiii se aşază pe axa Ox, copilul i la distanţa X_i metri faţă de origine.
• Copilul cel mai aproape de origine alege un cuvânt secret şi îl transmite celui din dreapta lui; cel din dreapta lui îl transmite următorului şi aşa mai departe până se ajunge la ultimul copil.

Pentru a transmite cuvântul, fiecare copil trebuie să meargă până la copilul din dreapta lui. Toţi copiii se deplasează cu viteza constantă de 1 metru/secundă.

Cu toate acestea, pentru a evita deplasarea fiecare copil dispune de un dispozitiv de tip walkie-talkie ce permite transmiterea unui cuvânt mai departe. Toate staţiile walkie-talkie au o rază de acţiune R, setată la începutul unei runde de joc (exprimată în metri) ce nu poate fi modificată pe parcursul jocului. Staţiile sunt conectate la aceeaşi sursă de alimentare care are B unităţi de energie.

În funcţie de raza de acţiune setată, copiii pot sau nu să folosească sistemul walkie-talkie pentru a nu se mai deplasa. Mai exact, dacă un copil ar trebui să parcurgă o distanţă mai mică sau egală cu R ca să transmită cuvântul celui din dreapta sa şi bateria sursei are cel puţin R unităţi de energie rămase, acesta poate folosi sistemul walkie-talkie ca să transmită instantaneu cuvântul secret, iar bateria se va descărca cu R unităţi de energie. Cu toate acestea, chiar şi cu sistemul walkie-talkie, un copil nu are voie să
transmită mesajul decât primului copil situat în dreapta lui.

Copiii doresc ca jocul să se termine cât mai repede, aşa că vor seta o rază de acţiune convenabilă şi vor alege să folosească sau nu sistemul walkie-talkie, pentru a minimiza timpul necesar ca toţi cei N copii să afle cuvântul secret.

Dorel doreşte să se alăture jocului, aşa că în a doua parte a jocului va intra şi el în rând. Dorel se va aşeza pe axa Ox, undeva între primul şi ultimul copil, la o anumită distanţă de origine unde nu se află un alt copil

Cerinţe

1. Care este durata minimă a jocului, dacă Dorel nu ia parte la joc?
2. Care este durata minimă a jocului, dacă Dorel ia parte la joc şi se poziţionează în mod optim
   pentru a minimiza durata jocului?

Date de intrare

Fişierul de intrare telefon3.in conţine pe prima linie două numere naturale N şi B cu semnificaţia din enunţ. Pe cea de-a doua linie se află N numere naturale nenule distincte X_i, în ordine strict crescătoare, unde X_i reprezintă distanţa copilului i faţă de origine, 1 ≤ i ≤ N.

Date de ieşire

Fişierul de ieşire telefon3.out va conţine două numere naturale C1 C2, separate printr-un spaţiu, unde C1 reprezintă răspunsul la cerinţa 1 iar C2 răspunsul la cerinţa 2.

Restricţii

• 2 ≤ N ≤ 10⁵
• 1 ≤ B ≤ 10⁹, 1 ≤ X_i ≤ 10⁹
• Se garantează că Dorel are cel puţin o poziţie liberă pe care se poate aşeza
• Un copil poate alege între a se deplasa sau a folosi walkie-talkie pentru a transmite un mesaj
• Copiii pot seta o noua rază de acţiune a walkie-talkie când Dorel intră în joc
• Pentru prima cerinţă se acordă 40 puncte
• Pentru a doua cerinţă se acordă 60 puncte
• Pentru teste în valoare de 15 puncte N, B ≤ 10²
• Pentru alte teste în valoare de 35 puncte N ≤ 10³, B ≤ 10⁴
• Pentru alte teste în valoare de 20 puncte N ≤ 10⁵, B ≤ 10⁵
• Pentru alte teste în valoare de 30 puncte N ≤ 10⁵, B ≤ 10⁹

Exemplu

Explicaţie

N=6, B=15
X_[1-6]=[7,9,12,16,21,27]

1. Dacă Dorel nu participă la joc atunci copiii vor alege raza de acţiune R=5 şi al 2-lea, al 3-lea şi al 4-lea copil vor folosi sistemul de comunicare. În consecinţă durata jocului va fi (9-7)+(27-21)= 2+6 = 8
2. Dacă Dorel participă la joc se va poziţiona la distanţa 26 faţă de origine. În această situaţie copiii vor alege raza de acţiune R tot 5 şi al 3-lea, al 4-lea şi al 5-lea copil vor folosi sistemul de comunicare. În consecinţă durata jocului va fi
   (9-7)+(12-9)+(27-26) = 2+3+1 = 6

Cum se trimit solutii?