1975 - bluescreen

Enunt

IceManLucky joacă League of Legends când dintr-o dată calculatorul i se blochează şi pe ecran îi apare bine cunoscutul blue screen. Pe ecran el vede acum 2N numere reale : a1 , a2 , …, a2n. Având un calculator mai special, IceManLucky ştie că există o singură soluţie ca să remedieze problema. El efectuează N operaţii consecutiv, o operaţie constând în :

- alege 2 indecşi i şi j (i ≠ j), pe care nu i-a mai ales anterior - rotunjeşte ai la cel mai apropriat număr întreg care nu este mai mare ca ai - rotunjeşte aj la cel mai apropriat număr întreg care nu este mai mic ca aj

Scopul lui IceManLucky este ca diferenţa absolută dintre suma numerelor apărute iniţial pe ecran şi suma numerelor după efectuarea celor N operaţii descrise mai sus să fie minimă.

Cerinta

Ajutaţi-l pe IceManLucky să determine diferenţa absolută minimă dintre cele două sume pentru ca acesta să se poată întoarce fericit la joc.

Date de intrare

Fişierul de intrare bluescreen.in conţine pe prima linie numărul N, iar pe a doua linie 2N numere reale, date cu exact 3 zecimale, separate prin spaţiu.

Date de ieșire

Fişierul de ieşire bluescreen.out va conţine pe prima linie diferenţa minimă (în valoare absolută), scrisă cu exact 3 zecimale.

Restricții și precizări

1 ≤ N ≤ 2000
Numerele din şir sunt reale pozitive şi mai mici decât 10000
FeelsGoodMan

Exemplul 1

bluescreenin.txt

3

0.000 0.500 0.750 1.000 2.000 3.000

bluescreenout.txt

Datele introduse corespund restrictiilor impuse.

0.250

Exemplul 2

bluescreenin.txt

0

1.222 1.333 1.654

bluescreenout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

def minim_diferenta_absoluta(n, numere):

   numere.sort()  # Sortăm lista de numere

   suma_initiala = sum(numere[:n])  # Suma primelor N elemente
   suma_dupa_operatii = sum(numere[n:])  # Suma celorlalte N elemente

   diferenta_absoluta = abs(suma_initiala - suma_dupa_operatii)
   return diferenta_absoluta

print(rezultat)

</syntaxhighlight>