فهرست مندرجات
Traitor
بر طبق یک سری اطلاعات موثق در سازمان امنیتی $ ACM $ یک خائن وجود دارد. سلسله مراتب سازمانی به این صورت است که هر شخص یک مدیر دارد. حداقل یک مدیر بالا‌رده هم وجود دارد که هیچ مدیری ندارد. منبع ما به صورت قطعی نمی‌داند که خائن کیست، ولی لیستی از افراد مظنون دارد. در نتیجه تنها چیزی که می‌دانیم وجود یک خائن در مجموعه و لیستی از افراد مظنون است. برای پیدا کردن کردن فرد خائن می‌خواهیم هر مظنون را توسط یک نفر تحت نظر بگیریم، به طوری که سه شرط زیر برقرار باشد.
- دو مظنون نمی‌توانند یکدیگر را تحت نظر قرار دهند.
- هر مظنون باید توسط مدیرش و یا یکی از کارمندان مستقیمش تحت نظر قرار گیرد.
- هیچ کس نمی‌تواند بیش از یک مظنون را تحت نظر بگیرد.
اگر بخواهیم تمامی شروط بالا را در نظر بگیریم شاید نتوانیم که همه‌ی مظنونین را تحت نظر بگیریم. شما باید برنامه‌ای بنویسید که ساختار سازمانی و لیست مظنونین را به عنوان ورودی دریافت کند و بیشینه تعداد مظنونینی که می‌توان تحت نظر قرار داد، را محاسبه کند. شکل زیر یک ساختار سازمانی را نشان می‌دهد که در آن دو مدیر بالا‌رده و در کل $11$ کارمند وجود دارد. کارمندان مظنون با رنگ تیره مشخص شده‌اند. یک انتساب به صورت شکل زیر است که $ 7 $ مظنون از $ 8 $مظنون تحت نظر گرفته شده‌اند. فلش از سمت کارمند $ x $ به سمت کارمند $ y $ به این معنا است که کارمند $ x $، کارمند $ y $ را تحت نظر گرفته است. می‌توان نشان داد که در این مثال هیچ انتسابی وجود ندارد که همه‌ی مظنونین را پوشش دهد.
ورودی
- سناریوهای مختلفی به عنوان ورودی داده می‌شود. در خط اول هر سناریو دو عدد صحیح داده شده است. اولی $ n (1 \leq n \leq 10000) $تعداد کارمندان و دومی $ k (1 \leq k \leq n) $ تعداد مظنونین است. کارمندان از $ 1 $ تا $ n $ شماره‌گذاری شده‌اند.
- در خط دوم $ n $ عدد داده شده است که $ i $ امین عدد تعداد مدیران کارمند $ i $ است. صفر بودن این عدد نیز به این معنا است که این کارمند مدیر بالا‌رتبه است.
- در خط سوم $ k $ عدد صحیح مثبت $ s_{1},s_{2},\ldots,s_{k} $ شماره های کارمندان مظنون را نشان می‌دهد. ورودی $ "0 0" $ با خاتمه می‌یابد که نباید پردازش گردد.
خروجی
خروجی برای هر سناریو در یک خط جداگانه درج می‌گردد که بیش‌ترین تعداد مظنونینی است که در یک انتساب می‌توان تحت نظر گرفت.
محدودیت‌ها
- محدودیت زمان: ۱۰ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 11 8 3 4 4 0 6 8 9 11 11 11 0 3 2 8 9 6 5 7 11 2 2 0 1 1 2 0 0 | 7 1 |
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
