Echipa SG1 se află în faţa unei noi provocări. Un dispozitiv antic are un sistem foarte ciudat prin care poate fi pus în funcţiune. Dispozitivul are n butoane numerotate de la stânga la dreapta de la 1 la n. Pe fiecare buton se găseşte un număr natural. Suma tuturor numerelor de pe butoane este divizibilă cu n.
S-a constatat că la atingerea butoanelor din capete (butonul 1 şi butonul n) numărul scris pe acestea scade cu o unitate, iar numărul de pe butonul vecin creşte cu o unitate. Dacă se atinge unul dintre celelalte butoane (cele numerotate cu 2, 3, ..., n-1) numărul corespunzător scade cu două unităţi, iar cele corespunzătoare vecinilor cresc cu câte o unitate. Dispozitivul va fi pus în funcţiune dacă toate cele n numere devin egale.
Ajuţati echipa SG1 să pună dispozitivul în funcţiune folosind un număr minim de atingeri ale butoanelor.
Cerinţă
Cunoscându-se n, numărul de butoane, precum şi cele n numere naturale scrise iniţial pe butoane să se stabilească de câte ori trebuie atins fiecare buton astfel încât dispozitivul să fie pornit astfel încât numărul total de atingeri să fie minim.
Date de intrare
Fişierul de intrare butoane.in conţine pe prima linie numărul natural n, reprezentând numărul de butoane. Pe cea de-a doua linie se află n numere naturale, separate prin câte un spaţiu, reprezentând în ordine valorile înscrise iniţial pe cele n butoane.
Date de ieşire
Fişierul de ieşire butoane.out va conţine n linii. Pe linia i (1≤i≤n) se va afişa un număr natural reprezentând numărul de atingeri ale butonului i.
Restricţii
• 3 ≤ n ≤ 1000
• Numerele înscrise iniţial pe cele n butoane sunt numere naturale mai mici sau egale cu 100. Suma celor n numere este divizibilă cu n.
• Numărul de atingeri ale oricărui buton va fi ≤ 2000000000 (două miliarde).
• Punctaj. Dacă programul afişează o soluţie care determină deschiderea dispozitivului cu număr minim de atingeri, obţine integral punctajul pentru testul respectiv. Dacă numărul de atingeri nu este minim, dar soluţia afişată determină deschiderea dispozitivului, se obţine 30% din punctaj.