Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

The gift

During the Moon festival in Imagiland the inhabitants hold a giant celebration where they present a "sacrifice" to their god. Since their god is quite fond of computer gaming it is decided that the gift will be an Nvidia 4090 Ti graphics card. However the inhabitants found out that these cards are quite expensive, thus need to put the money together collectively. Of course the people of Imagiland has a very strong sense of justice thus they decided that the amount paid by each citizen should not be the same. However the aforementioned "sense of justice" works in mysterious ways so the only resctrictions is that nobody should give more than what they can (so nobody should be in debts) and if possible everyone should pay as little as possible (so do not steal too much from the rich...khm).
Your task is to create the best cost distribution plan which describes the amount of money paid by each citizen.
We say that a cost distribution plan is the best if each of the following points are fulfilled:
  • The amount paid by each people are listed in increasing order, so it is impossible to know who paid that amount of money (gotta protect anonymity)
  • The maximum of the individually paid amounts is as low as possible. If there are more than one solutions where this maximum is the same then the second highest maximum should be the lowest, then the third one, etc.
  • Noone pays more than their maximum balance, however it is possible for someone to use up all their money.
  • Every paid amount is a non-negative integer.
For example if the price of the gift is 100 dollars which need to be paid by 3 people who can pay 40, 50 and 60 dollars respectively then the best financial distribution is 33, 33, 34 dollars.


  • The first line is a positive N integer which tells us the number of participitating people;
  • The second line is a non-negative M integer which is the price of the present;
  • The next N lines each contain a single non-negative integer X which tells the maximum amount of money a particular citizen has.


  • If it is not possible to buy the gift then print out IMPOSSIBLE.
  • If it is possible to buy the gift then N lines, each containing a single non-negative integer fulfilling each of the following criteria:
    • in each line there is exactly one number;
    • the numbers are in ascending order;
    • the sum of the numbers are M;
    • the maximum of the numbers is the lowest possible. If there are multiple solutions with the same maximum, then the second highest number should be the lowest, etc.


  • 0 < N ≤ 2000
  • 0 ≤ M, X ≤ 1000000000


  1. 3
  2. 100
  3. 20
  4. 20
  5. 40
download as text file Output:
download as text file Input:
  1. 3
  2. 100
  3. 100
  4. 1
  5. 60
download as text file Output:
  1. 1
  2. 49
  3. 50
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019