0108. Robbers

Имя входного файла:	robbers.in
Имя выходного файла:	robbers.out
Ограничение по времени:	1 s
Ограничение по памяти:	32 megabytes

N robbers have robbed the bank. As the result of their crime they chanced to get M golden coins. Before the robbery the band has made an agreement that after the robbery i-th gangster would get X_i/Y of all money gained. However, it turned out that M may be not divisible by Y.

The problem which now should be solved by robbers is what to do with the coins. They would like to share them fairly. Let us suppose that i-th robber would get K_i coins. In this case unfairness of this fact is |X_i/Y-K_i/M|. The total unfairness is the sum of all particular unfairnesses. Your task as the leader of the gang is to spread money among robbers in such a way that the total unfairness is minimized.

Input file

The first line of the input file contains numbers N, M and Y (1 ≤ N ≤ 1000, 1 ≤ M, Y ≤ 10000). N integer numbers follow - X_i (1 ≤ X_i ≤ 10000, sum of all X_i is Y).

Output file

Output N integer numbers – K_i (sum of all K_i must be M), so that the total unfairness is minimal.

Examples:

robbers.in	robbers.out
3 10 4 1 1 2	2 3 5

Источник: Petrozavodsk Summer 2003. Andrew Stankevich Contest 1, Saturday, August 23
Автор: Andrew Stankevich

Обсудить       Отправить решение



Версия для печати