رمزنگاری یکی از باحال ترین فیلدهای ریاضیه که همیشه تکنیک‌های مختلفش و حل کردنشون برای ریاضیدان‌ها جالب بوده.

پس چرا ما هم یه سوال برای دست گرمی نداشته باشیم؟ :))

هر موقع هم بحث رمزنگاری می‌شه, یه سری عدد می‌بینیم و قراره یه جوری از این عددا یه معنی دراریم. خب این دفعه هم همینه :))))

توی ورودی یه متن و یه سری عدد به شما داده می‌شه و شما باید از این متن و با این اعداد، یه کلیدی رو بدست بیارین. عددها به صورت حرف:کلمه وارد می‌شن و باید این حروف رو کنار هم بذارین و به عنوان خروجی چاپ کنین.

ورودی🔗

ورودی شامل دو خط هست که خط اول متن و خط دوم رمزمون هست.

خروجی🔗

خروجی باید کلمه کلید بدست اومده از ورودی با حروف بزرگ باشه.

*برای بهتر متوجه شدن مثال‌ها رو ببینین*

مثال🔗

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

Why are the people not dealing with their problems at this point?
1:3 2:1 4:5 6:1 10:1

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

YALDA

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

Hosting this contest was such a pleasure and it was so fun.
3:1 4:3 7:4 7:6 9:2

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

CSAUT

• محدودیت زمان: 0.25 ثانیه

آرین خیلی به اعداد اول علاقه داره. مخصوصا اعداد ۲ و ۳ و ۵. می‌خواد همه اعدادی که از ضرب این عددا به وجود میان رو پیدا کنه ولی این کار دستی خیلی سخته. پس باید یه راهی پیدا کنه که خیلی راحت و سریع nامین عدد از مجموعه اعداد بالا رو پیدا کنه. برای این کار به آرین کمک کن :)))

ورودی🔗

ورودی تنها شامل یک خط است که در آن عدد طبیعی $n$ آمده است. $1 \le n \le 1690$

خروجی🔗

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

مثال🔗

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

8

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

9

$[1, 2, 3, 4, 5, 6, 8, 9]$

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

1

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

1

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

جوانه یک رشته‌ی باینری $S$ به طول $n$ دارد.

جوانه در هر حرکت می تواند یک زیر رشته به طول حداقل $k$ از رشته‌اش را در نظر گرفته و همه‌ی اعداد زیر رشته را برعکس کند. (یک‌ها را به صفر و صفرها را به یک تبدیل کند.)

بزرگ‌ترین $k$ ای را پیدا کنید که جوانه بتواند با عملیات بالا همه‌ی اعداد رشته را صفر کند.

ورودی🔗

در تنها خط ورودی رشته‌ی باینری $S$ داده شده‌است. $1 \le |S| \le 10^5$

خروجی🔗

در تنها خط خروجی $k$ مورد نظر را چاپ کنید.

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

010

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

2

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

100000000

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

8

رها و آرین دارن تو حیاط آکادمی یاسان با یه سری توپ، یه بازی با اعداد می‌کنن، شرح بازی: روی میز 2k توپ کنار هم چیده شده‌است که روی هر کدام وزن آن نوشته شده. در هر مرحله، هر نفر یا توپ اول یا توپ آخر را بر می‌دارد و داخل کیفش می‌گذارد. در آخر هر کسی که جمع وزن توپ‌هایش بیشتر بود برنده است. رها شروع کننده بازی است. وزن توپ‌ها را به عنوان ورودی به شما می‌دهیم. برای وزن‌های داده شده چه کسی می‌تواند کاری کند که بازنده نباشد؟

ورودی🔗

ورودی شامل دو خط است که در خط اول n تعداد توپ‌ها و در خط بعد وزن توپ‌ها با فاصله به شما داده می‌شود.

خروجی🔗

نام بازیکنی که می‌تواند در هر بازی کاری کند که نبازد را به عنوان خروجی چاپ کنید. اگر رها بود RAHA و اگر آرین بود ARIAN.

مثال🔗

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

8
1 2 4 5 6 7 3 6

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

RAHA

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

این روزها آرین و رها درحال راه‌اندازی شرکتی نوپا هستند. امّا مثل همیشه اختلاف نظر پیدا کرده‌اند، این بار بر سر نامِ شرکت. اشکان به آن‌ها پیشنهاد می‌دهد بازی‌ای انجام دهند و نتیجه‌ی بازی اسم شرکت باشد.

