Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۶:عملی نهایی سوم:سوال ۲

Hands

در تورنمنت جهانی «نان‌بیار، کباب‌ببر»، ورزشکاران با قدرت دستهایشان شناخته می‌شوند. در این مسابقات، n ورزشکار شرکت‌ کرده‌اند که قدرت دست راست ورزشکار i-ام، ri و قدرت دست چپش li است. در این مسابقات، در هر مرحله، مسابقه‌ای بین دو ورزشکار انجام می‌شود و فرد بازنده از تورنمنت حذف می‌شود. بنابراین بعد از n1 مرحله، تنها یک فرد در تورنمنت باقی‌ می‌ماند که مدال طلای مسابقات را دریافت می‌کند.

اگر مسابقه‌ای بین ورزشکار i و j انجام شود، ورزشکار i شانس پیروزی در این مسابقه را دارد اگر li>rj و یا ri>lj باشد.

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

ورودی

در خط اول ورودی عدد طبیعی n، تعداد ورزشکاران، آمده است.

در هر یک از n خط بعدی، قدرت دست‌های ورزشکاران آمده است. در خط i از این خطوط، به ترتیب دو عدد طبیعی ri و li آمده است که نشان‌دهنده‌ی قدرت دست راست و دست چپ ورزشکار i است.

خروجی

در تنها خط خروجی یک رشته‌ی n حرفی از 0 و 1 چاپ کنید که 1 بودن حرف iام این رشته نشان‌دهنده‌ی این است که ورزشکار iام شانس قهرمانی دارد.

زیرمسئله‌ها

  • زیرمسئله اول (۱۲ نمره): n20
  • زیرمسئله دوم (۱۶ نمره): n200
  • زیرمسئله سوم (۲۸ نمره): n2000
  • زیرمسئله چهارم(۴۴ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • 1n2×105
  • 1li,ri2×n
  • تضمین می‌شود تمامی liها و riها متمایز هستند.

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

ورودی نمونه خروجی نمونه
2
1 2
3 4
01
4
1 8
6 7
5 4
3 2
1111

ابزار صفحه