Clasa a XII-a
Ziua 1
Problema 1
Bomboane
La o fabrica de bomboane, sunt puse pe un stand n (n<=100) cutii de bomboane.
Fiecare din cele n cutii contin cate m (m<=1000) bomboane dintr-un singur
sortiment. Toate cele n sortimente sunt distincte. Un angajat mai distrat
incepe sa se amuze si amesteca bomboanele din cutii. Spre a nu fi observata
modificarea el are grija ca in fiecare cutie sa ramana cate m bomboane.
Necazul apare cand seful sau ii cere sa-i aduca cate o bomboana din fiecare
cutie, deci din fiecare sortiment. Fiind urmarit de catre acesta muncitorul nu
va avea voie sa extraga decat o bomboana din fiecare cutie.
Muncitorul acorda 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 de risc al tuturor celor n extrageri va fi egal cu suma
riscurilor fiecareia.
Alcatuiti un
program care
determina ce
sortiment de bomboana va extrage din
fiecare cutie pentru ca gradul de risc total sa fie minim.
Datele de intrare
se gasesc in
fisierul bonbon.in
sub forma urmatoare:
-pe prima linie numerele n si m despartite printr-un spatiu;
-pe urmatoarele n linii se gasesc cate m numere despartite printr-un
spatiu.
Cele m numere reprezinta sortimentele bomboanelor ce se regasesc in fiecare
cutie dupa amestecare, in ordine, incepand cu cutia 1 pana la cutia n.
Fisierul de iesire bonbon.out contine doua linii:
-pe prima linie, un numar natural reprezentand gradul total minim de risc.
-pe a doua linie n numere despartite printr-un spatiu reprezentand numarul de
ordine al cutiei din care va fi scoasa bomboana din fiecare sortiment, in
ordine, incepand cu sortimentul 1 pana la sortimentul n.
Exemplu:
Pentru fisierul bonbon.in
7 3
1 2 7
6 6 4
4 7 3
4 2 3
2 1 3
7 5 1
5 5 6
Continutul fisierului bonbon.out va fi:
10
1 5 3 4 7 2 6
Note
- q Timp de executie, maxim 6 secunde pe test
- q Īn cazul in care exista mai multe posibilitati de extragere cu risc total
minim, se va afisa una singura.
Punctaj: 60 puncte