قبل از شروع بازی اشکان یک رشته‌ی $n$ حرفی به آرین و یک رشته‌ی $n$ حرفی به رها می‌دهد. آرین شروع کننده‌ی بازی است و در ابتدا نام شرکت به صورت $n$ تا جای‌خالی در نظر گرفته شده.(آرین و رها از رشته های یکدیگر مطلع هستند.)

در هر مرحله فردی که نوبت اوست از رشته‌ای که اشکان به او داده حرفی را انتخاب می‌کند و در یکی از جای‌خالی‌های اسم نهایی قرار می‌دهد سپس آن حرف را از رشته خود حذف می‌کند.

از نظر آرین اسمی ایده آل است که از نظر الفبایی تا حدّامکان کوچک باشد و از نظر رها اسم ایده آل از نظر الفبایی تا حدّ امکان بزرگ است.

اگر هردوی آن‌ها بهترین بازی خود را انجام دهند, نام شرکت چه خواهد بود؟

ورودی🔗

ورودی دارای دو خط است که در هر خط رشته‌ای از حروف کوچک انگلیسی به طول $n$ قرار دارد.

خط اول رشته‌ای که اشکان به آرین داده است و خط دوم رشته‌‌ای که اشکان به رها داده. $1 \leq n \leq 10^5$

خروجی🔗

در خروجی رشته‌ای به طول $n$ خواسته‌ می‌شود که اسم نهایی شرکت است.

مثال🔗

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

tinkoff
zscoder

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

fzfsirk

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

xxxxxx
xxxxxx

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

xxxxxx

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

آرین برای یلدا یه مهمونی بزرگ گرفته و تمام دوستاش رو دعوت کرده. دوستای آرین هیچ خوراکی دیگری را به اندازه‌ی آب نبات دوست ندارند!

صبح امروز آرین $m$ آب نبات $(1 \le m \le 10^5)$ با طعم و شرکت‌های مختلف خرید. متاسفانه آرین از هر طعم مختلف فقط یک عدد آب نبات خریده است. هر یک از $n$ دوست آرین $(1 \le n \le 10^5)$ ، یک طعم از آب نبات را دوست دارد و یک طعم دیگر را نیز بدش نمی‌آید و بقیه‌ی طعم‌ها را دوست ندارد. وقتی نوبت به یک شخص می‌رسد تا آب نباتش را بردارد، یکی از ۳ اتفاق زیر ممکن است بیفتد:

1. اگر آب نباتی که دوست دارد موجود باشد، آن را برمی‌دارد و خوشحال صحنه را ترک می‌کند و به رقصش می‌پردازد.
2. در غیر این صورت، اگر آب نباتی که بدش نمی‌آید موجود باشد، آن را برمی‌دارد و خوشحال صحنه را ترک می‌کند و باز هم به صحنه رقص می‌رود.
3. در غیر این صورت، آب نباتی برنمی‌دارد و ناراحت مهمانی را ترک می‌کند.

مهمان‌ها در صف ایستاده‌اند تا آب نبات بردارند. به ازای تمامی $i$های $0 \le i \le n-1$ ، حساب کنید چند مهمان خوشحال صحنه را ترک می‌کنند اگر آرین $i$ مهمان اول صف را از صف بیرون بیندازد.

ورودی🔗

در خط اول، دو عدد طبیعی $n$ و $m$ به ترتیب آمده‌اند.
در هر یک از $n$ خط بعدی دو عدد طبیعی $f_i$ و $s_i$ آمده‌اند $(1 \le s_i, f_i\le m)$ که به ترتیب نمایانگر آب نبات مورد علاقه‌ی مهمان $i$اُم و آب نباتی که مهمان $i$اُم از آن بدش نمی‌آید هستند.

خروجی🔗

در $n$ خط، جواب را به ازای تمامی $0 \le i \le n-1$ چاپ کنید.

زیرمسئله‌ها🔗

مثال‌ها🔗

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

4 2
1 2
1 2
1 2
1 2

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

2
2
2
1

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

محمد عاشق شده و میخواد زن بگیره و میخواد عروسی بگیره، تنها شیرینی عروسی کوکی لاهیجان و کلوچه نادریه.

گیلان شامل $n$ شهر است و بعضی از شهرها با یک جاده به هم متصل می‌شوند به طوری که بین هر دو شهر دقیقاً یک مسیر وجود دارد. (به عبارت دیگر گراف گیلان یک درخت است.)

از آنجا که خانه‌ی خانواده‌ی محمد در شهر $a$ و خانه‌ی خانواده‌ی عشقشق در شهر $b$ است، می‌خواهند در شهری جشن بگیرند که فاصله‌اش از $a$ و $b$ برابر باشد.

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

