الگوریتمستان

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

  

✤  مسئله‌ The Trip

آنچه در این نوشته می‌خوانید:
   •  مسئله‌ The Trip
       »  ورودی برنامه
       »  خروجی برنامه

گروهی از دانشجویان عضو کلوپی هستند که هر سال سفر به یک منطقه را در برنامه‌های خود دارد. ایندیاناپلیس، فینیکس، نَشویل، فیلادلفیا، سن خوزه و آتلانتا از جمله مناطقی هستند که در گذشته سفر انجام شده و این بهار نیز نوبت سفر به آیندهوون است.

این گروه دانشجویی توافق کرده‌اند که سهم هر کدام از نفرات در مخارج سفر با دیگر اعضا یکی باشد. برای رسیدن به این هدف، عملا امکان تقسیم خرج بین نفرات در هر هزینه وجود ندارد. به همین دلیل هر کدام از نفرات هزینه‌های مختلف از قبیل وعده‌های غذایی، اقامت و ایاب و ذهاب را پرداخت می‌کنند و پس از اتمام سفر، مجموع کل هزینه‌ها محاسبه شده و پول بین نفرات به قسمی رد و بدل می‌شود که همه به یک میزان در خرج مشارکت داشته باشند یا حداکثر یک سنت اختلاف وجود داشته باشد.

در گذشته این حساب و کتاب و تبادل پول کاری خسته‌کننده و زمان‌بر بود. کار شما یافتن حداقل میزان تبادل پول بین نفرات است به قسمی که همه به یک میزان یا حداکثر اختلاف یک سنت خرج کرده باشند.

  

ورودی برنامه

  [برگرد بالا]

ورودی برنامه شامل چندین مجموعه اطلاعات در مورد سفرهای مختلف دانشجویان است. هر مجموعه اطلاعات با عدد $n$ در یک سطر شروع می‌شود که بیانگر تعداد دانشجویان حاضر در سفر است. در $n$ خط بعدی نیز هزینه خرج شده هر کدام از این دانشجوها با واحد دلار و سنت آمده است که مقدار هر کدام بیش از 100000 دلار نیست. تعداد دانشجویان حاضر در سفر نیز بیش از 1000 نفر نیست.

انتهای ورودی با عدد صفر برای $n$ مشخص می‌شود.

  

3

10.00

20.00

30.00

4

15.00

15.01

3.00

3.01

0

  

خروجی برنامه

  [برگرد بالا]

به ازای هر ورودی یک سطر در خروجی چاپ شود که شامل حداقل تبادل پول برای برقراری توازن در خرج دانشجویان است.

  

$10.00

$11.99

  

Link: UVa Online Judge, 10137 - The Trip

مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته علوم کامپیوتر و فعال حوزه‌های برنامه‌نویسی پایتون، علم داده و یادگیری ماشین

algs.ir/spwa87e     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
       ✦   مسئله Encrypted SMS
آخرین نوشته‌ها
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14