فهرست مندرجات

قیمت نفت

قیمت نفت در بازارهای بورس تابع فاکتورهای زیادی است. یکی از این فاکتورها ‎«چشم و هم چشمی‎» میان کمپانی‌ها و کشورهای فعّال در بورس است‎!‎ برای مثال ممکن‌ست کشور بلیز‎ (یکی از کشورهای آمریکای لاتین که جمعیتش کمی بیش‌تر از باشگاه دانش‌پژوهان جوان است‎!‎) به‌تنهایی حاضر باشد نفت دریای شمال را حداکثر به‌قیمت بشکه‌ای ‎۸۰‎ دلار بخرد اما وقتی ببیند مثلاً ونزوئلا، اوگاندا، جزایر قناری، ساحل عاج و زامبیا (‎که مثلاً رقیب‌های اقتصادی بلیز است!)‎ دارند نفت می‌خرد، حاضر می‌شود تا ‎۸۵‎ دلار هم برای هر بشکه نفت بدهد. در سوی دیگر، کشورهای نفت‌خیز که فروشنده‌ی نفت هستند و از رقابت‌های اقتصادی میان کشورها خبر دارند، دوست دارند حداکثر فروش با سود مناسب را کرده و سود زیادی را در این میان به‌دست بیاورند.

آقای ‎«زی» (که اکسیر جوانی‌اش را نتوانست بسازد اما چیز دیگری ساخت و به خورد آقای ‎«کا»‎ داد و با قایق او فرار کرد‎(!‎ مشاور اقتصادی یک کمپانی بزرگ فروشنده‌ی نفت است. یک روز صبح رئیس کمپانی از او خواست تا با دانستن روابط اقتصادی میان کشورهای خریدار نفت و حداکثر ‎«ارزش اوّلیه‌ی نفت» (‎حداکثر پولی که آن کشور حاضرست در ابتدای کار و پیش از ‎«چشم و هم‌چشمی»ها برای نفت بپردازد) تک‌تک کشورها، یک قیمت ثابت و کلّی برای فروش نفت تعیین کند.

آقای ‎«زی»‎ می‌داند که هرگاه کشور ‎$X$‎ اقدام به خرید نفت کند، ارزش نفت در نزد هر کدام از کشورهایی که با ‎$X$‎ رقابت دارند و هنوز نفت نخریده‌اند، یک دلار افزایش می‌یابد. هم‌چنین هر کشور حداکثر یک‌بار اقدام به خرید نفت می‌کند و کشوری که ارزش‎ نفت (که با خرید نفت توسّط رقبایش افزایش می‌یابد) برایش بیش‌تر یا مساوی قیمت‎ نفت (که همواره ثابت است) بشود، در صورتی که هنوز نفت نخریده باشد، بلافاصله اقدام به‌خرید نفت می‌کند.

طبق اطلاعات داده شده به آقای ‎«زی»، در صورتی که قیمت نفت برابر ‎$V$‎ دلار باشد و در پایان کار ‎$n$‎ کشور نفت بخرند، سود نهایی کمپانی برابر ‎$nV$‎ می‌شود.

به آقای ‎«زی»‎ کمک کنید و برنامه‌ای بنویسید تا با دریافت ارزش اوّلیه‌ی نفت کشورها و رقابت‌های اقتصادی بین‌شان، قیمت نفت را طوری تعیین کند که بیش‌ترین سود عاید کمپانی بشود.

‎ورودی

‎‎خروجی

در تنها سطر خروجی بهترین قیمت اوّلیه‌ی نفت را بنویسید که بیش‌ترین سود (حاصل‌ضرب قیمت‌اوّلیه در تعداد کل کشورهایی که نفت می‌خرند) را به کمپانی می‌رساند.

محدودیت‌ها

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

ورودي نمونه خروجي نمونه
3
8 9 10
3
1 3
‎1 2
2 3‎
‎30‎
4
4 3 2 1
5
‎2 1
‎4 1
‎1 4‎
‎4 2
‎3 4‎
‎‎12‎