Fişierul intrare/ieşire:euro3.in, euro3.outSursăONI 2016, clasele 11-12
AutorRazvan SalajanAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Euro3

După calificarea la campionatul european de fotbal din Franţa, având în vizor N jucători din care trebuie să convoace câţiva în echipa naţională, selecţionerul României a apelat la nişte metode mai puţin ortodoxe. Acesta a mers la vrăjitoarele renumite din Craiova pentru a-l ajuta să gasească formula câştigătoare pentru meciul de deschidere cu Franţa. Vrăjitoarele, după descântece îndelungate, au ajuns la concluzia că lotul de jucatori trebuie sa aibă valoarea exact X şi coeficientul de aroganţă cât mai mic. Valoarea unui lot de jucători e definită ca suma valorilor jucătorilor ce intră în componenţa lotului. Coeficientul de aroganţă al unui lot de jucători e definit ca diferenţa dintre valoarea maximă a unui jucător din lot şi valoarea minimă a unui jucător din lot. Se mai ştie că valoarea lotului nu poate depăşi o valoare cunoscută Vmax. Un lot de jucători e definit ca o submulţime nevidă de jucători aleşi dintre cei N. Atenţie, un lot poate fi format şi dintr-un singur jucător.

Cerinta

Se dă numărul N de jucători, numărul Vmax definit mai sus şi valoarea fiecărui jucător. Selecţionerul României a găsit formula câştigătoare şi e curios dacă puteţi şi voi. Fiindcă nu are încredere totală în vrăjitoare, acesta vă cere să aflaţi pentru fiecare valoare X din intervalul [1,Vmax] coeficientul de aroganţă minim posibil pentru care există cel puţin un lot dintre cei N jucători cu valoare exact X. Dacă nu se poate obţine nici un lot de valoare exact X, se consideră ca răspuns -1.

Date de intrare

Fişierul de intrare euro3.in conţine pe prima linie T, reprezentând numărul de teste. În continuare vor urma T teste, fiecare având următoarea structură: pe prima linie dintr-un test se află N şi Vmax, reprezentând numărul total de jucători, respectiv valoarea maximă pe care o poate avea un lot de jucători. A doua linie a testului conţine N numere naturale despărţite prin câte un spaţiu. Al i-lea număr de pe această linie reprezintă valoarea pe care o are al i-lea jucător.

Date de ieşire

În fişierul de ieşire euro3.out se vor afişa T linii, câte una pentru fiecare test din fişierul de intrare. O linie corespunzătoare unui test conţine Vmax numere, unde cel de-al i-lea număr reprezintă coeficientul de aroganţă minim posibil pentru o submulţime de jucători de valoare exact i. În cazul în care nu există o submulţime de jucători de valoare exact i se afişează -1.

Restricţii si precizari

  • 1 ≤ T ≤ 2
  • 1 ≤ N ≤ 4000
  • 1 ≤ Vmax ≤ 8000
  • 1 ≤ valoare[i] ≤ Vmax
  • Pentru 20% din teste N ≤ 20
  • Pentru 40% din teste N ≤ 100 si Vmax ≤ 100
  • Pentru 50% din teste N ≤ 300 si Vmax ≤ 300

Exemplu

euro3.ineuro3.out
2
4 7
5 2 3 4
5 15
1 8 2 3 6
-1 0 0 0 0 2 1
0 0 0 2 1 0 5 0 3 5 4 5 6 2 7

Explicatie

Pentru primul test:

  • Nu se poate gasi un lot de valoarea 1, deci raspunsul pentru 1 este -1.
  • Se pot obtine loturi de valoare 2, 3, 4, 5 dintrun singur jucator.
  • Lotul de valoare 6 se poate obtine din jucatorii cu valorile 2 si 4.
  • Pentru valoarea 7 exista doua loturi posibile formate din jucatorii cu valorile 5 2 respectiv 3 4. Cel din urma lot are coeficientul de aroganta mai mic, adica max(3,4) - min(3,4) = 1.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?