Pracsiu Dan (dnprx) În preajma Crăciunului, pentru transportul celor N (N ≤ 15) porci, de la ferma proprie la piață pentru vânzare, un gospodar are la dispoziție un singur mijloc de transport – o remorcă. Această remorcă poate transporta doar o greutate maximă G (G ∊ N*). Gospodarul știe greutatea gi a fiecărui porc i, 1 ≤ i ≤ N, gi ∊ N*.
Cerința
Să se realizeze o repartizare a porcilor în 3 grupuri astfel încât mijlocul de transport să poată realiza trei drumuri până la piață, iar diferența de greutate dintre cele 3 transporturi să fie minimă.
Date de intrare
Fișierul de intrare ferma.in conține pe prima linie trei valori C N G, separate prin câte un spațiu, reprezentând cerința C (1, 2 sau 3), numărul de porci și greutatea maximă permisă în remorcă. Următoarea linie conține N valori naturale nenule separate prin câte un spațiu, g1 g2 ... gN. reprezentând greutățile celor N porci.
Date de ieșire
Dacă cerința este C = 1, fișierul de ieșire ferma.out va conține pe prima linie trei numere naturale separate prin câte un spațiu, reprezentând sumele greutăților din cele 3 transporturi, scrise în ordine crescătoare. Dacă cerința este C = 2, fișierul de ieșire va conține pe prima linie N valori 1, 2, 3 indicând transportul din care face parte fiecare porc; în cazul în care există mai multe soluții se va afișa soluția minimă din punct de vedere lexicografic. Dacă cerința este C = 3, fișierul de ieșire va conține pe prima linie un sigur număr natural reprezentând diferența de greutate dintre cele 3 transporturi.
Restricții și precizări
10 ≤ N ≤ 1510 ≤ G ≤ 40.0001 ≤ gi ≤ 10.000,1 ≤ i ≤ N- Pentru toate testele există soluție
Exemplul 1:
ferma.in
1 10 238 106 58 73 48 64 64 61 77 62 98
ferma.out
237 237 237
Explicație
Suma greutăților este 237 în fiecare transport.
Exemplul 2:
ferma.in
2 10 238 106 58 73 48 64 64 61 77 62 98
ferma.out
1 1 1 2 2 2 2 3 3 3
Explicație
Primii 3 în transportul 1, următorii 4 în transportul 2, ultimii 3 în transportul 3.
Alte soluții corecte:
2 2 2 1 1 1 1 3 3 3
3 3 3 1 1 1 1 2 2 2
etc.
Exemplul 3:
ferma.in
3 10 238 106 58 73 48 64 64 61 77 62 98
ferma.out
0
Explicație
Diferența este 0.
Exemplul 4:
ferma.in
1 7 33 9 1 8 2 7 3 4
ferma.out
11 11 12
Explicație
Transportul 1 și 2 greutate 11, transportul 3 greutate 12.
Exemplul 5:
ferma.in
2 7 33 9 1 8 2 7 3 4
ferma.out
1 1 2 1 3 2 3
Explicație
O altă soluție corectă este 3 3 2 3 1 2 1 dar nu este minimă lexicografic.
Exemplul 6:
ferma.in
3 7 33 9 1 8 2 7 3 4
ferma.out
1
Explicație
Cea mai mare diferență între cele 3 transporturi este 1.