Fișierul intrare/ieșire butoane.in, butoane.out Sursă ONI 2011 clasa a 8-a
Autor Adrian Panaete Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Butoane (clasa a 8-a)

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.

Exemplu

butoane.in butoane.out
3
10 11 12
0
1
2

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii