|
Az ajándék
Cerbengóciában Holdünnep idején hatalmas fesztivált rendeznek melyek része, hogy az ország istenségének áldozatot mutatnak be. Mivel az istenség kimondottan szereti a számítógépes játékokat, így az idei ajándék egy Nvidia 4090 Ti videokártya. Azonban az ország lakói rájöttek, hogy egy ilyen eszköznek igen borsos ára van, ezért úgy döntöttek, hogy közösen összedobják rá a pénzt. Természetesen a lakosok igen erős igazságérzettel rendelkeznek, így úgy döntöttek, hogy nem egyenlő részben járulnak hozzá a költségekhez. Azonban a már említett igazságérzet kicsit furcsán működik, így az egyetlen megkötés az, hogy senki nem adósodhat el az ajándékhoz való hozzájárulás során (azaz minden lakos maximum annyival járulhat hozzá a vásárláshoz amennyi pénze van) és lehetőség szerint törekedni kell arra, hogy mindenki a lehető legkevesebbet fizesse (azaz amennyiben egy mód van rá ne fosszuk ki teljesen a gazdagokat...khm).
A feladatunk az, hogy megadott lakosságszám, egyénenkénti költségvetés és ajándékár ismeretében megadjuk a lehető legjobb költségeloszlási tervet (azaz, hogy ki mennyit fizessen).
Egy költségvetési tervet legjobbnak nevezünk ha az alábbi feltételek mindegyike teljesül:
- A fizetendő összegek növekvő sorrendben vannak kiírva, azaz nem köthető emberhez a kifizetett mennyiség (a lakosság anonimitása mindig fontos volt az országban)
- A kifizetett összegek maximuma a lehető legkisebb. Több lehetséges ilyen megoldás esetén a második legnagyobb érték legyen a legkisebb. Ha még mindig több megoldás van akkor a harmadik legnagyobb érték legyen a legkisebb, stb.
- Senkinek nem kell többet fizetnie mint amennyivel rendelkezik (de semmi nem akadályozza meg azt, hogy az összes pénzét elvegyék).
- Minden kifizetett összeg nemnegatív egész szám.
Így például ha az ajándék összege 100 peták mely 3 ember között oszlik el akik fejenként 40, 50 és 60 petáknyi költségvetéssel rendelkeznek akkor a legjobb költségvetési eloszlás 33, 33, 34 peták.
Input
- A bemenet első sora egy N pozitív egész, mely megmondja, hogy hányfelé oszlik az ajándék ára;
- A második sor egy M nemnegatív egész, mely az ajándék árát adja meg;
- A következő N darab sor soronként egy darab nemnegatív egész X számot tartalmaz, mely egy-egy konkrét lakos maximálisan rendelkezésre álló pénzmennyiségét adja meg.
Output
- Amennyiben az ajándék kifizetése lehetetlen a megadott feltételek mellett úgy az IMPOSSIBLE szó.
- Ha az ajándékot ki lehet fizetni úgy N darab nemnegatív egész szám, melyek teljesítik a következő feltételeket:
- soronként pontosan 1 darab szám szerepel;
- a számok növekvő sorrendben vannak megadva;
- a számok összege M;
- a számok maximuma a lehető legkisebb. Több, ugyanakkora maximummal rendelkező megoldás esetén a 2. legnagyobb szám legyen a lehető legkisebb, stb.
Megkötések
- 0 < N ≤ 2000
- 0 ≤ M, X ≤ 1000000000
Példa
|
|