Desert

Time limit: 0.1s Memory limit: 2MB Input: desert.in Output: desert.outPoints by default: 10p

Andrei este pofticios. După ce a mâncat primele feluri, acesta vrea să își pregătească trei torturi, dintre care va mânca doar unul la întâmplare.

Un tort va fi alcătuit din mai multe sortimente de ciocolată. Definim greutatea unui astfel de tort ca fiind suma gramajelor sortimentelor de ciocolată folosite, adică un tort alcătuit din 2020 grame de ciocolată albă și 3030 grame de ciocolată neagră va avea greutatea de 5050 de grame.

Andrei are la dispoziție NN sortimente de ciocolată, dispuse în linie pe un raft din cămara sa, fiecare având un număr de ordine.

  • Pentru primul tort, băiatul va folosi toate sortimentele de la primul până la un anumit număr de ordine AA, ales de acesta;
  • Pentru al doilea tort, va folosi toate sortimentele de la numărul de ordine A+1A + 1 până la un anumit număr de ordine BB, ales de acesta;
  • Pentru al treilea tort, va folosi toate sortimentele de la numărul de ordine B+1B + 1 până la ultimul sortiment.

Cum tortul pe care îl va mânca băiatul este selectat la întâmplare, Andrei vrea să se asigure că se va sătura alegând oricare dintre cele trei torturi, așa că își propune să minimizeze diferența dintre greutatea celui mai "greu" tort și greutatea celui mai "ușor" tort.

Altfel spus, notând greutatea celor trei torturi cu T1, T2, T3, Andrei vrea ca expresia următoare, numită eroarea rețetei, să fie cât mai mică:

max(T1, T2, T3) - min(T1, T2, T3)

Cerință

Dându-se cele NN sortimente de ciocolată și gramajul fiecăruia, aflați cea mai mică eroare a rețetei posibilă, ajutându-l pe Andrei să aleagă cele două poziții/numere de ordine AA și BB.

Date de intrare

Pe prima linie a fișierului de intrare desert.in se va afla numărul NN.

Pe a doua linie se vor afla gramajele celor NN sortimente de ciocolată de pe raft.

Date de ieșire

Pe prima linie a fișierului de ieșire desert.out se va afișa eroarea minimă a rețetei.

Restricții și precizări

  • 3N21053 \le N \le 2 \cdot 10^5
  • 11 \le gramajul oricărui sortiment de ciocolată 104\le 10^4
  • Se acordă 1010 puncte din oficiu.
# Punctaj Restricții
1 20 3N5003 \le N \le 500
2 20 3N1043 \le N \le 10^4
3 50 Fără restricții suplimentare

Exemplu

desert.in

10
8 16 11 1 5 20 14 20 7 5

desert.out

7

Explicație

Putem alege A=4A = 4 și B=7B = 7, iar torturile vor arăta in felul următor:

Astfel, primul tort va conține sortimentele de la 11 la 44, având greutatea 8+16+11+1=368 + 16 + 11 + 1 = 36.
Al doilea tort va conține sortimentele de la 55 la 77, având greutatea 5+20+14=395 + 20 + 14 = 39.
Al treilea tort va conține sortimentele de la 8 la 10, având greutatea 20+7+5=3220 + 7 + 5 = 32.
În acest caz, eroarea rețetei este max(36,39,32)min(36,39,32)=3932=7\max(36, 39, 32) - \min(36, 39, 32) = 39 - 32 = 7. Se poate demonstra faptul că răspunsul este optim.

Log in or sign up to be able to send submissions!