فهرست مندرجات
شیروانی‌های آسمان‌خراش
در یک شهر دوبعدی، $n$ آپارتمان به شکل مستطیل قرار دارند. ضلع پایین تمام آپارتمان‌ها روی زمین است و هر آپارتمان
به دو آپارتمان کناری‌اش (به‌جز سمت چپِ چپ‌ترین و سمت راستِ راست‌ترین) چسبیده است. یک نمونه از چنین شهری در شکل زیر مشاهده می‌شود:
به‌عبارت دقیق‌تر، اگر دیوارهای ابتدایی، مابین و انتهایی ساختمان‌ها در نقاط صحیح $0 = a_0 < a_1 < \cdots a_n$ و ارتفاع ساختمان‌ها اعداد
صحیح $h_0$ تا $h_{n-1}$ باشند، ساختمان $i$اُم ($0 \leq i \leq n-1$)، مستطیلی به طول $a_{i+1}-a_i$ و ارتفاع $h_i$ است که گوشه‌ی پایین چپ آن$(a_i, 0)$ است.
یک روز شهردار این شهر که از دور به شهر نگاه می‌کند (و نمایی مشابه شکل بالا را می‌بیند) به این نتیجه می‌رسد که ساختمان‌ها از دور چندان زیبا نیستند.
از این رو، به‌منظور زیباسازی شهر، شهردار تصمیم می‌گیرد که یک عدد صحیح $r$ در نظر بگیرد که $a_n = k\times r$ و تمام این $n$ ساختمان مستطیلی‌شکل را تخریب کند و به‌جای آن‌ها $k$ ساختمان به شکل ذوزنقه (ذوزنقه، یک چهارضلعی است که حداقل دو ضلع آن موازی باشند) قائم‌الزاویه (ذوزنقهی قائم الزاویه ذوزنقه‌ای است که حداقل یکی از زوایای آن قائمه باشد) بسازد که $5$ شرط زیر را داشته باشند:
- عرض هر ساختمان (فاصله‌ی بین $2$ دیوارش) دقیقاً $r$ باشد.
- تمامی دیوارهای ساختمان‌ها عمود بر سطح زمین بوده و ضلع پایین آن‌ها نیز، تماماً روی زمین باشد.
- شیروانی (سقف) هر ساختمان دقیقاً یک خط صاف (اریب یا موازی با زمین) باشد و نقطه ابتدایی شیروانی ساختمانِ $i$اُم (که طول دیوار سمت چپ آن نیز هست و ما آن را $y_i$ می‌نامیم)، دقیقاً همان نقطه انتهایی شیروانی ساختمان $i-1$ (دیوار سمت راست ساختمان چپی، در صورت وجود) باشد. نقطه ابتدایی شیروانی ساختمان صفرم می‌تواند هر نقطه دلخواهی (روی سطح زمین و یا بالای آن) باشد. به عبارت دقیق‌تر، شیروانی ساختمان $i$اُم ($0 \leq i \leq k-1$)، یک خط مستقیم از نقطه $(ir, y_i)$ تا نقطه $((i+1)r, y_{i+1})$ است.
- $y_i$ ها (نقاط برخورد شیروانی‌های مذکور) می‌توانند اعشاری باشند منتها باید تمام $y_i$ ها ($0 \leq i \leq n$) نامنفی باشند و حداقل یکی از $y_i$ها صفر باشد تا بارانِ رویِ سقفِ آن خانه و خانه مجاورش (در صورت وجود) و احیاناً تعداد دیگری از خانه‌ها روی زمین بریزد. ساختمانی که $y_i$ ابتدایی (یا انتهایی) آن صفر باشد، مثلث قائم‌الزاویه می‌شود که ما آن را نیز استثنائاً ذوزنقه حساب می‌کنیم!
- نهایتاً حجم مصالحی که برای ساختمان $i$ (که در بازه $[ir~..~(i+1)r]$ روی زمین ساخته می‌شود) برابر حجم مصالح همین بازه در حالت اوّلیه (ساختمان‌های مستطیلی) باشد. واضح است که این حجم مصالح ممکن است از تمام یا بخشی از یک یا چند ساختمان اوّلیه به دست بیاید.
با داشتن موقعیت و اندازه اوّلیه ساختمان‌ها، شهردار را در زیباسازی شهر یاری کنید!
ورودی
- در سطر اول ورودی، دو عدد $n$ و سپس $r$ نوشته شده‌است.
- در سطر بعدی $n$ عدد آمده‌است که عدد اوّل (از چپ)، $a_1$، عدد دوم $a_2$ و عدد $i$اُم $a_i$ است (بالطبّع، $a_0$ چون صفر است در ورودی داده نمی‌شود.)
- در سطر سوم نیز $n$ عدد آمده است که عدد اوّل $h_0$، عدد دوم $h_1$ و عدد $i$اُم، همان $h_{i-1}$ است.
- $1 \leq r, n \leq 50,000$
- $\frac{a_n}{r}$ یک عدد صحیح کوچک‌تر یا مساوی $50,000$ است.
- تمامی اعداد ورودی، صحیح و نامنفی بوده و کوچک‌تر یا مساوی $50,000$ هستند.
- اعداد خروجی می‌بایست تا $2$ رقم اعشار (گرد شده) چاپ شوند.
خروجی
- در سطر اوّل خروجی تعداد ساختمان‌های جدید ($k$) را بنویسید.
- در سطر بعدی، $k+1$ عدد بنویسید که عدد $i$ اُم، $y_{i-1}$ باشد.
- در صورتی که مسئله چندین جواب دارد، شما باید جوابی که در آن مقدار $y_0$ کم‌ترین است را چاپ کنید.
- در صورتی که مسئله جواب ندارد، تنها در یک سطر خروجی عبارت No Solution را چاپ کنید.
محدودیت‌ها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت