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

در دوران دوره ۲۸ ایا شاز بسیار فعال شده بود و هر شب سوال جدید می‌گذاشت. پس از تحقیقات فراوان دوره ۱۰۲۸ ایا متوجه شدند که واحد ارزیابی سختی سوال در آن زمان نفس‌گیری بوده است. به این صورت که اگر میزان نفس‌گیری سوال $i$ ام $a_i$ باشد آنگاه فردی که آن را حل می‌کند طی فرایند حل سوال $a_i$ بار نفسش می‌گیرد. همچنین طبق آمار‌ها سوال $i$ ام را $b_i$ نفر حل کردند.

حالا شما باید به دوره ۱۰۲۸ ایا بگویید که در مجموع چند بار نفس‌ها گرفته شده است!

ورودی🔗

در خط اول عدد $n$ داده می‌شود که تعداد سوالات می‌باشد. در خط دوم $n$ عدد داده می‌شود که $i$ امین آنها $a_i$ است. در خط سوم هم $b_i$ داده می‌شود.

$1 \le n, a_i , b_i \le 100$

خروجی🔗

شما باید تعداد بار‌هایی که در مجموع نفس‌ها گرفته شده را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

2
1 2
3 4

خروجی نمونه ۱🔗

11

ورودی نمونه ۲🔗

3
3 1 4
8 3 3

خروجی نمونه ۲🔗

39

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

دوره ۱۰۲۸ ایا، دوره ۲۸ ایا را بسیار خفن می‌پنداشتند(زیرا دوره ۲۸ ایا واقعا خفن بودند). اعتقاد دوره ۱۰۲۸ ایا به خفونت دوره ۲۸ ایا چنان بود که فکر می‌کردند دوره ۲۸ ایا می‌توانستند حتی مساله توقف را حل کنند!

مساله توقف ( به انگلیسی : Halting problem ) مطرح می کند که آیا می توان برنامه ای نوشت که یک برنامه از ورودی بگیرد و تعیین کند که آیا برنامه متوقف می شود یا خیر. ثابت شده که در حالت کلی، الگوریتمی برای حل این مساله وجود ندارد.

مسئول دوره ۱۰۲۸ ایا برای اینکه اعتماد به نفس دوره ۱۰۲۸ ایا تقویت شود، نسخه ساده شده‌ای از مساله هالت را به آنها داد تا آنها فکر کنند مثل دوره ۲۸ ایا خفن هستند.

در این نسخه‌ ساده شده سه نوع دستور موجود است:

assign a = b + c
cout a
goto l

که در آن $a$ و $b$ و $c$ یک حرف کوچک انگلیسی (که نام یک متغیر است) یا یک عدد یک رقمی هستند و $l$ شماره خطی از برنامه است. تضمین می‌شود که بعد از assign متغیر a همیشه یک حرف کوچک انگلیسی است.

شما باید خط به خط برنامه را دنبال کنید، در صورتی که برنامه پایان‌ناپذیر است، $-1$ را چاپ کنید. در غیر این‌صورت خروجی این برنامه را چاپ کنید. در این برنامه cout به معنای چاپ کردن یک عدد یا یک متغیر است. goto به معنای پرش به یک خط خاص است (خط‌ها از ۱ شماره‌گذاری شده‌اند). assign a = b + c یعنی $b+c$ را در متغیر $a$ قرار بده. هر حرف کوچک انگلیسی نشان‌دهنده یک متغیر است و محتوای همه‌ متغیرها در ابتدا صفر می‌باشد.

با توجه به اینکه جواب مسئله ممکن است بزرگ شود شما باید باقی مانده خروجی بر $10^9+7$ را بگویید.

ورودی🔗

در ورودی یک برنامه به شما داده می‌شود.

در خط اول $n$ تعداد خط‌های برنامه و در $n$ خط بعد در هر خط یک دستور از برنامه داده می‌شود. $1 \le l \le n \le 100\ 000$

خروجی🔗

اگر برنامه داده‌شده تمام نمی‌شود، در تنها سطر خروجی $-1$ چاپ کنید.

در غیر اینصورت خروجی‌های برنامه‌ (به ازای هر cout) را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

2
assign a = 2 + 2
cout a

خروجی نمونه ۱🔗

4

ورودی نمونه ۲🔗

4
assign a = 1 + 0
cout a
assign a = a + a
goto 2

خروجی نمونه ۲🔗

-1

ورودی نمونه ۳🔗

7
cout 0
goto 5
cout 1
goto 7
cout 2
goto 3
cout 3

خروجی نمونه ۳🔗

0
2
1
3

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

دوره ۲۸ ایا بعضی وقت‌ها خسته می‌شدند. دوره ۱۰۲۸ ایا بعد از فهمیدن این موضوع می‌خواهند آن برای تخریب وجهه دوره ۲۸ ایا استفاده کنند. دوره ۲۸ ایا در زمان خستگی همه دور هم جمع می‌شدند و فعالیت روزانه استاد بزرگ را تماشا می‌کردند.

استاد بزرگ هر روز یک تکه چوب دارای $n$ مربع به هم چسبیده تهیه می‌کرد و در خانه $i$ ام آن عدد $a_i$ را می‌نوشت. پس از تهیه چوب استاد عملیات زیر را روی تمام مرز‌‌های مربع‌های متوالی انجام می‌داد ($n-1$ مرز داریم).

استاد با ذکر غوودا ضربه‌‌ای محکم به مرز می‌زد که این ضربه به احتمال $\frac{1}{2}$ چوب را می‌شکاند و به احتمال $\frac{1}{2}$ نمی‌شکاند (‌استاد در دوران پیری به سر می‌برد به همین دلیل بعضی وقت‌ها چوب نمی‌شکست).

آنگاه دوره ۲۸ ایا مات و مبهوت از مهارت استاد و به نشانه احترام جمع اعداد روی هر تکه چوب باقی‌مانده را بر سردر شاز نصب می‌کردند (برای مثال اگر $n = 3$ و اعداد روی تکه‌ها به ترتیب $17\ , 2\ , 3\$ بودند و ضربه‌ی استاد مرز بین اولین تکه و دومین تکه را نمی‌شکاند ولی مرز بین دومین تکه و سومین را می‌شکاند، دوره ۲۸ ایا اعداد $5\ ,17\$ را بر سر در شاز نصب می‌کردند).

دوره ۱۰۲۸ ایا برای اثبات خفونت خود می‌خواهند امیدریاضی تعداد اعداد متفاوتی که سر در شاز نصب می‌شود را بیابند (برای مثال تعداد اعضای متفاوت مجموعه‌ی $\{7, 1, 2, 7, 3, 5, 1, 1\}$ برابر $5$ است).

ثابت می‌شود که جواب مورد نظر را می توان به صورت کسر $\frac{P}{Q}$ نشان داد (که قابل ساده کردن نیست). از شما خواسته شده که $P.Q^{-1}$ را در پیمانه‌ $10^9+7$ خروجی دهید.

ورودی🔗

در خط اول ورودی عدد $n$ داده می‌شود. سپس در خط بعدی $n$ عدد طبیعی می‌آیند که $i$ امین آنها $a_i$ می‌باشد. $1 \le n \le 500$ $-10^{15} \le a_i \le 10^{15}$

خروجی🔗

امیدریاضی تعداد اعداد متفاوت نصب شده در سردر را به فرم $P.Q^{-1}$ در پیمانه $10^9+7$ خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

2
-77 14   

خروجی نمونه ۱🔗

500000005

به احتمال $\frac{1}{2}$ مجموعه ، $\{-63\}$

به احتمال $\frac{1}{2}$ مجموعه ، $\{-77,14\}$

