Processing math: 31%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:تئوری:سوال ۱۸

تبدیل عدد

می‌خواهیم از عدد ‎1‎ به عدد ‎n‎ برسیم. در هر مرحله می‌توانیم یا عددمان را دوبرابر کنیم یا به آن یک واحد اضافه کنیم. هزینه‌ی هر کدام از این دو عمل نیز ‎1‎ است.

به ازای هر عدد ‎1xn‎ یک زیرمجموعه‌ی ‎Ax‎ از اعداد ‎1‎, ‎2‎, ‎\dots‎, ‎x-1‎ و یک عدد ‎0 \leq c_x \leq 10‎ نیز به ما داده‌اند که اگر در طول مراحل عدد ‎x‎ تولید شد و قبل از تولید ‎x‎ نیز حداقل یکی از اعضای ‎A_x‎ تولید شده بود ما باید هزینه‌ی اضافی ‎c_x‎ را بپردازیم. دقّت کنید که به‌ازای هر ‎x‎، ما هزینه‌ی ‎c_x‎ را حداکثر یک‌بار می‌پردازیم.

الگوریتمی چندجمله‌ای بر حسب ‎n‎ ارائه کنید تا با پرداخت کم‌ترین هزینه، با شروع از عدد ‎1‎، عدد ‎n‎ را تولید کند.


ابزار صفحه