Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1991_3e1_diskeliai.in

Rezultatų failas: lmio_1991_3e1_diskeliai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Diskelių paskirstymas

Užduotis

Mūsuose prekių paklausa dažnai viršija pasiūlą. Tarkime, kad n pirkėjų nori įsigyti

D=D_1+D_2+...+D_n

diskelių kompiuteriams. Tuo tarpu tiekėjas gavo tik d<D diskelių. Kaip juos padalyti?

Buvo sutarta, kad teisingiausia būtų išdalyti taip, kad egzistuotų toks skaičius C ir būtų tenkinamos tokios sąlygos:

  • jei D_i\\leqC, tai d_i=D_i;
  • jei D_i>C arba d_i=C+1;
  • jei D_i\\leqD_j, tai d_i\\leqd_j;

d=d_1+d_2+...+d_n.

C – skaičius, parenkamas sprendžiant uždavinį. Kaip išdalyti diskelius, kad būtų tenkinamos išvardytos sąlygos?

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas 
20
7
10
11
13
15
0
 
C = 3
1 7 4
2 10 4
3 11 4
4 13 4
5 15 4
 Tiekėjas gavo 20 diskelių.
Tolesnėse eilutėse išvardyta kiekvieno pirkėjo pageidaujamas diskelių skaičius. Duomenų pabaigą rodo eilutė, kurioje įrašytas 0.
Tad iš viso yra 5 pirkėjai ir jie pageidauja 7+10+11+13+15=56 diskelių.
Pirmoji rezultatų eilutė parodo C reikšmę. Toliau yra tiek eilučių kiek yra pirkėjų ir kiekvienoje jų yra po tris skaičius.
Pirmasis parodo pirkėjon umerį, antrasis – pirkėjo prašomų diskelių skaičių, trečiasis – pirkėjui paskirtų diskelių skaičių.

Ribojimai

1\\leqn\\leq100

1\\leqd\\leq25000

1\\leqD\\leq70000