بر سردر شاز نوشته می‌شوند پس جواب مسئله $\frac{1+2}{2}$ می‌باشد.

ورودی نمونه ۲🔗

3
1 2 3

خروجی نمونه ۲🔗

750000007

به احتمال $\frac{1}{4}$ مجموعه ، $\{6\}$

به احتمال $\frac{1}{4}$ مجموعه ، $\{1,5\}$

به احتمال $\frac{1}{4}$ مجموعه ، $\{3,3\}$

به احتمال $\frac{1}{4}$ مجموعه ، $\{1,2,3\}$

بر سر در شاز نوشته می‌شوند پس جواب مسئله $\frac{1+2+1+3}{4}$ می‌باشد.

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

در زمان دوره ۱۰۲۸ ایا ربات‌ها آنقدر پیشرفت کرد‌ه بودند که بتوانند کنترل جهان را بدست بگیرند! (همانطور که پیشگوی بزرگ دوره ۲۸ ایا پیش‌بینی کرده بود).

برای مقابله با این تهدید بزرگ تیم زبده‌ای از دوره ۱۰۲۸ ایا دست‌‌بکار شدند. طبق آخرین اخبار رسیده از جاسوس‌هایمان، ربات‌ها توانایی تولید ربات‌های دیگر را پیدا کرده‌اند. اما از آنجایی که اینکار برایشان سخت است، یک ربات به تنهایی نمی‌تواند یک ربات دیگر بسازد و هر ربات جدید را دقیقا دو ربات با همکاری یکدیگر می‌سازند. همچنین می‌دانیم که یک ربات جدید، دو ربات تولید‌کننده‌اش را پدر خود می‌داند.

دوره ۱۰۲۸ ایا به‌تازگی حمله موفقیت‌آمیزی به مقرر ربات‌ها داشته‌اند و طی این عملیات دو تا از ربات‌ها به نام $a$ و $b$ را گروگان گرفته‌اند و حالا می‌خواهند از ربات $a$ بازجویی کنند!

از آنجایی که ربات $a$ دهنش قرص قرص است، دوره ۱۰۲۸ ایا تصمیم گرفتند به روش‌های سخت تر رو بیاورند و ربات $a$ را تهدید به کشتن ربات $b$ کنند. (در حقیقت دوره ۱۰۲۸ ایا مهربان‌تر از این حرف‌ها هستند و هرگز حاضر نخواهند شد به $b$ آسیبی وارد کنند).

حالا دوره ۱۰۲۸ ایا برای اینکه بفهمند تهدیدشان چقدر کارساز خواهد بود نیاز دارند کوتاه‌ترین رابطه فامیلی $a$ با $b$ را بدانند.

ورودی🔗

در سطر اول $n$ (تعداد کل ربات‌ها) ، $a$ و $b$ داده می‌شود.

در $n$ سطر بعد دو عدد $par1_i$ و $par2_i$ که سازنده‌های ربات $i$ ام هستند، می‌آیند. همچنین اگر آن ربات توسط انسان‌ها تولید شده بود، به جای هر دو $-1$ می‌آید.

$1 \le n \le 100\ 000$ $-1 \le par1_i,par2_i \le i-1$ $par1_i \neq par2_i$ $a \neq b$

خروجی🔗

کوتاه‌ترین نسبت $a$ با $b$ را از لحاظ تعداد کلمات چاپ کنید. اگر چندین کوتاه‌ترین رابطه وجود داشت شما باید رابطه‌ای که از لحاظ ترتیب لغت‌نامه‌ای بزرگترین است را چاپ کنید!

توجه کنید که رابطه‌ای که در خروجی بیان می‌شود باید از زبان $a$ باشد.به عنوان مثال اگر $b$ سازنده $a$ باشد جواب pedar است. در صورتیکه $a$ و $b$ با هم هیچ رابطه فامیلی نداشتند فقط باید ‍‍No relationship! را چاپ کنید.

رابطه‌هایی که در خروجی می‌آیند:

