سوال ۴
امیرمحمد و سینا با هم یک بازی می‌کنند. امیرمحمد در جاده‌ای راه می‌رود و سینا او را دنبال می‌کند. آن‌ها از قبل، شش اسکناس با ارزش‌های $\langle 8, 3, 6, 3, 10, 9 \rangle$ را به ترتیب (از چپ به راست) در طول جاده انداخته‌اند. هر کسی زودتر به اسکناسی برسد می‌تواند آن را بردارد، ولی فرد عقب‌تر از او جلو می‌زند و ترتیب دو نفر عوض می‌شود. اگر فرد جلوتر اسکناس را برندارد، فرد عقب‌تر می‌تواند اسکناس را بردارد و ترتیب دو نفر هم عوض نمی‌شود. هر کسی می‌خواهد بیش‌ترین پول را برای خود جمع کند. حداکثر پولی که امیرمحمد می‌تواند در انتها جمع کند چە‌قدر است؟
- ۲۲
- ۲۱
- ۲۴
- ۲۳
- ۲۵
راهنمایی
اگر فقط دو اسکناس روی زمین بود، امیرمحمد چه استراتژی‌ای در پیش می‌گرفت؟
راهنمایی
اگر مقدار $f(n)$ را برابر با بیش‌ترین مقدار پولی که امیرمحمد می‌تواند جمع کند تعریف کنیم، در حالتی که فقط $n$ اسکناس آخر روی زمین باشند؛ مقادیر $f(n)$ را به صورت بازگشتی محاسبه کنید.
(به عنوان مثال، $f(2)$ جواب مسئله به ازای دنباله‌ی
$\langle 10, 9 \rangle$
است که برابر با ۱۰ می‌باشد.)
راهنمایی
برای محاسبه‌ی $f(n)$، مقدار $g(n)$ را به طور مشابه برای حالتی که در ابتدا سینا جلوتر باشد تعریف کنید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
