در دانشگاه خلیج فارس مسابقهای بین قویترین گروه به نام الف و ضعیفترین گروه به نام ب برقرار میباشد. تیم داوران در ابتدای کار از لوح مسابقه که شامل چند معادله میباشد، تعدادی را انتخاب کرده و به تیم الف میدهد. علاوه بر آنها دو عدد M و N (1\leq N, M) را نیز به آنها میدهند.
تیم الف همه معادلات را به دلخواه خود به نامعادله تغییر میدهد. سپس داوران دو عدد تصادفی A و B در بازهی [-2^{31}, 2^{31}-1] تولید میکنند. در صورتی که دو عدد A و B حتی در یک نامعادلهی محصول کار تیم الف صدق نکرد، بازی تمام میشود.
در صورتی که دو عدد A و B در نامعادلات صدق بکنند اگر A در بازهی بستهی [0, M] و B در بازهی بستهی [0, N] باشد، تیم الف برنده، و در غیر اینصورت (A یا B در بازهی مورد نظر نباشند) تیم ب برنده خواهد شد.
به منظور سادگی فرض کنید معادلات به صورت خطی و در حالت کلی به شکل xA+yB=c باشند که x,y\in\{1,-1\} و c\in Z. تیم الف میخواهد با داشتن معادلات انتخابی داوران و دو عدد M و N جهت نامعادلات را به صورتی تعیین کند که امکان برنده شدن تیم ب وجود نداشته باشد و همچنین احتمال برنده شدن خود (تیم الف) را بیشینه کند.
در خروجی به ازای هر مسابقه در یک سطر احتمال برنده شدن تیم الف (با توجه به شرایط مساله) ضربدر 2^{65} کرده، سپس گرد کنید و بنویسید. (فرض کنید همیشه جوابی با احتمال بیش از صفر برای تیم الف وجود دارد.)
ورودی نمونه | خروجی نمونه |
---|---|
4 1 1 5 1 1 15 1 -1 5 1 -1 -5 1 10 10 1 1 4 | 100 |