المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۴۷

Worldcup

‎$n$‎ کشور متقاضی برگزاری مسابقات جام جهانی فوتبال هستند. میزبان مسابقات به صورت زیر انتخاب می شود:

  • تا زمانی که حد اقل دو کاندیدا برای میزبانی مسابقات وجود دارد، دو کاندیدا به صورت تصادفی انتخاب می‌شود و با توجه به رای کمیته مسابقات، یکی از آن‌ها از لیست میزبان‌ها حذف می‌شود.
  • تیم باقی‌مانده در لیست به عنوان میزبان انتخاب می‌شود.

به ازای هر تیم ‎$i$‎ و ‎$j$‎ می‌دانیم در صورتی که کمیته بخواهد از میان این دو تیم یکی را انتخاب کند، کدام تیم حذف می شود.

‎ شما باید برنامه‌ای بنویسید که با گرفتن اطلاعات ورودی، تمام تیم‌هایی که شانس میزبانی مسابقات را دارند را به دست آورد.‎

ورودی

  • در سطر اول ورودی، عدد ‎$1 \leq n \leq 5000$‎ آمده است.
  • در ‎$n$‎ سطر بعدی، در هر سطر ‎$n$‎ کاراکتر آمده که ‎$j$‎امین کاراکتر سطر ‎$i+1$‎ام ورودی در صورتی ‎$1$‎ است که کمیته بین دو تیم ‎$i$‎ و ‎$j$‎ ، تیم ‎$j$‎ را از لیست حذف کند. در غیر این‌صورت کاراکتر ‎$j$‎ام سطر ‎$i+1$‎ام ورودی برابر با ‎$0$‎ خواهد بود.‎
  • همیشه ‎$i$‎امین کاراکتر سطر ‎$i+1$‎ام ورودی برابر با ‎$0$‎ است و کاراکتر ‎$i$‎ام سطر ‎$j+1$‎ام با کاراکتر ‎$j$‎ام سطر ‎$i+1$‎ ام متفاوت است.‎

خروجی

در سطر اول خروجی تعداد کاندیدای دارای شانس میزبانی و در سطر بعدی آن‌ها را به ترتیب صعودی چاپ نمایید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2
01
00
1
1
3
001
100
010
3
1 2 3

پاسخ

فرض کنید گراف ‎$G$‎ یک گراف ‎$n$‎ راسی کامل جهت‌دار باشد که جهت یال بین دو راس ‎$u$‎ و ‎$v$‎ به سمت راسی باشد که کمیته مسابقات در صورت انتخاب بین دو کشور ‎$u$‎ و ‎$v$‎ آن کشور را انتخاب می‌کند (و کشور دیگر را حذف می‌کند).

اگر کشور ‎$r$‎ برای میزبانی مسابقات انتخاب شده باشد، می‌دانیم به ازای هر راس ‎$u \neq r$‎ یک کشور ‎$f(u)$‎ وجود دارد که باعث حذف کشور ‎$u$‎ شده است. همچنین واضح است که یال بین دو راس ‎$u$‎ و ‎$f(u)$‎ به سمت ‎$f(u)$‎ است. فرض کنید از گراف ‎$G$‎ یال‌های بین ‎$u$‎ و ‎$f(u)$‎ ها را انتخاب کنیم و بقیه یال‌ها را حذف کنیم و گراف جدید را ‎$G'$‎ بنامیم. می توان نشان داد که گراف ‎$G'$‎ یک درخت ریشه دار به ریشه ‎$r$‎ است که تمام یال‌های آن به سمت ریشه است. پس از تمام رئوس گراف یک مسیر به سمت راس ‎$r$‎ وجود دارد‎.

همچنین در صورتی که تمام رئوس گراف مسیری به سمت راس ‎$r'$‎ داشته باشند، اجتماع این مسیرها گرافی شبیه به ‎$G'$‎ به ریشه ‎$r'$‎ تولید می‌کند که می‌توانیم با استفاده از آن طوری مراحل انتخاب کشور میزبان را بسازیم که کشور ‎$r'$‎میزبان مسابقات شود‎.

پس کشور ‎$u$‎ قابلیت میزبانی مسابقات را دارد اگر و فقط اگر در گراف ‎$G$‎ تمام رئوس مسیری به سمت راس ‎$u$‎ داشته باشند‎.

حال برای به‌دست آوردن تمام رئوسی که شرط بالا را دارند، کافیست گراف را به مولفه‌های قویاً همبند افراض کنیم و رئوس مولفه‌ای که به هیچ مولفه دیگر یالی ندارد را به عنوان جواب انتخاب کنیم‎. ‎

‎پیچیدگی

‎ افراض گراف به مولفه‌های قویاً همبند را می‌توان در زمان ‎$o(n+e)$‎ انجام داد. همچنین انتخاب مولفه‌ای که به مولفه‌های دیگر یالی ندارد را می‌توان در زمان ‎$o(e)$‎ انجام داد. پس سوال را می‌توان در زمان ‎$o(n+e) = o(n^2)$‎ حل کرد.


ابزار صفحه