شاید براتون جالب باشه محمد عاشق چایی شده و اینا همه توهمه و در اصل عروسی سبحان در شهر وازوسکیه

ورودی🔗

*توجّه:* برای آسانی، گراف گیلان به صورت یک درخت ریشه‌دار شده از راس شماره‌ی ۱ در ورودی داده می‌شود.

در خط اول ورودی، $n$ تعداد شهرهای گیلان آمده است. پس از آن در خط $i$ ($2 \leq i \leq n$) یک عدد داده می‌شود که پدر (Parent) رأس $i$ در گراف گیلان است.

در خط بعد عدد $m$ تعداد پرسش‌ها آمده‌است. سپس در خط $i$ اُم از $m$ خط بعد، دو عدد طبیعی $a_i$ و $b_i$ آمده‌ است. $1 \leq u, v, a_i, b_i\le n \le 100\ 000 \quad , \quad 1 \leq m \le 100\ 000$

خروجی🔗

خروجی شامل $m$ خط است که باید در خط $i$ اُم تعداد شهرهایی که فاصله‌ی آن‌ها از دو شهر $a_i$ و $b_i$ برابر است را چاپ کنید.

مثال🔗

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

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

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

0
5
3

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

اشکان فیلمر یک جدول از فیلم‌های دیده شده و دیده نشده‌اش ‌$n \times m$ دارد که روی هر خانه‌ی آن ۰ یا ۱ برای فیلم‌های دیده نشده و دیده شده‌اش نوشته شده است. تعداد خانه‌های بزرگ‌ترین زیرمستطیلی از جدول فیلم‌های اشکان فیلمر را پیدا کنید که تمام خانه‌های آن ۰ باشد.

ورودی🔗

در خط اول ورودی دو عدد طبیعی $n$ و $m$ $(1 \le n, m \le 1000)$ به ترتیب می‌آید.
در هر یک از $n$ خط بعدی، $m$ عدد ۰ یا ۱ می‌آیند.

خروجی🔗

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

مثال🔗

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

3 5
1 0 1 1 0
0 0 0 1 1
1 0 0 1 0

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

4

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

4 4
1 1 0 0
1 1 0 0
0 0 0 0
1 1 0 1

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

6

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

رها یک آرایه‌ی $n$ عضوی به‌ نام $A$ از اعداد مختلف دارد. او می‌خواهد در آرایه‌ی $B$ که به صورت زیر تعریف می‌شود، یک کوه سیاه پیدا کند. $B_i = (\prod_{1 \leq j \leq n , j \neq i} A_j)\ mod\ A_i$

کوه سیاه خانه‌ای از آرایه است که هیچ یک از خانه‌های مجاورش بزرگ‌تر از آن نباشند. اگر شما بتوانید برنامه‌ای بنویسید که یک کوه سیاه در آرایه‌ی $B$ پیدا کند، حتما توجه رها را جلب خواهید کرد.

ورودی🔗

در خط اوّل ورودی عدد طبیعی $n$، تعداد اعضای آرایه‌ی $A$ آمده‌است.

سپس در خط بعد $n$ عدد طبیعی متفاوت $A_1, A_2, \dots, A_n\$ داده می‌شود. $2 \le n \le 10^6 \quad , \quad 1 \le A_i \le 2\times 10^9$

خروجی🔗

در تنها خط خروجی یک عدد $i$ چاپ کنید به طوری که $B_i$ یکی از کوه‌های سیاه آرایه‌ی $B$ باشد. در صورتی که $B$ چند کوه سیاه داشت، شماره‌ی یکی از کوه‌های سیاه را به دل‌خواه چاپ کنید.

مثال🔗

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

3
16 15 77

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

3

داریم: $B = 3, 2, 9$ که در آن خانه‌های شماره‌ی $1$ و $3$ کوه سیاه هستند.

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

5
1 3 4 100 10

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

2

داریم: $B = 0, 1, 0, 20, 0$ که در آن خانه‌های شماره‌ی $2$ و $4$ کوه سیاه هستند.

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

رها متوجه شده که وضع آرین نه تنها در درس جغرافی خوب نیست (بعد از ۱۰ سال در شهرک غرب بدون نقشه گم میشه)، بلکه در ریاضی هم تعریفی ندارد‌‌‌‌؛ برای همین یک سوال طرح کرده که آرین باید آن را حل کند.

