207. Robbers
time limit per test: 0.5
sec.
memory limit per test: 65536
KB
input: standard
output: standard
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 ith 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 ith robber would get K_{i} coins. In this case unfairness of this fact is X_{i}/YK_{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
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
Output N integer numbers — K_{i} (sum of all K_{i} must be M), so that the total unfairness is minimal.
Sample test(s)
Input
3 10 4
1 1 2
Output
2 3 5
Author:  Andrew Stankevich

Resource:  Petrozavodsk Summer Trainings 2003

Date:  20030823

Server time: 20170923 04:19:54  Online Contester Team © 2002  2016. All rights reserved. 

