问题 4390 --2011年校内赛 - D 买礼物

4390: 2011年校内赛 - D 买礼物

时间限制: 2 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

 你的好朋友小Y快生日了!你和其他的朋友商量后决定,凑钱买一份礼物送给你的好朋友小Y

       礼物的价钱已经获知,所有的朋友委托你把买礼物的钱分摊到各个人。你答应他们一定会尽可能分摊公平,也就是说各个人分摊到的资金尽可能接近。同时,朋友们每个人都有一个最大可支付资金,也就是说他们拿不出超过他们最大可支付资金的钱。

       现在你已经知道礼物的价格和朋友们的最大可支付资金列表,你的任务就是寻找最公平的方案,计算所有人该付多少钱。所谓最公平的方案,就是让分摊的资金,跟 礼物的价钱的n分之一的最大差距 尽可能小。如果有两个方案,分摊的资金,跟 礼物的价钱的n分之一的最大差距 一样大,则跟 礼物的价钱的n分之一的第二大差距 小的为优,以此类推。如果还存在多个可行方案,则让最大可支付资金大的人付更多的钱。如果这时还存在多个可行方案,则让在列表中先出现的人付更多的钱。

       注意,每个人分摊的钱必须是整数。      

输入

 多组测试数据。测试数据的开头是一个正整数t,表示测试数据的组数。

    每一组测试数据都以两个整数pn开头,分别代表礼物的价格和朋友的个数。接下来有n个整数,代表第1个朋友到第n个朋友的最大可支付资金ai(1 ≤ p ≤ 10000002 ≤ n ≤ 1001 ≤ ai ≤ 1000000)

输出

 每组测试数据输出一行,该行有n个整数,表示每个朋友应支付的价钱。顺序跟输入的顺序一样。两个整数之间输出一个空格,注意行末不要输出空格。如果没有可行方案,则输出 IMPOSSIBLE”

 

样例输入

3
20 4
10 10 4 4
7 3
1 1 4
34 5
9 8 9 9 4

样例输出

6 6 4 4
IMPOSSIBLE
8 7 8 7 4

来源

[提交][状态]