مسئله‌ The Trip

متن فارسی مسئله‌ The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge

✤    ۱۵ اردیبهشت ۱۳۹۶

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

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

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

  

ورودی برنامه

  [برگرد بالا]

ورودی برنامه شامل چندین مجموعه اطلاعات در مورد سفرهای مختلف دانشجویان است. هر مجموعه اطلاعات با عدد $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


نام: *  

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

پیام: *