المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۸:g

Bribing FIPA

بنت در شرکت ایرانفون به عنوان یک برنامه نویس مشغول به کار است. رئیس ایرانفون هر سال به خوش اخلاق‌ترین کارمندانش جایزه بزرگی می‌دهد. بنت می‌خواهد امسال برنده این جایزه باشد. برای انتخاب برنده‌ها، ابتدا چند نفر کاندیدا می‌شوند. سپس رئیس نظر همه کارمندانی که کاندیدا نشده‌اند را می‌پرسد و به تمام کاندیداهایی که حداقل $m$ رای آورده باشند جایزه می‌دهد.

بنت، می‌خواهد با خریدن رأی بعضی از همکارانش، مطمئن شود که برنده خواهد بود. هر فرد قیمت خاصی برای رأیش قائل است، همچنین بعضی از افراد رئیسی دارند. اگر بنت رأی کسی را بخرد، تمام کسانی که به صورت مستقیم یا غیر مستقیم زیر‌دست او هستند نیز به بنت رأی خواهند داد.

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

ورودی

در ورودی چند سناریو آمده است. هر سناریو با خطی شامل دو عدد $n$ (تعداد افرادی که رأی می‌دهند) و m آغاز شده است. ($ 1 <= n <= 200, 0 <= m <= n $)

در $n$ خط بعد در هر خط ابتدا نام فرد $i$ام (رشته‌ای به طول حداکثر ۱۰۰ حرف) و سپس میزان پولی که بنت باید به او بدهد تا رأی او را بخرد آمده و بعد از آن نام تمام کارمندانی آمده است که رئیشان فرد $i$ام است.

خط آخر ورودی تنها شامل یک کاراکتر # است.

خروجی

برای هر سناریو،‌ در یک خط کمینه مقدار هزینه‌ای را که بنت باید خرج کند تا حداقل $m$ نفر به او رأی دهند را چاپ کنید.

محدودیت‌ها

  • محدودیت زمان: ۱۰ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودی نمونه خروجی نمونه
3 2
Aland 10
Boland 20 Aland
Coland 15
#
20

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه