Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۸:سوال ۹

PGU

در دانشگاه خلیج فارس مسابقه‌ای بین قوی‌ترین گروه به نام الف و ضعیف‌ترین گروه به نام ب برقرار می‌باشد. تیم داوران در ابتدای کار از لوح مسابقه که شامل چند معادله می‌باشد، تعدادی را انتخاب کرده و به تیم الف می‌دهد. علاوه بر آن‌ها دو عدد ‎M‎ و ‎N (1N,M)‎ را نیز به آن‌ها می‌دهند.

تیم الف همه معادلات را به دلخواه خود به نامعادله تغییر می‌دهد. سپس داوران دو عدد تصادفی ‎A‎ و ‎B‎ در بازه‌ی ‎[231,2311]‎ تولید می‌کنند. در صورتی که دو عدد ‎A‎ و ‎B‎ حتی در یک نامعادله‌ی محصول کار تیم الف صدق نکرد، بازی تمام می‌شود.

در صورتی که دو عدد ‎A‎ و ‎B‎ در نامعادلات صدق بکنند اگر ‎A‎ در بازه‌ی بسته‌ی ‎[0,M]‎ و ‎B‎ در بازه‌ی بسته‌ی ‎[0,N]‎ باشد، تیم الف برنده، و در غیر این‌صورت (‎A‎ یا ‎B‎ در بازه‌ی مورد نظر نباشند) تیم ب برنده خواهد شد.

به منظور سادگی فرض کنید معادلات به صورت خطی و در حالت کلی به شکل ‎xA+yB=c‎ باشند که ‎x,y{1,1}‎ و ‎cZ‎. تیم الف می‌خواهد با داشتن معادلات انتخابی داوران و دو عدد ‎M‎ و ‎N‎ جهت نامعادلات را به صورتی تعیین کند که امکان برنده شدن تیم ب وجود نداشته باشد و همچنین احتمال برنده شدن خود (تیم الف) را بیشینه کند.

ورودی

  • هر ورودی شامل دو بخش می‌باشد.
  • بخش نخست توصیف معادلات در لوح مسابقه می‌باشد.
    • این بخش با یک عدد ‎L‎ که تعداد معادلات در لوح را نشان می‌دهد شروع می‌شود.
    • در ‎L‎ سطر بعدی در سطر ‎i‎ام (با شروع از ‎۱‎) سه عدد ‎x‎، ‎y‎، و ‎c‎ آمده است که معادله‌ی ‎i‎ام را مشخص می‌کنند.
  • در بخش دوم ‎k‎ مسابقه با استفاده از بخش نخست توصیف شده است.
    • سطر اول بخش دوم شامل عدد ‎k‎ می‌باشد.
    • سپس ‎k‎ مسابقه در ادامه توصیف شده‌اند.
    • مسابقه‌ی ‎i‎ام در دو سطر توصیف می‌شود.
      • سطر اول شامل سه عدد ‎M‎، ‎N‎، و ‎T‎ می‌باشد.
      • سطر دوم شامل ‎2T‎ عدد pj (‎ pj<pj+1‎ و ‎1j2T‎ و ‎1pjL‎) می‌باشد.
      • اعداد ‎pj‎ معادلات مسابقه‌ی ‎i‎ام را نشان می‌دهد که شامل معادلاتی می‌باشد که اندیسشان در ‎S=1lT[p2l1,p2l] ‎ ([pa,pb] بازه‌ی بسته ‎pb‎ و‎pa‎ را نشان می‌دهد) باشد.
  • 2L100000‎ و ‎1k10

خروجی

در خروجی به ازای هر مسابقه در یک سطر احتمال برنده شدن تیم الف (با توجه به شرایط مساله) ضربدر ‎265‎ کرده، سپس گرد کنید و بنویسید. (فرض کنید همیشه جوابی با احتمال بیش از صفر برای تیم الف وجود دارد.)

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4
1 1 5
1 1 15
1 -1 5
1 -1 -5
1
10 10 1
1 4
100‎

ابزار صفحه