====== Rabbits ====== علی ‎$n$‎ خرگوش دارد و می‌خواهد از شهر A‎ به شهر B‎ برود‎. خرگوش ‎$i$‎ ام ‎$w_i$‎ کیلوگرم وزن دارد و هزینه حمل یک متر هر کیلوگرم خرگوش برابر با ‎$k$‎ است. همچنین بین دو شهر ‎A‎ و ‎B‎ ، ‎$n$‎ شهر وجود دارد که فاصله شهر ‎$i$‎ ام از شهر ‎A‎ برابر ‎$d_i$‎ متر است‎. ‎ در شهر ‎$i$‎ ام هر کیلو خرگوش را به قیمت ‎$p_i$‎ خریداری می‌کنند‎. ‎ علی می‌خواهد ‎$n$‎ خرگوش خود را در مسیر بفروشد طوری که در هر شهر دقیقاً یکی از آن‌ها را بفروشد‎. ‎ شما باید مشخص کنید که علی باید در هر شهر چه خرگوشی را بفروشد تا هزینه‌ای که به‌دست می‌آورد بیشینه باشد‎. ‎ ===== ورودی ===== * در سطر اول ورودی دو عدد ‎$1 \leq n \leq 1000$‎ و ‎$1 \leq k \leq 10^9$‎ آمده است .‎ * در سطر بعدی ‎$n$‎ عدد ‎$w_1$‎ تا ‎$w_n$‎ آمده است‎. * در سطر بعدی ‎$n$‎ عدد ‎$d_1$‎ تا ‎$d_n$‎ آمده است‎. * در سطر بعدی ‎$n$‎ عدد ‎$p_1$‎ تا ‎$p_n$‎ آمده است‎. ===== خروجی ===== ‎ در تنها سطر خروجی ‎$n$‎ عدد ‎$r_1$‎ تا ‎$r_n$‎ را چاپ کنید که نشان می‌دهد علی باید در شهر ‎$i$‎ ام خرگوش ‎$r_i$‎ را بفروشد‎. ‎ ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودي و خروجي نمونه ===== ^ ورودي نمونه ^ خروجي نمونه ^ |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$‎ رو با هم عوض کرد و جواب بهینه‌تر شود‎. ‎ تناقض‎! ‎ * [[سوال ۶۱|سوال بعد]] * [[سوال ۵۹|سوال قبل]]