Fişierul intrare/ieşire:bile8.in, bile8.outSursăLot Seniori Alexandria, 2017, baraj 5
AutorZoltan SzaboAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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 testuluiValoarea lui NValoarea lui P
143
234
3122
466
575
658
7610
8399
9513
10429

Exemplu

bile.inbile.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?