در شهر ‎«اتوپیا» $n$‎ نفر با نام‌های ‎$p_1, \ldots, p_n$‎ زندگی می‌کنند. ‎«پدر خوانده‎ «‎ $n$ عدد آبنبات دارد و می‌خواهد این آبنبات‌ها را به مردم بیچاره بفروشد. او می‌داند که برای هر ‎$1 \leq i \leq n$‎ ‎‎ نفر $p_i$ حاضر است ‎$b_i$‎ تومان پول، برای یک آبنبات بپردازد ‎($0 \leq b_i$)‎. در حقیقت ‎$b_i$‎ میزان علاقه‌ی ‎$p_i$‎ به آبنبات است. هم‌چنین بین هر دو عضو دلخواه از مردم این شهر، مثل ‎$p_i$‎ و ‎$p_j$‎ یک رابطه دوستی وجود دارد. میزان استحکام این رابطه دوستی را با عددی نامنفی به شکل ‎$w_{i,j}$‎ نشان می‌دهیم، در ضمن ‎$w_{i,j} = w_{j,i}$‎ . اگر ‎$p_i$‎ قبل از ‎$p_j$‎ آبنبات بخرد، میزان علاقه‌ی ‎$p_j$‎ به آبنبات به اندازه ‎$w_{i,j}$‎ افزایش می‌یابد.

پدرخوانده برای فروش آبنبات‌ها گوشه‌ی خانه‌اش می‌نشیند. او می‌داند که در روز اول ‎$p_1$‎ ، در روز دوم ‎$p_2$‎ و … در روز ‎$n$‎ اُم ‎$p_n$‎ به سراغش می‌آیند تا از او آبنبات بخرند (هر کس حداکثر یک آبنبات از پدرخوانده می‌خرد). قبل از شروع روز اول، پدر خوانده می‌خواهد یک قیمت ثابت برای آبنبات‌ها مشخص کند (این قیمت را ‎$x$‎ می‌نامیم). در روز ‎$i$‎اُم، ‎$p_i$‎ در صورتی آبنبات می‌خرد که میزان علاقه‌اش، بیش‌تر یا مساوی ‎$x$‎ باشد. پدرخوانده در ازای هر آبنباتی که بفروشد، ‎$x$‎ تومان سود می‌کند.

حال الگوریتمی ارائه دهید تا با دریافت ‎$n$‎ و ‎$b_1, \ldots, b_n$‎ و هم‌چنین میزان استحکام روابط دوستی، مقدار ‎$x$‎ را طوری مشخص کند که پس از ‎$n$‎ روز، پدرخوانده بیش‌ترین سود ممکن را برده باشد. زمان اجرای الگوریتم شما باید از ‎$O(n^2)$‎ باشد.

• سوال بعد
• سوال قبل