- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
خانم دکتر دنبالهای از اعداد طبیعی دارد. همانطور که میدانید دکترها برعکس مهندسها از صعودیبودن دنبالهها لذت میبرند ولی بلد نیستند دنبالههایشان را صعودی کنند. برای همین خانم دکتر از آقای مهندس خواستهاست تا دنبالهاش را برایش صعودی کند. (منظور از دنبالهی صعودی دنبالهای است که هیچ عضوی از آن از عضو قبلیاش کمتر نیست) آقای مهندس در هر حرکت میتواند یکی از ارقام یکی از اعداد دنباله را حذف کند. دقت کنید که وقتی تمامی ارقام یکی از اعداد دنباله را حذف کنیم مقدارش صفر خواهد شد.
او به عنوان یک مهندس مجبور است در کمترین تعداد حرکت دنباله را صعودی کند. این کمترین تعداد حرکت چقدر است؟ همچنین او میخواهد جمع اعداد دنبالهی نهایی که با کمترین تعداد حرکات به آن میرسد کمینه باشد. (در عین استفاده از کمترین تعداد حرکت) این مجموع کمینه را نیز پیدا کنید.
ورودی
سطر اول ورودی شامل عدد طبیعی \(n\)، تعداد اعداد دنباله، است.
در سطر بعد \(n\) عدد طبیعی \(a_i\) آمدهاست که اعداد دنباله را نشان میدهند. تضمین میشود هیچ کدام از اعداد دنباله رقم \(0\) ندارند.
\[1\leq n \leq 50\ 000 \]
\[1\leq a_i \leq 10^{18} \]
خروجی
در سطر اول خروجی کمترین تعداد حرکت برای صعودی کردن دنباله را چاپ کنید.
در سطر دوم \(n\) عدد چاپ کنید که اعداد دنباله نهایی را نشان میدهند که هم باید صعودی باشند و هم مجموعشان کمینه شود. در صورت وجود چندین جواب هر کدام از آنها را میتوانید چاپ کنید.
زیرمسئلهها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۰ | \( 1 \le n \le 100\) ,\( 1 \le a_i \le 1\ 000\) |
| ۲ | ۲۰ | \( 1 \le n \le 100\) ,\( 1 \le a_i \le 1\ 000\ 000\) |
| ۳ | ۳۰ | \( 1 \le n \le 500\) ,\( 1 \le a_i \le 10^{18}\) |
| ۴ | ۴۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
4
63 54 45 36
خروجی نمونه ۱
3
3 4 4 36
ورودی نمونه ۲
6
8 16 16 1393 6 19
خروجی نمونه ۲
6
0 1 1 1 6 19
۲۴امین دوره المپیاد کامپیوتر - آزمون هفتم - ۱۳۹۳/۰۶/۱۹