المپدیا

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

ابزار کاربر

ابزار سایت


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

محمد حریص

محمد و حسین مشغول تصحیح برگه‌های مرحله‌ی دوم المپیاد هستند. محمد که فرد حریصی است می‌خواهد پول بیش‌تری به‌دست آورد به ازای تصحیح هر برگه پول ثابتی می‌دهند. یعنی هدف محمد این است که تا آنجا که می‌تواند برگه‌های بیش‌تری تصحیح کند. فرض کنید برگه‌ها در ابتدا با یک ترتیب اولیه چیده شده است و زمان تصحیح هر برگه مشخص است. هر فرد می‌تواند در ابتدای ثانیه یک برگه بردارد (به شرطی که مشغول تصحیح برگه‌ای نباشد) و در هر ثانیه می‌توان حداکثر ۱ برگه برداشت محمد فرد زرنگی است و اگر در ابتدای ثانیه فعلی بردارد یا برداشتن برگه را به ثانیه بعد موکول کند. حسین فرد صادقی است و به محض این‌که تصحیح برگه خود را تمام کرد اگر بتواند (محمد اجازه بدهد) برگه بعدی را برمی‌دارد ولی محمد این طور نیست و بعد از تصحیح برگه‌ها می‌تواند به مقدار دلخواه صبر کند. محمد می‌خواهد طوری زمان‌بندی کند که حداکثر برگه ممکن را بردارد.

ورودی

در سطر اول فایل ورودی عدد $n\Leftarrow 500000$ تعداد برگه‌ها آمده است. (توجه کنید این برنامه تا زمانی که شرکت کنندگان مرحله دوم از $500000$ کم‌تر است کار می‌کند) در سطر بعد $n$ عدد آمده که عدد $i$ ام زمان تصحیح برگه $i$ ام در واحد ثانیه است (زمان‌ها از ۴۱ کم‌تر هستند چون اگر تصحیح یک برگه بیش از ۴۰ ثانیه شد به او ۰ می‌دهیم ولی از ۰ بیش‌تر است)

خروجی

در فایل خروجی تعداد حداکثر برگه‌هایی که محمد می‌تواند تصحیح کند آمده است.

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

ورودي نمونه خروجي نمونه
5
4 1 1 1 1
4‎

ابزار صفحه