Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:عملی:سوال ۱

عبور از بزرگ‌راه

مردی می‌خواهد از عرض یک بزرگ‌راه n بانده عبور کند. عبور از باند i ام بزرگ‌راه، ti واحد زمانی طول می‌کشد. همچنین به دلیل عبور ماشین، این باند در ki بازه‌ی زمانی Ii1، Ii2، … و Iik غیر قابل عبور است. بازه‌ی زمانی Iij شامل همه‌ی زمان‌های t که uijt<vij است می‌باشد. تنها محل‌هایی که پس از شروع حرکت، مرد می‌تواند در آن‌ها توقف کند، مرزهای بین باندها است. مرز بین باندهای i ام به باند i+1 ام تعلق دارد و بنابراین در زمان عبور ماشین از آن باند، مرد حق توقف در این مرز را ندارد. همچنین مرد حرکت خود را از باند یک بزرگ‌راه شروع می‌کند و هیچ‌گاه به باند با شماره‌ی پایین‌تر برنمی‌گردد.

برنامه‌ای بنویسید که این مرد را برای عبور، طوری راهنمایی کند که در اولین زمان ممکن به انتهای باند n ام برسد.

ورودي

در خط اول فایل ورودی n با مقدار بیشینه‌ی ۱۰۰ و پس از آن اطلاعات مربوط به باندها به ترتیب در n‌ خط آمده است. خط i+1 ام فایل شامل 2ki+2 عدد است. ui2،ui1،ki،ti، …، vi2،vi1،uik، …، vik عددهای درج شده در این خط هستند. در این میان ki یک عدد صحیح با حداکثر مقدار ۵۰ و بقیه‌ی مقادیر اعداد صحیح نابیش‌تر از ۲۰۰ هستند.

خروجي

در ابتدای فایل خروجی زمان رسیدن مرد به انتهای باند n ام و سپس در n تخط به ترتیب زمان شروع به حرکت از عرض باندها را بنویسید. (هر باند در یک خط.) توجه کنید که زمان اجرای برنامه نباید متجاوز از ۲۰ ثانیه باشد.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
3
3 2 5 15 9 20
1 1 0 12
2 0
‎15
9
12
13

ابزار صفحه