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

محمد و عرفان از دوستان خوب و هم‌رشته هستند، آن‌ها برای کار روی یک پروژه تصمیم گرفتند یک روز در سال را انتخاب کنند و به توسعه پروژه‌شان بپردازند ولی روزهای انتخاب شده توسط آن‌ها یکی نیست!

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

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

در واقع به شما تاریخ دو روز در سال ۱۳۹۹ داده می‌شود و شما باید فاصله آن دو روز را چاپ کنید. توجه کنید که ۶ ماه اول سال ۳۱ روزه و ۵ ماه بعدی ۳۰ روزه و ماه آخر ۲۹ روزه است.

ورودی🔗

در خط اول ورودی ابتدا عدد $m1$ و سپس عدد $d1$ به ترتیب نشان‌دهنده شماره ماه و روز انتخابی محمد و در خط دوم ابتدا عدد $m2$ و سپس عدد $d2$ به ترتیب نشان‌دهنده شماره ماه و روز انتخابی عرفان آمده است. (توجه داشته باشید سال مورد نظر کبیسه نیست). $1 \leq m1, m2 \leq 12$ $1 \leq d1, d2 \leq 31$

خروجی🔗

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

مثال🔗

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

1 1
1 2

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

1

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

6 30
7 30

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

31

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

صفا باشه!، صمیمیت باشه!

محمد و عرفان بعد از این که با روشی عجیب فهمیدند ذهن‌هایشان خیلی از هم فاصله دارد با روشی عجیب‌تر اقدام به رفع فاصله اذهانشان کردند!

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

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

حال برنامه شما باید در $2n - 1$ خط (تعداد مراحل بازی که طول می‌کشد تا فقط یک پا باقی بماند) روند جلو رفتن هر مرحله را چاپ کند (برای فهم بهتر مثال‌ها را ببینید). در آخر هم برنده بازی را مشخص کند.

توجه کنید در حالتی که در آخر هر دو پای یک نفر باقی بماند، نباید مرحله آخر را چاپ کنید و برنده مشخص می‌شود.

ورودی🔗

به شما دو عدد $n$ و $k$ داده می‌شود که نشان دهنده تعداد بازی کنان و تعداد کلمات شعر است (یعنی با شروع از پای اول $k$ تا پا به جلو می‌رود و آن را ورمیچیند!) $2 \le n, k \le 100$

خروجی🔗

ابتدا در هر خط خروجی یک مرحله از بازی به صورت $k$ عدد چاپ می‌شود که بیانگر ترتیب پاها در آن مرحله است. در آخرین خط از خروجی باید شمارهٔ بازیکن برنده طبق فرمتی که در ادامه مشاهده می‌کنید چاپ شود.

مثال🔗

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

4 7

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

1 1 2 2 3 3 4 
4 1 1 2 2 3 3 
4 1 1 2 2 3 4 
1 1 2 2 3 1 1 
2 2 3 1 2 2 3 
1 2 2 1 2 2 1 
winner:2

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

3 8

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

1 1 2 2 3 3 1 1
2 2 3 3 1 2 2 3
3 1 2 2 3 1 2 2
3 1 2 3 1 2 3 1
2 3 2 3 2 3 2 3
winner:2

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

بریم ببینیم برنامه چیه!

در کمال ناباوری محمد این جمله معروفش را هم گفت و به همه ثابت کرد روش عجیبی که برای نزدیک‌ کردن فاصله ذهن‌شان پیش گرفتند جواب داد! اکنون فاصله بین ذهن محمد و عرفان به سمت صفر میل می‌کند و آن‌ها مقدار زیادی خوشحال‌اند! قبل از اینکه بالاخره شروع به توسعه دادن پروژه کنند تصمیم گرفتند که اندکی برای دست‌گرمی با هم کد بزنند ولی متاسفانه هنوز به کدزدن با زبان ++C تسلط کافی ندارند.

از آن‌جایی که محمد و عرفان هیچ کدام از کارهایشان عادی نبوده، یادگیری ++Cشان هم از این قاعده مستثنی نیست! آن‌ها از شما درخواست کردند که با حل یک سوال کمک کنید تا به طور کامل به ++C مسلط شوند!

رشته $S$ برای رشته $T$ یک وارواژه است اگر بتوان با جابه‌جا کردن حروف رشته $S$ به رشته $T$ رسید. برای مثال aba وارواژه رشته aab است اما وارواژه رشته aaa نیست.

رشته $S$ رشته‌ای است که شامل حروف کوچک زبان انگلیسی و تعدادی کاراکتر $?$ است. همچنان رشته $P$ رشته‌ای است که تنها شامل حروف کوچک انگلیسی است. زیررشته‌ای از $S$ را زیررشته خوب می‌گوییم اگر بتوان با قرار دادن حروف دل‌خواه بجای $?$، به وارواژه‌ای از $P$ دست یافت.

ورودی🔗

در این سوال به شما ابتدا رشته $S$ و بعد $p$ داده می‌شود.

$1 \le |S|, |p| \le 1\ 000$

خروجی🔗

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

مثال🔗

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

bb??x???
aab

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

2

در این نمونه دو زیررشته b?? و ???می‌توانند با جایگزین شدن علامت سوال‌هایشان و تبدیل شدن به baa و aab وارواژه رشته $P$ شوند.

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

ab?c
acb

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

2

در این مثال دو زیررشته ab? و b?c با تبدیل شدن به abc و bac می توانند وارواژه رشته acb شوند.

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

