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ă.

Cerința

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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

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

Exemplul 1:

bluescreen.in

3
0.000 0.500 0.750 1.000 2.000 3.000

bluescreen.out

0.250 

Explicație

Operatiile efectuate sunt: (i=1, j=4); (i=2, j=3); (i=5, j=6).

Se obtine sirul : 0, 0, 1, 1, 2, 3.

Exemplul 2:

bluescreen.in

20000
0.000 0.500 0.750 1.000 2.000 3.000

bluescreen.out

Datele nu corespund restrictiilor impuse

Rezolvare

import sys

MAX_N = 4005

def check_constraints(N, input_values):
    if not (1 <= N <= 2000):
        print("Datele nu corespund restrictiilor impuse", file=sys.stdout)
        sys.stdout.close()
        sys.exit(0)

    for a in input_values:
        a_float = float(a)
        if not (0 <= a_float < 10000):
            print("Datele nu corespund restrictiilor impuse", file=sys.stdout)
            sys.stdout.close()
            sys.exit(0)

def main():
    sys.stdin = open("bluescreenIN.txt", "r")
    sys.stdout = open("bluescreenOUT.txt", "w")

    N = int(input().strip())
    input_line = input().strip().split()

    check_constraints(N, input_line)

    integer_numbers = 0
    sum_initial = 0

    for i in range(2 * N):
        a = float(input_line[i])
        if a % 1 == 0:
            integer_numbers += 1
        sum_initial += (a - int(a))

    sol = 1e9

    for i in range(N, N - integer_numbers, -1):
        sol = min(sol, abs(sum_initial - i))

    print("{:.3f}".format(sol))

    sys.stdin.close()
    sys.stdout.close()

if __name__ == "__main__":
    main()