- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
نمرههای درس «آمار» این ترم پایین بوده و استاد تصمیم گرفته نمرهی دانش آموزان را افزایش دهد. اگر نمرهی دانش آموز $i$ را $a_i$ در نظر بگیریم، استاد میخواهد نمرهی $b_i$ را برای او ثبت کند، به طوری که شرایط زیر برقرار باشد:
-
$a_i \leq b_i$
-
$a_i < a_j \Rightarrow b_i < b_j$
-
تمامی $b_i$ها طبیعی هستند.
برای اینکه نمرهها به صورت منطقی افزایش یابند، استاد میخواهد میانگین نمرات بعد از افزایش برابر با عدد $M$ شود و در بین حالتهایی که این ویژگی را دارند، پراکندگی نمرات کمینه شود. پراکندگی یک دنبالهی دلخواه مانند $c_i, c_2, \cdots , c_n$ با میانگین $T$ برابر است با :
$$\frac{\Sigma_{i=1}^{n} (c_i - T)^2}{n}$$
ورودی
سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد دانش آموزان، و عدد $M'$، به طوری که $M'= M\times n$ است.
در سطر دوم دنبالهی $a_1, a_2, \cdots, a_n$ آمده است به طوری که $a_i$ نشاندهندهی نمرهی دانشآموز $i$ است. دنبالهی $a_i$ها اکیدا صعودی است. $$1 \leq n \leq 1\ 000\ 000$$
$$1 \leq a_i \leq 10^9 $$
$$\Sigma_{i=1}^{n} a_i \leq M' \leq 10^{18}$$
خروجی
دنبالهی $b_1, b_2, \cdots, b_n$ را در خروجط چاپ کنید. در صورت وجود چندین جواب یکی را به دلخواه چاپ کنید.
مثال
ورودی نمونه ۱
3 9
1 2 3
خروجی نمونه ۱
2 3 4
ورودی نمونه ۲
4 10
1 2 3 4
خروجی نمونه ۲
1 2 3 4
۲۵امین دوره المپیاد کامپیوتر - آزمون اول- ۱۳۹۴/۵/۳۱
ارسال پاسخ برای این سؤال