در یکی از زندان‌های شهر قلی‌لند، $n$ زندانی وجود دارند که هرکدام در یک سلول انفرادی زندانی هستند.

این زندان شکلی عجیب دارد و به این صورت است که سلول‌های زندان به دور یک دایره می‌باشند و سلول‌ها از ۱ تا $n$ به ترتیب شماره‌گذاری شده‌اند.

زندانی‌ها برای ارتباط مخفیانه با یکدیگر، از قبل با استفاده از قاشق، زمین را حفر کردند و تونل‌هایی ساختند. نقشه فعلی تونل‌ها به این شکل می‌باشد که شخصی که در سلول شماره‌ی $i$ است، می‌تواند با استفاده از تونل، به سلول $i-1$ ام و سلول $i + 1$ ام برود (همچنین سلول شماره‌ی $n$ و سلول شماره‌ی ۱ نیز به یکدیگر با تونل مسیر دارند).

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

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

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

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

ورودی🔗

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

در خط $i$ام از $m$ خط بعدی، دو عدد $u_i$ و $v_i$ داده می‌شود که دو سر تونل $i$ام می‌باشد.

توجه کنید در میان تونل‌های جدید ممکن است تونلی دو سلول مجاور که از ابتدا به یکدیگر تونل داشته‌اند را وصل کند که در این صورت هم می‌توانید آن را درون دایره بسازید و هم می‌توانید بیرون دایره بسازید.

$1 \le n,m \le 2\ 000$ $1 \le u_i, v_i \le n$

خروجی🔗

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

در غیر اینصورت یک رشته $m$ حرفی متشکل از $I,O$ چاپ کنید که حرف $i$ام آن $I$ است اگر تونل درون دایره ساخته می‌شود و $O$ است اگر بیرون دایره ساخته می‌شود.

در صورت وجود جواب‌های مختلف یکی را می‌توانید به دلخواه چاپ کنید.

مثال🔗

ورودی نمونه🔗

5 3
1 3
3 5
2 4

خروجی نمونه🔗

IIO

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

پس از اینکه مهدی به زندانیان در حفر تونل کمک کرد، زندانیان شروع به پرسیدن سوال از مهدی کردند تا اعتمادشان نسبت به مهدی زیاد شود.

آن‌ها یک تکه کد که مربوط به الگوریتم مرتب‌سازی ادغامی می‌باشد را به مهدی دادند و به او گفتند که یک جایگشت از اعداد ۱ تا $n$ را با توجه به کد داده شده، مرتب کرده‌اند و همچنین خروجی تولید شده توسط کد را نیز به او دادند (به cout ها در کد توجه کنید).

کد به صورت زیر می‌باشد:

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

به دلیل اینکه زندانیان فرصت کافی برای چک کردن جواب شما را ندارند، از شما می‌خواهند که جایگشت مورد نظر را به عنوان ورودی به تابع زیر بدهید و خروجی تابع را به آن‌ها بگویید.

ورودی🔗

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

خط دوم رشته‌ی مربوط به خروجی تولید شده توسط کد است که متشکل از اعداد ۱ و ۲ می‌باشد.

$2 \le n \le 10\ 000$

خروجی🔗

در تنها خط خروجی، عددی که به عنوان خروجی از تابع checksum در کد بالا گرفته‌اید را خروجی دهید.

مثال🔗

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

4
12212

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

987041

جایگشت اولیه برابر 2, 4, 3, 1 می‌باشد.

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

2
1

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

994

جایگشت اولیه برابر 1, 2 می‌باشد.

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

2
2

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

1024

جایگشت اولیه برابر 2, 1 می‌باشد.

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

علی که دانش‌جویی دغدغه‌مند است تصمیم گرفته کاری جهادی به انجام برساند و شبکه‌ی ملی مواسات را راه‌اندازی کرده‌ست. این شبکه با متصل کردن خیرین شهرهای مختلف به یک‌دیگر ضمن نیازسنجی از هر منطقه کمک می‌کند خیرین شهر دارای تقاضا از خیرین دیگر شهرها تقاضای کمک کنند. این شبکه از پیوندهایی تشکیل شده است که هر پیوند دو خیّر را به هم متصل می‌کند.

پارسا که دانش‌جویی ظاهرالصلاح است، با دانش اندک خود از شبکه و امنیت قصد خراب‌کاری دارد. او تصمیم دارد یکی از پیوندها را مختل کند. بین پیوندهای موجود او پیوندی را انتخاب می‌کند که بیشترین آسیب را به شبکه‌ی مواسات بزند؛ یعنی بیشینه تعداد جفت از خیّرها را از هم جدا کند. منظور از جدا شدن دو خیر این است که پیش از آن با شبکه‌ی پیوندها به هم متصل بوده‌ند و پس از حمله‌ی پارسا دیگر متصل نیستند.

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

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

ورودی🔗

خط اول ورودی شامل $n, m, k$ است، تعداد خیرین، تعداد پیوندها و تعداد پیوندهایی که مهدی می‌تواند ایجاد کند. در $m$ خط بعدی پیوندها به شکل $v u$ داده می‌شوند. $0 \le n, m, k \le 300\ 000$

$1 \le v, u \le n$

خروجی🔗

تعداد خیرینی که بعد از هم جدا می‌شوند، در صورتی که مهدی بهینه عمل کند.

مثال🔗

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

3 3 1
1 2
2 3
1 3

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

0

پارسا هیچ کاری نمی‌تواند بکند.

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

7 6 1
1 2
2 3
3 4
3 5
5 6
5 7

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

6