Fişierul intrare/ieşire:oxificarelight.in, oxificarelight.outSursăAlgoritmiada 2017, Runda Finala, Juniors
AutorAndrei Popa, Radu MunteanAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.8 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Oxificare Light

In aceasta problema, trebuie sa amplasati N + 1 puncte pe axa numerelor reale, respectand anumite restrictii. Mai exact, vi se ofera un sir lungime, de N elemente. Punctele trebuie amplasate pe axa astfel incat:

- Distanta pe axa dintre punctul cu numarul i si punctul cu numarul i + 1 trebuie sa fie exact lungime[i].
- Distanta dintre cel mai din stanga punct amplasat si cel mai din dreapta punct amplasat trebuie sa fie minim posibila.

Date de intrare

Fişierul de intrare oxificarelight.in va contine pe prima sa linie numarul de teste, T. Structura unui test este urmatoarea:

Pe prima linie se afla numarul natural N.

Pe a doua linie se afla N numere naturale, reprezentand, in ordine, elementele sirului lungime.

Date de ieşire

În fişierul de ieşire oxificarelight.out se vor afla T valori: pentru fiecare test trebuie sa afisati distanta minim posibila dintre punctul cel mai din stanga si punctul cel mai din dreapta intr-o amplasare optima.

Restricţii

  • 1 ≤ N ≤ 1.000
  • 1 ≤ lungime[i] ≤ 5.000
  • Suma valorilor lui N in cadrul aceluiasi fisier de intrare este mai mica sau egala cu 6.000.
  • Pentru teste in valoare de 50 de puncte, se garanteaza in plus ca 1 ≤ N, lungime[i] ≤ 100, 1 ≤ T ≤ 25.
  • Printre acestea se afla teste in valoare de 20 de puncte, pentru care se garanteaza in plus ca lungime[i] ≤ lungime[i + 1] pentru toti 1 ≤ i ≤ N - 1.

Exemplu

oxificarelight.inoxificarelight.out
2
3
5 5 5
3
5 4 5
5
6

Explicaţie

O solutie pentru primul test este lista de puncte {1, 6, 1, 6}.
O solutie pentru cel de al doilea test este lista de puncte {0, 5, 1, 6}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?