Ədalətli Bölüşdürmə#2449

Şərt Müzakirə

Ədalətli Bölüşdürmə

1 saniyə

64 meqabayt

Çətin

Dostunuzun ad günüdür və siz və bir neçə nəfər ona StarCraft II oyununun bir nüsxəsini almağa qərar verdiniz, çünki kim bu oyunu istəməz ki?

Aranızda xərcləri mümkün qədər ədalətli şəkildə bölüşmək qərarına gəldiniz. Bəzilərinizin başqalarına nisbətən daha çox pulu olduğu üçün həmçinin razılaşdınız ki, heç kim ödəyə biləcəyindən artıq pul ödəməməlidir. Hər bir ödəniş $1$ sentin kəsi olmamalıdır, yəni heç kim sentin ondalığı ilə ödəməməlidir.

Hər kəs ödəyə biləcəyi maksimum məbləği yazır. Hər kəsin bu maksimum məbləği nəzərə alındıqda, hədiyyənin qiymətini mümkün qədər ədalətli bölüşürsünüz. Bu o deməkdir ki, hər kəsin ödədiyi məbləğlərin ümumi xərclə $1/n$ -nə olan ən böyük fərqi minimum olmalıdır. Əgər bərabərlik olarsa, ikinci ən böyük fərqi, sonra üçüncüsünü, və s. minimallaşdırırsınız. Ödənişin ən kiçik vahidi $1$ sent olduğundan, xərcləri bir neçə fərqli yolla böldüyünüz hallar ola bilər. Bu halda, daha çox ödəyə bilən şəxslər daha çox ödəməlidir. Əgər yenə də qeyri-müəyyənlik qalırsa, siyahıda daha əvvəl gələnlər daha çox ödəyir.

Prezenti siz aldığınız üçün, hər kəsin nə qədər ödəməli olduğunu (özünüz də daxil olmaqla) tapmaq tapşırığı sizə düşür.

Giriş

Birinci sətirdə müsbət tam ədəd, testlərin sayı verilir, ən çox $100$ . Hər test üçün:

Bir sətirdə iki tam ədəd $p$ və $n$ : hədiyyənin qiyməti sentlərlə (1 \leq p \leq 1000000) və iştirakçıların sayı (2 \leq n \leq 100) (özünüz daxil olmaqla).
Bir sətirdə $n$ tam ədəd $\textbf{a_i}$ (1 \leq a_i \leq 1000000), burada a_i siyahıdakı $i$ -ci şəxsin ödəyə biləcəyi maksimum məbləğdir (sentlərlə).

Çıxış

Hər test üçün:

Bir sətirdə $n$ tam ədəd: yuxarıdakı qaydaya uyğun olaraq hər bir şəxsin ödəməli olduğu məbləğlər. Əgər ümumi xərci bu qaydalar əsasında bölüşdürmək mümkün deyilsə, bu sətirdə "IMPOSSIBLE" yazılmalıdır.

Nümunələr

Nümunə 1

Loading

Loading

1 \leq p \leq 1000000

2 \leq n \leq 100

1 \leq a_{i} \leq 1000000

a_{i}