مثال🔗

ورودی نمونه ۱🔗

10 8 4
-1 -1
-1 -1
-1 -1
2 1
-1 -1
1 5
-1 -1
1 2
6 3
5 2

خروجی نمونه ۱🔗

1
baradar 

ورودی نمونه ۲🔗

9 9 6
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
5 4
5 3
7 2
8 1

خروجی نمونه ۲🔗

2
amoo pedar 

ورودی نمونه ۳🔗

8 8 1
-1 -1
-1 -1
1 2
1 2
3 4
3 4
5 6
5 6

خروجی نمونه ۳🔗

3
pedar pedar pedar 

ورودی نمونه ۳🔗

2 1 2
-1 -1
-1 -1

خروجی نمونه ۳🔗

No relationship!

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

دوره ۱۰۲۸ ایا می‌خواستند از سطح دانش آموزانی که در آزمون های شاز در سال ۱۳۹۷ شرکت می‌کردند مطلع شوند. اما چون دوره ۲۸ ایا جزییات کامل رنکینگ‌ها را منتشر نکرده بودند، دوره ۱۰۲۸ ایا مجبور شدند تا رمز سرورها را به‌دست آورده و با استفاده از آن به رنکینگ‌های کامل دست یافته و سطح دانش‌آموزان را ارزیابی کنند. رمز سرورهای شاز در آن زمان یک جایگشت طولانی بود. دوره ۲۸ ایا که در تمام امور کارهایشان را گروهی انجام می‌دادند، انتخاب رمز را نیز مستثنی نکرده بودند. در زمان دوره ۲۸ ایا، $m$ نفر در دست‌اندرکاران شاز وجود داشتند ($8$ نفر اصلی و $m-8$ نفر دست‌های پشت پرده!) نفر $i$ ام از این افراد معتقد بود که اگر الگوی رمز مانند جایگشت $i$ ام باشد، رمز بسیار سخت است.

عملیات چیدن تعدادی عدد متمایز مثل $a_k$...$a_1$ طبق جایگشت $p_k$...$p_1$ به اینصورت تعریف می‌شود که ترتیب اعداد آرایه $a$ را طوری تغییر می‌دهیم که به ازای هر دو اندیس متمایز $1 \leq i,j \leq k$ داشته باشیم: $a_i<a_j$ برقرار است اگر و فقط اگر $p_i<p_j$ برقرار باشد.

مثلا اگر بخواهیم اعداد $\{8,7,4,11\}$ را طبق جایگشت $\{4,2,3,1\}$ بچینیم به $\{11,7,8,4\}$ تبدیل می‌شود‌.

دوره ۲۸ ایا طول رمز را برحسب اهمیت آن، $n$ انتخاب می‌کردند. سپس در هر مرحله یکی از افراد تعدادی عدد از اعداد باقی‌مانده (اعداد مجموعه $1$ تا $n$ که تا حالا کسی آنها را در رمز استفاده نکرده است) انتخاب می‌کرد و آن ها را طبق جایگشت خودش می‌چید‌ و سپس آن را به انتهای رمز به دست آمده تا‌کنون اضافه می‌کرد. همچنین یک نفر ممکن است چند بار از جایگشتش استفاده کرده و رمز را گسترش دهد. حال دوره ۱۰۲۸ ایا حدس‌هایی راجع به رمز سرورهای شاز زده‌اند. اما آن ها می خواهند ببینند حدسشان چقدر محتمل است. برای همین از شما می‌خواهند بپرسند که رمز مذکور به چند طریق توسط دوره ۲۸ ایا قابل ساخت است.

ورودی🔗