رها یک معادله‌ی درست و خیلی ساده، مشابه زیر انتخاب کرده: $a+b=c$ که در آن $a$، $b$ و $c$ سه عدد صحیح و نامنفی هستند و هیچ صفر اضافه‌ای در سمت چپ این سه عدد وجود ندارد.

سپس علامت جمع و تساوی را از معادله حذف کرده و حاصل که به شکل زیر است را در اختیار آرین قرار داده است: $abc$

رها از آرین خواسته که مکان علامت‌های $+$ و $=$ را پیدا کند ولی چون این کار اصلاً ساده به نظر نمی‌رسد شما باید به آرین کمک کنید.

ورودی🔗

تنها خط ورودی شامل یک رشته‌ی $abc$ از ارقام $0$ تا $9$ است که طول آن از $10^6$ تجاوز نخواهد کرد.

خروجی🔗

در تنها خط خروجی سه عدد چاپ کنید که به ترتیب طول $a$، $b$ و $c$ هستند. در صورتی که مسئله چند پاسخ ممکن داشت، یک پاسخ را به دلخواه خروجی دهید.

مثال🔗

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

12345168

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

3 2 3

*توضیح نمونه ١:* معادله‌ی $123+45=168$ معتبر است که در آن طول $a$ برابر ٣، طول $b$ برابر ٢ و طول $c$ برابر ٣ می‌باشد.

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

099

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

1 1 1

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

199100

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

1 2 3

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

رها این ترم نمیدونه چرا مبانی منطق و نظریه مجموعه ها برداشته و هیچ ایده ای نداره چه طوری با مجموعه ها کار کنه؟

رها باید عملیات های زیر رو انجام بده: یک مجموعه داریم که در ابتدا تنها شامل عنصر صفر است. در هر مرحله یکی از سه عملیات زیر را روی این مجموعه اعمال می‌کنیم:

1. به ازای ورودی $x$: $x$ را به مجموعه اضافه کن.
2. به ازای ورودی $x$: به ازای هر عضو مجموعه مانند $y$ قرار بده $y=y \oplus x$. (اطلاعات بیشتر)
3. بزرگترین عنصر مجموعه را چاپ کن.

ورودی🔗

در اولین خط ورودی $q$ آمده است که تعداد عملیاتی است که باید روی مجموعه اجرا شود. در $q$ خط بعد، در هر خط یک عملیات داده می‌شود که به یکی از سه شکل زیر است:

• $1\ x$
• $2\ x$
• $3$

$1 \le n \le 500\ 000 \quad , \quad 0 \le x \le 10^9$

خروجی🔗

به ازای هر عملیات نوع ۳ که در ورودی آمده است، بزرگترین عنصر مجموعه را در یک خط چاپ کنید.

مثال🔗

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

10
3
1 7
3
2 4
2 8
2 3
1 10
1 3
3
2 1

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

0
7
15

• محدودیت زمان: 10 ثانیه
• محدودیت حافظه: 50 مگابایت

یک گراف جهت دار، غیر ساده و وزن دار با n راس به شما داده میشود. همچنین یک مجموعه قوانین نیز برای شما قرار داده شده است. مجموعه قوانین راجع به گراف به این صورت است که دو یال از گراف را میگیرد و به ازای آنها یک یال جدید اضافه میشود.

به عنوان مثال فرض کنید:

در این مثال از راس 0 به راس 1 با یال A و از راس 1 به راس 2 با یال B میرود. با توجه به قانون داده شده به ازای هر AB قرار است C نمایش بدهد پس از 0 به 2 یک C اضافه میکند و در ادامه از 0 به 2 با C میرود و از 2 به 3 با B میرود و در نتیجه طبق قانون از 0 به 3 یال A اضافه میشود. این کار را تا زمانی که دیگر یالی اضافه نشود، تکرار میکنیم.

فرض کنین مجموعه قوانین داده شده به این صورت است که هر دو یال n و e که در یک پیمایش به صورت ne باشد. یعنی: n->ne

ورودی🔗

در سطر اول گراف تعداد راس ها (n) را میبینید. و در سطرهای بعدی به ترتیب ابتدا شماره راس مبدا (A)، شماره راس مقصد (B) و با وزن یال از A به B

$1 \le A, B, n \le 40000$

خروجی🔗

در خروجی فقط تعداد یال‌های اضافه شده در انتها بنویسید.

مثال🔗

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

25
0  1  e
2  3  e
4  5  e
6  7  e
8  9  e
10 11 e
12 4  e
13 14 e
9  15 e
16 8  n
7  17 e
18 19 e
20 6  e
21 22 e
11 17 e
-1

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

2