- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون عملی دوره ۲۰ المپیاد کامپیوتر
یوری پسر جومونگ می‌خواهد لذت مردم گوگوریو از زندگی را به حد اعلا برساند. در گوگوریو $n$ نفر زندگی می‌کنند و در انبارهای گوگوریو $m$ کیلو ترب وجود دارد. یوری برای بیشینه کردن لذت مردم، می‌خواهد تمام ترب‌ها را بین مردم تقسیم کند. هر فرد در گوگوریو با توجه به میزان تربی که به او می‌رسد خوشحال می‌شود(به وضوح هر چی بیشتر ترب به یک نفر برسد، بیشتر خوشحال می‌شود.)
فرض کنید فرد $i$ ام در گوگوریو با $x$ کیلو ترب، به میزان $s_i(x)$ شودوکی (شودوکی واحد خوشحالی مردم در گوگوریو می‌باشد) خوشحال می‌شود (تابع $s_i(x)$ یک تابع اکیدا صعودی بر حسب $x$ می‌باشد). همچنین رابطه زیر برای هر تابع $s_i$، به ازای هر $x$ و $y$ (که $ x < y $)، برقرار است:
$$ s_i(x) + s_i(y) \le s_i(x + 1) + s_i(y - 1) $$
هدف یوری بیشینه کردن مجموع لذتی است که مردم در گوگوریو می‌برند.
نحوه‌ی پیاده‌سازی برنامه‌ی این مسئله با سوال‌های معمول بسیار تفاوت دارد. به بخش کتاب‌خانه توجه کنید.
ورودی
در این سوال، ورودی توسط کتاب‌خانه از فایل ورودی خوانده می‌شود. دقت کنید هیچ چیزی توسط برنامه شما نباید از ورودی خوانده شود. فرمت فایل ورودی برای کتاب‌خانه ی مثالی که به شما داده‌ایم به شکل زیر است:
در سطر اول دو عدد $n$ و $m$ آمده‌است که $n$ جمعیت مردم گوگوریو و $m$ میزان (به کیلو) ترب موجود در انبارهای گوگوریو است.
$$1 \le m, n \le 1 \ 000\ 000 $$
خروجی
در این سوال شما باید بیشترین مجموع لذتی که مردم گوگوریو می‌توانند ببرند را به کتاب‌خانه گزارش دهید. دقت کنید که هیچ چیزی توسط برنامه شما نباید در خروجی نوشته شود.
زیرمسئله‌ها
| زیرمسئله | شماره‌ی تست‌ها | نمره | محدودیت |
|---|---|---|---|
| ۱ | ۱ تا ۵ | ۳۰ | $ n \le 500 $ |
| ۲ | ۶ تا ۲۰ | ۷۰ | بدون محدودیت اضافی |
کتاب‌خانه
باید این سوال را به زبان ++C پیاده‌سازی کنید.
کدهای مورد نیازتان در این فایل فشرده موجود هستند. توضیحات:
شما در این سوال باید برای دریافت اطلاعات تابع لذت افراد از کتاب‌خانه‌ای که در اختیار کد شما قرار داده می‌شود استفاده کنید. برای این منظور فایل‌های کتاب‌خانه‌ی lezatlib.h و lezatlib.cpp در اختیار شما قرار داده شده‌است. برای اینکه بتوانید از کتاب‌خانه مورد نظر استفاده کنید باید در بالای برنامه خود، کتاب‌خانه lezatlib.h را include کنید:
#include "lezatlib.h"
برای compile کردن برنامه خود می‌توانید از دستور زیر استفاده کنید:
g++ yourProgram.cpp lezatlib.cpp
همچنین توابعی با فرمت زیر در کتاب‌خانه قرار دارد:
Initialize();
int getN();
int getM();
int getLezat(int, int);
void reportSol(int);
شما باید در ابتدای برنامه خود، تابع initialize() را از کتاب‌خانه فراخوانی کنید؛ در غیر این صورت رفتار کتاب‌خانه غیرقابل استناد می‌باشد. بعد از آن با فراخوانی توابع getN() و getM() می‌توانید مقادیر $n$ و $m$ را از کتاب‌خانه بگیرید.
شما می‌توانید با فراخوانی تابع getLezat(l,x)، مقدار لذتی که فرد $i$ از داشتن $x$ کیلو ترب می‌برد را از کتاب‌خانه بپرسید (پارامتر اول، شماره فرد و پارامتر دوم میزان ترب را مشخص می‌کند). برای مثال:
int p = getLezat(3,5);
میزان لذتی که فرد ۳ از ۵ کیلو ترب می‌برد را می‌گوید.
در پایان باید مقدار جواب خود را با تابع reportSol(int) به کتاب‌خانه گزارش دهید. بعد از فراخوانی این تابع برنامه شما هیچ فعالیتی نباید انجام دهد.
یک نمونه برنامه‌ای که شما می‌توانید بفرستید: (فایل lezat.cpp در کدهایی که به شما دادیم.)
#include "lezatlib.h"
using namespace std;
int main() {
initialize();
int n = getN();
int m = getM();
int x = getLezat(n-1,m-1);
reportSol(x);
return 0;
}
دقت کنید که کتاب‌خانه‌ای که به شما به عنوان نمونه داده شده است، کتاب‌خانه‌ای نیست که برنامه‌ی شما با آن تست می‌شود و صرفاً جهت یک مثال به شما داده شده است.
ارسال پاسخ برای این سؤال