المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۷:سوال هفت

سفر دوستان

$n$۲ تا دوست دسته‌جمعی به مسافرت رفته‌اند. در طول مسافرت تعدادی «تبادل پول» بین آن‌ها صورت می‌گیرد. در هر تبادل پول٬ یک نفر می‌تواند به یک نفر دیگر مقداری پول بدهد. بعد از این که مسافرت تمام شد و این $n$۲ نفر به خانه‌هایشان بازگشتند٬ معلوم شد که درست $n$ نفر از آن‌ها در این مسافرت ضرر کرده‌اند (یعنی مقدار پولی که به بقیه داده‌اند٬ بیش‌تر از مقداری است که از بقیه گرفته‌اند) و $n$ نفر دیگر سود کرده‌اند.

ما می‌دانیم که این $n$۲ نفر در خانه‌هایشان هر چه‌قدر که بخواهند پول دارند. با توجه به این موضوع٬ می‌خواهیم بین این $n$۲ نفر تعدادی تبادل پول دیگر ترتیب دهیم. هدف این است که بعد از انجام تبادل پول‌هایی که در این مرحله ترتیب داده‌ایم٬ هیچ‌کس وجود نداشته باشد که سود٬ یا ضرر کرده باشد (به عبارت دیگر این $n$۲ نفر «بی‌حساب» شوند).

کوچک‌ترین $x$ای را بیابید که همیشه بتوان با انجام حداکثر $x$ تبادل پول٬ این $n$۲ نفر را بی‌حساب کرد.


ابزار صفحه