در دانشگاه خلیج فارس مسابقهای بین قویترین گروه به نام الف و ضعیفترین گروه به نام ب برقرار میباشد. تیم داوران در ابتدای کار از لوح مسابقه که شامل چند معادله میباشد، تعدادی را انتخاب کرده و به تیم الف میدهد. علاوه بر آنها دو عدد $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 |