| Fişierul intrare/ieşire: | bile8.in, bile8.out | Sursă | Lot Seniori Alexandria, 2017, baraj 5 |
| Autor | Zoltan Szabo | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 2.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bile8
Într-o cameră sunt N urne. În fiecare urnă sunt plasate câte P bile numerotate cu numere întregi. Printre cele N * P bile nu există două bile care să aibă acelaşi număr.
Pentru orice număr natural X din intervalul [1, P * N] există o combinaţie de bile, extrase din fiecare urnă câte una, asfel încât suma numerelor inscripţionate pe bile să fie X.
De exemplu, dacă avem 2 urne şi în fiecare urnă câte 4 bile, atunci urnele cu conţinutul U1 = {6, 7, 10, 11}, U2 = {-5, -3, 3, 5} permit obţinerea tuturor numerelor naturale din intervalul [1, 16]:
1=6-5, 2=7-5, 3=6-3, 4=7-3,
5=10-5, 6=11-5, 7=10-3, 8=11-3,
9=6+3, 10=7+3, 11=6+5, 12=7+5,
13=10+3, 14=11+3, 15=10+5, 16=11+5.
O altă posibilă configuraţie a urnelor este {-2, 0, 2, -4} şi {5, 14, 13, 6}.
În prima soluţie prezentată maximul bilelor este 11, pe când în a doua soluţie maximul bilelor este 14.
Cunoscând valorile lui N şi P se cere o configuraţie a urnelor în care maximul numerelor înscrise pe bile este minim.
Date de intrare
Fişierul de intrare bile.in va conţine pe N şi P, pe un rând.
Date de ieşire
Fişierul de ieşire x-bile.out va conţine N linii, iar pe fiecare linie vor fi câte P numere întregi separate prin spaţiu. Fiecare linie reprezintă conţinutul unei urne.
Restricţii şi precizări
- N * P ≤ 1.000.000
- -1.000.000.000 ≤ numerele de pe bile ≤ 1.000.000.000
- Nu contează ordinea urnelor, respectiv ordinea bilelor în urne.
- O soluţie valorează 0 puncte dacă valoarea maximă a bilelor este mai mare decât maximul bilelor din rezultatul comisiei.
- Valorile lui N şi P pentru toate testele sunt sintetizate mai jos:
| Indicele testului | Valoarea lui N | Valoarea lui P |
|---|---|---|
| 1 | 4 | 3 |
| 2 | 3 | 4 |
| 3 | 12 | 2 |
| 4 | 6 | 6 |
| 5 | 7 | 5 |
| 6 | 5 | 8 |
| 7 | 6 | 10 |
| 8 | 3 | 99 |
| 9 | 5 | 13 |
| 10 | 4 | 29 |
Exemplu
| bile.in | bile.out |
|---|---|
| 2 4 | -6 2 -2 6 10 8 7 9 |
Explicaţie
Avem 2 urne, fiecare conţine câte 4 bile.
Valoarea maximă minimizată este 10.
Dacă s-ar fi afişat oricare din exemplele din descrierea cerinţei, punctajul pe test ar fi fost 0.
