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

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


Timp maxim de executie/test:
0.4 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

La o fabrica de bomboane, sunt puse pe un stand n cutii de bomboane. Fiecare dintre cele n cutii contine câte m bomboane dintr-un singur sortiment. Toate cele n sortimente sunt distincte. Un muncitor mai distrat începe sa se amuze si amesteca bomboanele din cutii. Pentru a nu fi observata modificarea, el are grija ca în fiecare cutie sa ramâna câte m bomboane.

Necazul apare când seful sau îi cere sa-i aduca câte o bomboana din fiecare cutie, deci o bomboana din fiecare sortiment. Fiind urmarit de catre acesta, muncitorul nu va avea voie sa extraga decât o bomboana din fiecare cutie.

Muncitorul a asociat fiecarei extrageri un grad de risc. Astfel, la extragerea unei bomboane din sortimentul cu numarul i din cutia care continea initial sortimentul cu numarul j, gradul de risc va fi valoarea absoluta a diferentei dintre i si j. Gradul total de risc este egal cu suma riscurilor tuturor celor n extrageri.

Cerinta

Sa se determine ce sortiment de bomboana va trebui sa extraga muncitorul din fiecare cutie pentru ca gradul de risc total sa fie minim.

Date de intrare

Pe prima linie a fisierului bomboane.in sunt scrise numerele n si m separate printr-un spatiu. Pe fiecare dintre urmatoarele n linii se gasesc câte m numere separate prin cate un spatiu. Cele m numere de pe linia i+1 reprezinta sortimentele bomboanelor ce se gasesc în cutia i dupa amestecare.

Date de iesire

Fisierul de iesire bomboane.out va contine doua linii:
- pe prima linie se va scrie un numar natural reprezentând gradul total minim de risc
- pe a doua linie sunt scrise n numere separate prin cate un spatiu ; al i-lea numar de pe linie reprezinta numarul de ordine al cutiei din care va fi extrasa bomboana din sortimentul i.
În cazul în care exista mai multe posibilittati de extragere cu risc total minim, se va afisa una singura.

Restrictii

0 < n < 101
0 < m < 1001

Exemplu

bomboane.in bomboane.out
7 3  
1 2 7
6 6 4
4 7 3
4 2 3
2 1 3
7 5 1
5 5 6
10
1 5 3 4 7 2 6

Prof. Dana Lica
 Colegiul Naţional "I.L. Caragiale" Ploieşti
Contact:danal182001@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre flux: matrice2, furtuna, croco, kimberley, datorii, trafic, sponsori, monede1, algola, trasee, drumuri, magic5, teroristi, universitate, terenuri3d, asfalt1
Despre drum minim: miniasm, robot, furtuna, excursie, arthur, bete, zmeu, trafic, masina1, traseu, litoral, lover, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
surse trimise | ajutor