المپدیا

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

ابزار کاربر

ابزار سایت


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

فهرست مندرجات

جمع کردن سیب

تعدادی سیب با سرعت‌های معینی (با صرف نظر از شتاب جاذبه) به زمین سقوط می‌کنند. روی زمین سبدی قرار دارد که می‌تواند با سرعت $V$ و به صورت افقی (چپ و راست) حرکت کند.

برنامه‌ای برای حرکت سبد بنویسید که بیش‌ترین تعداد سیب‌ها را جمع کند.

در لحظه شروع، سیب $i$ ام در مختصات $(X_i,10000)$ قرار دارد. (تمام سیب‌ها از ارتفاع ۱۰۰۰ شروع به سقوط می‌کنند.) و مختصات سبد نیز $(X,0)$ است. برای آن‌که سیب $i$ ام درون سبد بیفتد، سبد باید هم‌زمان با سیب به نقطه‌ی $(X_i,0)$ برسد و یا قبل از سیب به این نقطه رسیده و تا زمان رسیدن سیب، حرکت نکند.

ورودي

در سطر اول فایل ورودی، $N$، تعداد سیب‌ها نوشته شده است و در هر یک از $N$ سطر بعدی $(X_i,V_i)$ قرار دارد که $V_i$ سرعت سقوط سیب $i$ ام است. در آخرین سطر فایل $(X,V)$ مربوط به سبد نوشته شده است. تمام اعداد ورودی در محدوده‌ی $1…200$ هستند.

خروجي

در سطر اول فایل خروجی حداکثر تعداد سیب‌هایی که در سبد جمع شده‌اند و سپس در سطر $i+1$ ام شماره‌ی $i$ امین سیبی که وارد سبد شده را بنویسید.


ابزار صفحه