المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲:سوال ۳

مهمانی مدیر عامل

در یک شرکت بزرگ هر کارمند (غیر از مدیرعامل) یک رئیس مستقیم دارد و هرکدام از مدیران تعدادی کارمند را مستقیما زیر نظر و مدیریت خود دارد. مدیر عامل می‌خواهد تعدادی از کارمندان را به یک مهمانی دعوت کند و می‌خواهد این مهمانی از هر نظر موفق باشد. او به هر یک از کارمندان یک ضریب به نام «ضریب اجتماعی بودن» نسبت داده است و شرایطش برای این مهمانی به این صورت است:

  • هیچ کارمندی با رئیس مستقیم خود با هم در مهمانی شرکت نکنند.
  • مجموع ضریب اجتماعی بودن کلیه‌ی کارمندان شرکت کننده حداکثر باشد.
  • بدیهی است که مدیر عامل می‌خواهد خود در مهمانی‌اش شرکت کند.

فرض کنید فایل ورودی داده شده است که در سطر اول آن تعداد کارمندان شرکت و در $i$ امین سطر از سطرهای بعد، ابتدا ضریب اجتماعی بودن و تعداد کارمندان زیر نظر کارمند شماره‌ی $i$ و سپس شماره‌ی این کارمندان نوشته شده است. فرض کنید تعداد کارمندان از ۱۰۰ کم‌تر است و ضریب اجتماعی بودن هر کارمند عددی صحیح بین ۱ و ۱۰ است. فرض کنید که مدیر عامل هم به عنوان کارمند شماره‌ی ۱ در فایل ورودی قرار دارد.

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

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

ورودي نمونه خروجي نمونه
14
1 3 2 3 4
1 2 5 6
2 1 7
2 3 8 9 10
3 2 11 12
9 0
1 2 13 14
8 0
2 0
1 0
1 0
9 0
10 0
10 0
2 0
‎1
6
8
9
10
11
12
13
14
SUM OF THE PUBLIC RELATION NO. = 52‎

ابزار صفحه