خط اول ورودی عدد $n$ و$m$ داده می‌شود. در خط بعد جایگشت $p$ داده می‌شود که نشان دهنده رمز شاز است. سپس در $m$ خط بعدی جایگشت ها به این‌صورت داده می‌شود. در ابتدا عدد $k_i$ و سپس یک جایگشت $k_i$ تایی ورودی داده می‌شود. $1 \le n, m , k_i \le 100\ 000$ تضمین می‌شود که مجموع $k_i$ ها از $100\ 000$ بیشتر نمی‌شود. توجه کنید که ممکن است دو نفر الگوی جایگشتی مشابهی داشته باشند!

خروجی🔗

خروجی تنها شامل یک عدد است که تعداد راه‌های مختلف تولید رمز $p$ در پیمانه $10^9+7$ می‌باشد (دو روش تولید رمز متفاوت‌اند اگر تعداد بار‌هایی که رمز گسترش داده شده در آن دو روش متفاوت باشد یا اینکه این تعداد مساوی باشد اما در مرحله‌ای مثل $i$‌ دو جایگشت متفاوت برای گسترش رمز استفاده شده باشند).

برای فهم بهتر ورودی نمونه ۳ را ببینید.

مثال🔗

ورودی نمونه ۱🔗

5 2
5 3 2 4 1 
4 4 1 3 2 
1 1 

خروجی نمونه ۱🔗

1

در اینجا نمی توان از نقشه اول استفاده کرد و تنها حالت ممکن ۵ بار استفاده از نقشه دوم است.

ورودی نمونه ۲🔗

10 2
1 2 3 4 5 6 7 8 9 10 
1 1 
2 1 2 

خروجی نمونه ۲🔗

89

ورودی نمونه ۳🔗

5 4
5 3 4 1 2
2 1 2 
2 1 2
2 2 1
3 3 1 2 

خروجی نمونه ۳🔗

2

ورودی نمونه ۴🔗

3 2
1 2 3
3 1 2 3
3 1 2 3

خروجی نمونه ۴🔗

1

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

اخیرا دوره ۱۰۲۸ ایا متوجه شده‌اند که دوره ۲۸ ایا در ضرب کردن در پیمانه مهارت فراوان داشتند. دوره ۲۸ ایا $n$ سوال اصلی داشتند که سختی سوال $i$ ام $a_i$ می باشد. آنها هر وقت سوال کم می آوردند یک زیرمجموعه از سوالات اصلی را با هم ترکیب می‌کردند و سوال دیگری بدست می‌‌آوردند که سختی آن برابر با ضرب سختی سوالات زیر مجموعه در پیمانه $p$ بود (دقت کنید که به طور خاص اگر آنها زیرمجموعه تهی را انتخاب می‌کردند سوالی با سختی ۱ به دست می‌آوردند). حالا دوره ۱۰۲۸ ایا سوالات اصلی را به طریقی گیر آوردند و می‌خواهند خفونت خود را به جهانیان ثابت کنند. بنابرین می‌خواهند تمام سوالات با سختی‌های متفاوتی که دوره ۲۸ ایا می‌توانستند طرح کنند را حل کنند اما قبل از آن از شما می خواهند بگویید به ازای هر سختی از $1$ تا $p-1$ آیا دوره ۲۸ ایا می‌توانستند سوالی با این سختی تولید کنند یا خیر. ضمنا ما از منبع موثقی می‌دانیم که p عددی اول است.

ورودی🔗

در خط اول عدد $n$ , $p$ می‌آید. در خط بعد $n$ عدد می‌آید که $i$ امین آن $a_i$ می‌باشد. $1 \le n, p \le 100\ 000$ $1 \le a_i \le p-1$

خروجی🔗

یک رشته $p-1$ بیتی دودویی خروجی دهید که بیت $i$ امش‌ (از چپ) ۱ است اگر و فقط اگر بتوان سوالی با سختی $i$ تولید کرد.

مثال🔗

ورودی نمونه ۱🔗

3 7
3 3 3 

خروجی نمونه ۱🔗

111001 

ورودی نمونه ۲🔗

5 19
16 10 2 2 4 

خروجی نمونه ۲🔗

110100111100110100