Processing math: 75%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۶۰

Rabbits

علی ‎n‎ خرگوش دارد و می‌خواهد از شهر A‎ به شهر B‎ برود‎.

خرگوش ‎i‎ ام ‎wi‎ کیلوگرم وزن دارد و هزینه حمل یک متر هر کیلوگرم خرگوش برابر با ‎k‎ است. همچنین بین دو شهر ‎A‎ و ‎B‎ ، ‎n‎ شهر وجود دارد که فاصله شهر ‎i‎ ام از شهر ‎A‎ برابر ‎di‎ متر است‎. ‎

در شهر ‎i‎ ام هر کیلو خرگوش را به قیمت ‎pi‎ خریداری می‌کنند‎. ‎

علی می‌خواهد ‎n‎ خرگوش خود را در مسیر بفروشد طوری که در هر شهر دقیقاً یکی از آن‌ها را بفروشد‎. ‎ شما باید مشخص کنید که علی باید در هر شهر چه خرگوشی را بفروشد تا هزینه‌ای که به‌دست می‌آورد بیشینه باشد‎. ‎

ورودی

  • در سطر اول ورودی دو عدد ‎1n1000‎ و ‎1k109‎ آمده است .‎
  • در سطر بعدی ‎n‎ عدد ‎w1‎ تا ‎wn‎ آمده است‎.
  • در سطر بعدی ‎n‎ عدد ‎d1‎ تا ‎dn‎ آمده است‎.
  • در سطر بعدی ‎n‎ عدد ‎p1‎ تا ‎pn‎ آمده است‎.

خروجی

‎ در تنها سطر خروجی ‎n‎ عدد ‎r1‎ تا ‎rn‎ را چاپ کنید که نشان می‌دهد علی باید در شهر ‎i‎ ام خرگوش ‎ri‎ را بفروشد‎. ‎

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودي نمونه خروجي نمونه
3 1‎
10 20 15‎
‎10 20 30‎
‎50 70 60‎
‎3 2 1

پاسخ

راه‌حل این سوال greedy ‎(حریصانه)‎ است. نکته کلیدی در حل سؤال این است که اگر ‎1‎ کیلوگرم خرگوش در شهر ‎i‎ ام فروخته شود مقدار سود ما از آن ثابت و مستقل از باقی و برابر با ‎(p_i‎ + ‎d_i ‎ -‎k)‎ است که آن را ارزش آن شهر می‌نامیم. تنها محدودیت این است که یک خرگوش باید به طور کامل در یک شهر و در هر شهر فقط یک خرگوش فروخته شود. راه حل حریصانه بدین صورت است که شهر‌ها را بر اساس ارزش و خرگوش‌ها را بر اساس وزن (هر دو از بزرگ به کوچک) مرتب کرده و به ترتیب با هم جفت کرده. پیچیدگی الگوریتم هم برابر با ‎O(n \log n)‎ است که مربوط به مرتب کردن است‎. ‎

برای اثبات الگوریتم فرض کنید که جواب ما بهینه نباشد. جواب ما و بهینه را در نظر می‌گیریم و هر دو را بر حسب ارزش شهرها مرتب کرده (هر دو از بزرگ به کوچک) و اولین جایی که با هم فرق دارن را در نظر بگیرید. خرگوشی که با این شهر در جواب بهینه جور شده ‎a‎ و در جواب ما ‎b‎ می‌نامیم. وزن ‎b > a‎ است. اگر در جواب بهینه جای ‎b‎ ، ‎a‎ را عوض کنیم به اندازه ‎b-a‎ ارزش این شهر سود می‌کنیم پس می توان این ‎2‎ رو با هم عوض کرد و جواب بهینه‌تر شود‎. ‎

تناقض‎! ‎


ابزار صفحه