.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » butoane

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
butoane


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

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.

Exemple

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

autor: Prof. Adrian Panaete
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2011: sport2, macheta, acces, mxl, segmente, tsunami, tort1, ec, ape, poligon4, stalpi2, furnici1, telecab, ikebana, posta, fotbal1, xmoto, radare, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
De acelaşi autor: risipa, mofocarburi, cover1, codarb, trifoi, albine2, nkd, transform, fractii2, 2sah
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre sisteme de ecuatii liniare: xor, romeo, bcolor, magic4, mofocarburi, gxor
surse trimise | ajutor