Fişierul intrare/ieşire:dragonball.in, dragonball.outSursăLot Mehedinți 2015 - Baraj 6 Seniori
AutorEugenie Daniel PosdarascuAdăugată deatatomirTatomir Alex atatomir
Timp execuţie pe test0.3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dragon Ball

Goku este pus într-o situaţie FĂRĂ PRECEDENT: trebuie să parcurgă o mlaştină de lungime L (mlaştina poate fi văzută ca un segment de lungime L pe axa OX). Goku, împreună cu prietenul lui, Krillin, trebuie să parcurgă mlaştina dintr-un capăt în celălalt (aceştia se află la poziţia 0 şi trebuie să ajungă la poziţia L). N scânduri se află la anumite poziţii distincte in mlaştină. Din moment ce Goku nu poate ajunge direct la destinaţie, acesta se va folosi de cele N scânduri si de saltul ţestoasei. Goku poate sa ajungă de la o scândură (situată la poziţia x) la o altă scândură (situată la poziţia y) dacă distanţa dintre cele 2 scânduri (adica y - x) este mai mică sau egală ca D ( D fiind abilitatea lui Goku de a sări). Krillin s-a facut util şi a adus T scânduri suplimentare (pe care le cară în spate). Să se determine abilitatea minimă D necesară ca Goku să ajungă din poziţia 0 in poziţia L, ştiind că acesta poate poziţiona cele T scânduri suplimentare cum vrea el.

Date de intrare

Pe prima linie a fişierului de intrare dragonball.in se vor afla un număr natural N, un număr natural T şi un număr natural natural L. Pe următoarele N linii vor fi cele N numere naturale reprezentând cele N pozitii ale scândurilor.

Date de ieşire

În fişierul de ieşire dragonball.out se va afişa abilitatea minimă D necesară pentru ca Goku să ajungă dintr-un capăt al mlaştinii în celălalt.

Restricţii

  • 1 ≤ N, T ≤ 1 000
  • 1 ≤ L ≤ 1010 000
  • Pentru 20% din teste L ≤ 109
  • Pentru 40% din teste L ≤ 1050
  • Poziţiile celor N scânduri sunt distincte, sortate crescător şi fac parte din intervalul [1, L – 1].
  • Krillin îl urmăreşte tot timpul pe Goku.

Exemplu

dragonball.indragonball.out
5 5 100
10
13
50
69
88
12
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?