Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

جمع کردن سیب

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

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

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

ورودي

در سطر اول فایل ورودی، N، تعداد سیب‌ها نوشته شده است و در هر یک از N سطر بعدی (Xi,Vi) قرار دارد که Vi سرعت سقوط سیب i ام است. در آخرین سطر فایل (X,V) مربوط به سبد نوشته شده است. تمام اعداد ورودی در محدوده‌ی 1200 هستند.

خروجي

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


ابزار صفحه