فهرست مندرجات
آسان‌بر برقی
نزدیک غروب بود که آتش‌سوزی‌ای که در ساختمان شروع شده بود، تمام ساختمان را در بر گرفت. ساختمان تجاری و بلندی بود و تعداد زیادی آدم در طبقات مختلف آن گیرافتاده بودند. تنها راه فرار از طریق طبقه صفرم (و دویدن در خیابان) یا سقف ساختمان (طبقه آخر؛ از طریق بالگرد امداد) بود. از خبرها بر می‌آمد که تنها راه رسیدن به طبقه صفرم یا آخر ساختمان، استفاده از آسان‌بر (آسانسور) می‌باشد. $n$ آسان‌بر در ساختمان قرار داشت که هر کدام یا به سمت پایین در حرکت بود و یا به سمت بالا می‌رفت. شدت آتش طوری بود که آسان‌برها بعد از رسیدن به انتهای ساختمان (طبقه صفرم یا آخر) از کار می‌افتادند، ولی تنها نکته امیدوار کننده این بود که هر آسان‌بر در مسیر خود (دقّت کنید که آسان‌بر می‌تواند افرادی که در طبقه ابتدایی‌اش قرار دارند را نیز سوار کند) می‌توانست $k$ آدم را سوار کند و به طبقه صفرم یا آخر (بسته به جهت ثابت خود) ببرد. خوش‌بختانه با همت نیروی آتش‌نشانی، معلوم شد آدم‌هایی که در ساختمان هستند در چه طبقاتی قرار دارند و هم‌چنین آسان‌برهایی که در ساختمان هستند در چه طبقه‌ای می‌باشند و به کدام سمت در حرکتند. این ماموران بر آن شدند تا بیش‌ترین تعداد آدم را نجات دهند. در نتیجه قرار بر آن شد، که مشخص کنند هر آدم باید با چه آسان‌بری حرکت کند.
ورودی
- در سطر اول ورودی سه عدد $n$، تعداد آسان‌برها و سپس $m$، تعداد آدم‌های داخل ساختمان و نهایتاً $k$، گنجایش آسان‌برها آمده است.
- در سطر بعدی $m$ عدد آمده است که عدد $i$اُم این سطر طبقه‌ای را مشخص می‌کند که فرد $i$اُم در آن قرار دارد.
- در سطر بعدی $n$ عدد آمده است که عدد $i$اُم این سطر طبقه‌ی ابتدایی آسان‌بر $i$اُم را مشخص می‌کند.
- نهایتاً در سطر چهارم $n$ عدد $0$ یا $1$ آمده است که اگر عدد $i$اُم $0$ باشد یعنی آسان‌بر $i$اُم به سمت پایین حرکت می‌کند و اگر $1$ باشد، یعنی آسان‌بر $i$ام به سمت بالا حرکت می‌کند.
- $1 \leq n, m, k \leq 100,000$.
خروجی
- در سطر اول خروجی، بیش‌ترین تعداد آدمی را که می‌توان نجات داد، بنویسید.
- در سطر بعدی $m$ عدد بنویسید که عدد $i$اُم مشخص می‌کند آدم $i$اُم با چه آسان‌بری (شماره آسان‌برها از $1$ تا $n$ هستند) باید فرار کند. اگر آدم $i$اُم موفق به فرار نشده بود عدد $0$ را برای آن نفر بنویسید.
محدودیت‌ها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
