چوپان خسته

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

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

ورودی🔗

در تنها خط ورودی، عدد $n$ می آید که نشان دهنده تعداد پای گوسفندان است. تضمین می شود که هر گوسفند دقیقاً ۴ پا دارد و تعداد داده شده درست است.

خروجی🔗

در تنها خط خروجی، تعداد گوسفندان را نمایش دهید.

محدودیت‌ها🔗

$0 \leq n \leq 10^9$

مثال‌ها🔗

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

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

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

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

تولد مهدیس

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

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

ورودی🔗

در خط اول ورودی، عدد $n$ داده می‌شود.

در خط دوم ورودی، اعداد $a$ و $b$ که نشان‌دهنده‌ی گیلاس‌های انتخاب شده برای برش اول هستند داده می‌شوند.

در خط سوم ورودی، اعداد $c$ و $d$ که نشان‌دهنده‌ی گیلاس‌های انتخاب شده برای برش دوم هستند داده می‌شوند.

تضمین می‌شود که:

هر دو سر هر برش متفاوت و همچنین خود دو برش نیز متفاوت هستند.

خروجی🔗

در تنها خط خروجی، تعداد تکه‌های کیک بعد از دو برش داده شده را چاپ کنید.

محدودیت‌ها🔗

$3 \leq n \leq 100$
$1 \leq a, b, c, d \leq n$

مثال‌ها🔗

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

4
1 3
2 4

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

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

4
1 3
2 3

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت -------------- رضا که از شهر برره خسته شده بود، تصمیم دارد یک شهر جدید بسازد. او می‌خواهد این شهر به شکل یک جدول از خانه‌ها باشد، به طوری که هر خانه با خانه‌های مجاور افقی، عمودی و قطری همسایه باشد (هر خانه حداکثر $8$ همسایه می‌تواند داشته باشد). در ابتدا، چراغ هر خانه روشن یا خاموش بوده و در جدول به صورت زیر مشخص می‌شود: - روشن باشد، خانه در ترسیمات خانگی متناظر در جدول با علامت $"X"$ مشخص می‌شود. - خاموش باشد، خانه در ترسیمات خانگی متناظر در جدول با علامت $"."$ مشخص می‌شود. ![شکل سوال](https://quera.org/qbox/download/FWxesBWKya/C.jpg) صالح، از اهالی برره، که فردی حساس به نور و خطاهای احتمالی است، تصمیم به آزاردیدن اهل شهر جدید دارد. او گفته است که برای انجام این کار، باید تعداد خانه‌هایی که دقیقاً دو خانه روشن همسایه دارند (یعنی خانه‌هایی با علامت $"X"$ در همسایگی‌شان) محاسبه شود. به رضا کمک کنید که ساختار اولیه شهر و نحوی روشن و خاموش بودن چراغ‌ها را طوری طراحی کند که صالح دقیقاً $n$ خانه را به خاطر مشکل کمبود مصالح بتواند علامت بزند. # ورودی در تنها خط ورودی عدد صحیح $n$ که بیانگر تعداد خانه‌هایی است که صالح باید علامت بزند، داده می‌شود. # خروجی - در خط اول خروجی یک عدد که به ترتیب برابر با تعداد سطرها و ستون‌های جدول است را چاپ کنید. - در خطوط بعدی، جدول مستطیلی از $"X"$ و $"."$ چاپ کنید که شرط مسئله را داشته باشد. دقت کنید تعداد سطرها و ستون‌ها هرکدام باید حداکثر $50$ باشند. # محدودیت‌ها $1 \leq n \leq 500$ # مثال‌ها ## ورودی نمونه ۱ ``` 2 ``` ## خروجی نمونه ۱ ``` 5 5 ..... .XX.. .X.X. .X... ..... ``` ## ورودی نمونه ۲ ``` 6 ``` ## خروجی نمونه ۲ ``` 6 8 ........ .XXX..X. ..X..X.. ..X..X.. ..X...X. ........ ``` ## ورودی نمونه ۳ ``` 1 ``` ## خروجی نمونه ۳ ``` 2 4 XXXX XXXX .XXX ```

کنار برره

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

رضا که از شهر برره خسته شده بود، تصمیم دارد یک شهر جدید بسازد. او می‌خواهد این شهر به شکل یک جدول از خانه‌ها باشد، به طوری که هر خانه با خانه‌های مجاور افقی، عمودی و قطری همسایه باشد (هر خانه حداکثر $8$ همسایه می‌تواند داشته باشد). در ابتدا، چراغ هر خانه روشن یا خاموش بوده و در جدول به صورت زیر مشخص می‌شود:

روشن باشد، خانه در ترسیمات خانگی متناظر در جدول با علامت $"X"$ مشخص می‌شود.
خاموش باشد، خانه در ترسیمات خانگی متناظر در جدول با علامت $"."$ مشخص می‌شود.

شکل سوال

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

به رضا کمک کنید که ساختار اولیه شهر و نحوی روشن و خاموش بودن چراغ‌ها را طوری طراحی کند که صالح دقیقاً $n$ خانه را به خاطر مشکل کمبود مصالح بتواند علامت بزند.

ورودی🔗

در تنها خط ورودی عدد صحیح $n$ که بیانگر تعداد خانه‌هایی است که صالح باید علامت بزند، داده می‌شود.

خروجی🔗

در خط اول خروجی یک عدد که به ترتیب برابر با تعداد سطرها و ستون‌های جدول است را چاپ کنید.
در خطوط بعدی، جدول مستطیلی از $"X"$ و $"."$ چاپ کنید که شرط مسئله را داشته باشد. دقت کنید تعداد سطرها و ستون‌ها هرکدام باید حداکثر $50$ باشند.

محدودیت‌ها🔗

$1 \leq n \leq 500$

مثال‌ها🔗

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

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

5 5
.....
.XX..
.X.X.
.X...
.....

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

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

6 8
........
.XXX..X.
..X..X..
..X..X..
..X...X.
........

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

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

2 4
XXXX
XXXX
.XXX

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در مرکز داده ی سرداده $n$ سرور که با شماره های $1$ تا $n$ شماره گذاری شده اند، برای نگهداری فایل های کاربران قرار دارد که هر فایل در تعدادی از آن ها ذخیره می شود تا در صورت بروز مشکل یا خرابی در هرکدام از آن ها، اطلاعات تا جای ممکن از دست نروند و میزان دسترسی کاربران به فایل هایشان در هر لحظه در بالاترین سطح ممکن قرار بگیرد. شما به عنوان مسئول زیرساخت و طراح سیستم، مسئولیت طراحی داده ساختاری دارید که بتواند نیازهای سیستم را برطرف کند و به درخواست های آن پاسخ مناسبی بدهد. در طول روز، $q$ درخواست مختلف به ترتیب به سمت مرکز داده می آید که هر کدام به یکی از دو نوع زیر است: • درخواست `“x add”`: فایل جدیدی با حجم $x$ مگابایت به انتهای صف فایل های سرور $1$ اضافه می شود. • درخواست `“sync”`: به صورت همزمان، به ازای هر $1 <= i <= n$ قدیمی ترین فایلی که در صف سرومiام قرار دارد و در صف فایل های سرور$(i+1)$ام قرار ندارد (در صورت وجود) به سرور$(i+1)$ام ارسال می شود تا در انتهای صف فایل های سرور$(i+1)$ام قرار بگیرد. تمام فایل های ورودی، حتی در صورت هم حجم بودن، باهم متفاوت در نظر گرفته می شوند. هدف، محاسبه ی مجموع حجم فایل های درون صف های سرور ها پس از اجرای هر دستور است. دقت کنید که فایل های ورودی هرگز حذف نخواهند شد. # ورودی در خط اول ورودی دو عدد$n$ و $q$ که به ترتیب برابر با تعداد سرورها و تعداد درخواست های ورودی به سیستم است به شما داده می شود. در هرکدام از $q$ خط بعدی، به ترتیب یکی از درخواست های گفته شده با فرمت معتبر داده می شود. # خروجی خروجی شامل $q$ خط است که در خط $i$ام باید مجموع حجم تمام فایل های درون صف های سرورها تا انتهای انجام درخواست $i$ام را محاسبه و چاپ کنید. ## محدودیت‌ها - $1 \leq n, q \leq 10^6$ - اندازه‌ی فایل‌ها عددی طبیعی و حداکثر برابر با $10^9$ است. # مثال‌ها ## ورودی نمونه ۱ ``` 3 7 add 1 add 2 sync add 1 add 2 sync sync ```` ## خروجی نمونه ۱ ``` 1 3 4 5 7 10 13 ````

انتقال فایل

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

در مرکز داده ی سرداده $n$ سرور که با شماره های $1$ تا $n$ شماره گذاری شده اند، برای نگهداری فایل های کاربران قرار دارد که هر فایل در تعدادی از آن ها ذخیره می شود تا در صورت بروز مشکل یا خرابی در هرکدام از آن ها، اطلاعات تا جای ممکن از دست نروند و میزان دسترسی کاربران به فایل هایشان در هر لحظه در بالاترین سطح ممکن قرار بگیرد. شما به عنوان مسئول زیرساخت و طراح سیستم، مسئولیت طراحی داده ساختاری دارید که بتواند نیازهای سیستم را برطرف کند و به درخواست های آن پاسخ مناسبی بدهد. در طول روز، $q$ درخواست مختلف به ترتیب به سمت مرکز داده می آید که هر کدام به یکی از دو نوع زیر است:

• درخواست “x add”: فایل جدیدی با حجم $x$ مگابایت به انتهای صف فایل های سرور $1$ اضافه می شود.

• درخواست “sync”: به صورت همزمان، به ازای هر $1 <= i <= n$ قدیمی ترین فایلی که در صف سرومiام قرار دارد و در صف فایل های سرور $(i+1)$ ام قرار ندارد (در صورت وجود) به سرور $(i+1)$ ام ارسال می شود تا در انتهای صف فایل های سرور $(i+1)$ ام قرار بگیرد.

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

ورودی🔗

در خط اول ورودی دو عدد $n$ و $q$ که به ترتیب برابر با تعداد سرورها و تعداد درخواست های ورودی به سیستم است به شما داده می شود. در هرکدام از $q$ خط بعدی، به ترتیب یکی از درخواست های گفته شده با فرمت معتبر داده می شود.

خروجی🔗

خروجی شامل $q$ خط است که در خط $i$ ام باید مجموع حجم تمام فایل های درون صف های سرورها تا انتهای انجام درخواست $i$ ام را محاسبه و چاپ کنید.

محدودیت‌ها🔗

$1 \leq n, q \leq 10^6$
اندازه‌ی فایل‌ها عددی طبیعی و حداکثر برابر با $10^9$ است.

مثال‌ها🔗

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

3 7
add 1
add 2
sync
add 1
add 2
sync
sync

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- مهدی که یک لوله کش برتر است، تعدادی چاه آب دارد که به خروجی هایی که با`“X”` نشان داده می شوند، وصل می شوند. او می خواهد خروجی ها را با استفاده از اتصالاتی که در اختیار دارد به یک شاه لوله وصل کند. برای این کار مهدی قادر به استفاده از دو نوع اتصال است: • اتصال نوع `“A ”` که دو خروجی را می گیرد و به اندازه جمع آب خروجی شان، خروجی می دهد. • اتصال نوع `“B ”` که دو خروجی را می گیرد و به اندازه بیشینه آب خروجی شان، خروجی می دهد. مثلا اگر `“Y ”`و `“Z ”` دو خروجی باشند، دو سیستم لوله ای `“AYZ ”` و `“BYZ ”` را می توان با استفاده از آن ها ساخت. به شما یک سیستم لوله ای داده می شود که متشکل از کاراکترهای `"A"`, `"B"` و `"X"` است. به تعداد `"X"`ها در این سیستم چاه آب با ظرفیت های متفاوت داریم که ظرفیت ها به شما داده می شوند. شما باید با وصل کردن چاه ها به خروجی ها (`“X”`ها)، بیشترین خروجی آب ممکن سیستم لوله ای داده شده را به دست بیاورید. دقت کنید که هر چاه باید به دقیقا یک خروجی متصل شود. # ورودی در خط اول به شما عدد $n$ داده می‌شود که برابر با تعداد چاه‌های آب است. در خط دوم، یک رشته از کاراکترهای `"A"`, `"B"` و `"X"` می‌آید. تضمین می‌شود که این رشته متناظر با یک سیستم لوله‌ای معتبر است و تعداد کاراکترهای `"X"` برابر $n$ است. در خط سوم $n$ عدد صحیح $A_i$ $(1 \leq i \leq n)$ به شما داده می‌شود که ظرفیت چاه‌ها است. # خروجی در یک خط بیشترین مقدار خروجی آب ممکن سیستم را چاپ کنید. # محدودیت‌ها - $1 \leq n \leq 2 \times 10^5$ - $0 \leq A_i \leq 10^9$ # مثال‌ها ## ورودی نمونه ۱ ``` 3 BXBXX 8 2 3 ```` ## خروجی نمونه ۱ ``` 8 ```` ## ورودی نمونه ۲ ``` 5 AAXXAXAXX 1 1 10 2 8 ```` ## خروجی نمونه ۲ ``` 22 ```` ## ورودی نمونه ۳ ``` 3 AXBXX 8 2 3 ```` ## خروجی نمونه ۳ ``` 11 ````

لوله‌کشی برتر

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

مهدی که یک لوله کش برتر است، تعدادی چاه آب دارد که به خروجی هایی که با“X” نشان داده می شوند، وصل می شوند. او می خواهد خروجی ها را با استفاده از اتصالاتی که در اختیار دارد به یک شاه لوله وصل کند. برای این کار مهدی قادر به استفاده از دو نوع اتصال است:

• اتصال نوع “A ” که دو خروجی را می گیرد و به اندازه جمع آب خروجی شان، خروجی می دهد.

• اتصال نوع “B ” که دو خروجی را می گیرد و به اندازه بیشینه آب خروجی شان، خروجی می دهد.

مثلا اگر “Y ”و “Z ” دو خروجی باشند، دو سیستم لوله ای “AYZ ” و “BYZ ” را می توان با استفاده از آن ها ساخت. به شما یک سیستم لوله ای داده می شود که متشکل از کاراکترهای "A", "B" و "X" است. به تعداد "X"ها در این سیستم چاه آب با ظرفیت های متفاوت داریم که ظرفیت ها به شما داده می شوند. شما باید با وصل کردن چاه ها به خروجی ها (“X”ها)، بیشترین خروجی آب ممکن سیستم لوله ای داده شده را به دست بیاورید. دقت کنید که هر چاه باید به دقیقا یک خروجی متصل شود.

ورودی🔗

در خط اول به شما عدد $n$ داده می‌شود که برابر با تعداد چاه‌های آب است.
در خط دوم، یک رشته از کاراکترهای "A", "B" و "X" می‌آید.
تضمین می‌شود که این رشته متناظر با یک سیستم لوله‌ای معتبر است و تعداد کاراکترهای "X" برابر $n$ است.
در خط سوم $n$ عدد صحیح $A_i$ $(1 \leq i \leq n)$ به شما داده می‌شود که ظرفیت چاه‌ها است.

خروجی🔗

در یک خط بیشترین مقدار خروجی آب ممکن سیستم را چاپ کنید.

محدودیت‌ها🔗

$1 \leq n \leq 2 \times 10^5$
$0 \leq A_i \leq 10^9$

مثال‌ها🔗

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

3
BXBXX
8 2 3

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

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

5
AAXXAXAXX
1 1 10 2 8

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

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

3
AXBXX
8 2 3

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- زهرا به دلیل علاقه زیاد مسئولیت نظارت بر بازسازی دانشکده را به عهده گرفته است. برای انجام این کار او $n$ داوطلب در اختیار دارد که به هرکدام از آن ها حداکثر یک وظیفه محول خواهد کرد. انجام شدن هر وظیفه زهرا را مقداری خوشحال می کند، اما اگر خودش آن وظیفه را انجام داده باشد بیشتر خوشحال می شود. از آنجایی که زهرا بیشتر از $m$ وظیفه نمی تواند انجام دهد، باید به طور هوشمندانه ای تصمیم بگیرد که کدام وظیفه ها را خودش انجام $b_i$ واحد خوشحالی به دست می آورد و اگر خودش انجام دهد $a_i$ واحد خوشحالی دهد. اگر وظیفه ی $i$ام را داوطلب انجام داده باشد زهرا به دست می آورد. بیشینه مقدار خوشحالی که زهرا می تواند کسب کند را بیابید. # ورودی در خط اول ورودی اعداد $n$ و $m$ از چپ به راست داده می‌شوند. به ازای هر $1 \leq i \leq n$، در $(i + 1)$امین خط ورودی، از چپ به راست، اعداد صحیح $a_i$ و $b_i$ داده خواهند شد. # خروجی در تنها خط خروجی بیشترین مقدار خوشحالی که زهرا می تواند کسب کند را نمایش دهید. # محدودیت‌ها - $1 \leq n, m \leq 10^5$ - $1 \leq b_i < a_i \leq 1000$ # مثال‌ها ## ورودی نمونه ۱ ``` 4 1 6 3 6 4 101 51 6 2 ```` ## خروجی نمونه ۱ ``` 110 ```` ## ورودی نمونه ۲ ``` 5 2 6 3 101 51 6 4 6 2 101 4 ```` ## خروجی نمونه ۲ ``` 211 ```` ## ورودی نمونه ۳ ``` 4 5 321 1 654 2 987 3 1000 4 ```` ## خروجی نمونه ۳ ``` 2962 ````

وظایف زهرا

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

زهرا به دلیل علاقه زیاد مسئولیت نظارت بر بازسازی دانشکده را به عهده گرفته است. برای انجام این کار او $n$ داوطلب در اختیار دارد که به هرکدام از آن ها حداکثر یک وظیفه محول خواهد کرد. انجام شدن هر وظیفه زهرا را مقداری خوشحال می کند، اما اگر خودش آن وظیفه را انجام داده باشد بیشتر خوشحال می شود. از آنجایی که زهرا بیشتر از $m$ وظیفه نمی تواند انجام دهد، باید به طور هوشمندانه ای تصمیم بگیرد که کدام وظیفه ها را خودش انجام $b_i$ واحد خوشحالی به دست می آورد و اگر خودش انجام دهد $a_i$ واحد خوشحالی دهد. اگر وظیفه ی $i$ ام را داوطلب انجام داده باشد زهرا به دست می آورد. بیشینه مقدار خوشحالی که زهرا می تواند کسب کند را بیابید.

ورودی🔗

در خط اول ورودی اعداد $n$ و $m$ از چپ به راست داده می‌شوند.
به ازای هر $1 \leq i \leq n$ ، در $(i + 1)$ امین خط ورودی، از چپ به راست، اعداد صحیح $a_i$ و $b_i$ داده خواهند شد.

خروجی🔗

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

محدودیت‌ها🔗

$1 \leq n, m \leq 10^5$
$1 \leq b_i < a_i \leq 1000$

مثال‌ها🔗

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

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

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

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

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- قرار است یک تورنومنت کشتی با $n$ شرکت‌کننده برگزار شود. شرکت‌کنندگان را با اعداد $1$ تا $n$ نام‌گذاری می‌کنیم. در این تورنومنت هر دو شرکت‌کننده دقیقاً یک بار با هم بازی می‌کنند (در کل $ \frac{n(n-1)}{2} $ بازی انجام خواهد شد) و هر شرکت‌کننده در یک روز حداکثر یک بازی می‌تواند انجام دهد. شرکت‌کنندگان فکر می‌کنند اگر به ترتیب خاصی با حریفان خود بازی کنند، شانس بیشتری برای قهرمانی خواهند داشت. به طور دقیق، هر شرکت‌کننده نام ترتیب زیر را برای بازی با شرکت‌کنندگان دیگر ترجیح می‌دهد: $$ P_{i,1}, P_{i,2}, \dots, P_{i,n-2}, P_{i,n-1} $$ برگزارکننده تورنومنت که می‌خواهد همه شرکت‌کنندگان راضی باشند، از شما می‌خواهد که به او بگویید آیا می‌توان برنامه بازی‌ها را به گونه‌ای چید که همه شرکت‌کنندگان به ترتیب دلخواه خود بازی کنند یا خیر. اگر جواب مثبت است، به او بگویید حداقل چند روز برای برگزاری تورنومنت لازم است. # ورودی در خط اول ورودی $n$ که تعداد شرکت‌کنندگان است داده می‌شود. سپس، به ازای هر $1 \leq i \leq n$، در $(i+1)$امین خط ورودی که مرتبط با شرکت‌کننده $i$ام است، جایگشتی از $1$ تا $n-1$ شرکت‌کننده‌ی دیگر داده می‌شود که بیانگر ترتیب مطلوب شرکت‌کننده $i$ام است. # خروجی در تنها خط خروجی، اگر برگزاری این تورنومنت ممکن است کمترین تعداد روز لازم و در غیر این صورت −۱ چاپ کنید. # محدودیت‌ها - $3 \leq n \leq 1000$ # مثال‌ها ## ورودی نمونه ۱ ``` 3 2 3 1 3 1 2 ```` ## خروجی نمونه ۱ ``` 3 ```` ## ورودی نمونه ۲ ``` 4 4 2 3 3 4 1 2 4 1 1 2 3 ```` ## خروجی نمونه ۲ ``` 4 ```` ## ورودی نمونه ۳ ``` 3 3 2 1 3 2 1 ```` ## خروجی نمونه ۳ ``` -1 ````

تورنمنت کشتی

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

قرار است یک تورنومنت کشتی با $n$ شرکت‌کننده برگزار شود. شرکت‌کنندگان را با اعداد $1$ تا $n$ نام‌گذاری می‌کنیم. در این تورنومنت هر دو شرکت‌کننده دقیقاً یک بار با هم بازی می‌کنند (در کل $\frac{n(n-1)}{2}$ بازی انجام خواهد شد) و هر شرکت‌کننده در یک روز حداکثر یک بازی می‌تواند انجام دهد. شرکت‌کنندگان فکر می‌کنند اگر به ترتیب خاصی با حریفان خود بازی کنند، شانس بیشتری برای قهرمانی خواهند داشت. به طور دقیق، هر شرکت‌کننده نام ترتیب زیر را برای بازی با شرکت‌کنندگان دیگر ترجیح می‌دهد:

$P_{i,1}, P_{i,2}, \dots, P_{i,n-2}, P_{i,n-1}$

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

ورودی🔗

در خط اول ورودی $n$ که تعداد شرکت‌کنندگان است داده می‌شود.
سپس، به ازای هر $1 \leq i \leq n$ ، در $(i+1)$ امین خط ورودی که مرتبط با شرکت‌کننده $i$ ام است، جایگشتی از $1$ تا $n-1$ شرکت‌کننده‌ی دیگر داده می‌شود که بیانگر ترتیب مطلوب شرکت‌کننده $i$ ام است.

خروجی🔗

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

محدودیت‌ها🔗

$3 \leq n \leq 1000$

مثال‌ها🔗

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

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

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

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

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

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

-1

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- صالح پس از یک شام سنگین به خواب می‌رود. او در خواب با یک دیو در کابوس گیر می‌کند و تنها راه فرار از کابوس این است که جواب سوال دیو را بدهد. در این کابوس، صالح شاه یک محله است که $n$ خانه دارد. خانه‌ها از چپ به راست با اعداد ۱ تا $n$ نام‌گذاری شده‌اند. در خانه $i$، عدد صحیح مثبت $a_i$ وجود دارد. دیو عدد صحیح مثبت $5$ را به صالح می‌گوید. همچنین او به ازای هر زوج مرتب $(l, r)$ که نامساوی $1 \leq l \leq r \leq n$ در آن صدق می‌کند، مقدار $f(l, r)$ را برابر با تعداد زیر دنباله‌های دنباله‌ای به‌عنوان $a_l, a_{l+1}, \dots, a_r$ که جمع اعضایشان برابر $5$ است تعریف می‌کند. دقت کنید که یک زیر دنباله می‌تواند از دنباله اصلی با حذف برخی یا هیچ یک از عناصر ایجاد شود (بدون اینکه ترتیب عناصر باقی‌مانده تغییر کند). دیو از صالح می‌خواهد که جمع همه $f(l, r)$ها به ازای همه جفت‌های ممکن را حساب کند و باقیمانده آن را بر عدد $998244353$ به او بدهد. ازآنجایی که صالح قادر به حل این مسئله نیست، با محاسبه پاسخ این سوال به او کمک کنید تا از کابوسش فرار کند. # ورودی در خط اول ورودی، دو عدد $n$ و $S$ به شما داده می‌شود. سپس، در خط بعدی $n$ عدد که نشان‌دهنده دنباله $a_i$ها است به شما داده می‌شوند. # خروجی در تنها خط خروجی، جواب سوال را چاپ کنید. ## محدودیت‌ها - $1 \leq n \leq 3000$ - $1 \leq S \leq 3000$ - $1 \leq a_i \leq 3000$ # مثال‌ها ## ورودی نمونه ۱ ``` 3 6 3 3 6 ```` ## خروجی نمونه ۱ ``` 5 ```` ## ورودی نمونه ۲ ``` 5 3 4 5 6 7 8 ```` ## خروجی نمونه ۲ ``` 0 ```` ## ورودی نمونه ۳ ``` 10 10 3 2 5 2 3 5 2 1 8 1 ```` ## خروجی نمونه ۳ ``` 273 ````

کابوس

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

صالح پس از یک شام سنگین به خواب می‌رود. او در خواب با یک دیو در کابوس گیر می‌کند و تنها راه فرار از کابوس این است که جواب سوال دیو را بدهد.
در این کابوس، صالح شاه یک محله است که $n$ خانه دارد. خانه‌ها از چپ به راست با اعداد ۱ تا $n$ نام‌گذاری شده‌اند. در خانه $i$ ، عدد صحیح مثبت $a_i$ وجود دارد. دیو عدد صحیح مثبت $5$ را به صالح می‌گوید.
همچنین او به ازای هر زوج مرتب $(l, r)$ که نامساوی $1 \leq l \leq r \leq n$ در آن صدق می‌کند، مقدار $f(l, r)$ را برابر با تعداد زیر دنباله‌های دنباله‌ای به‌عنوان $a_l, a_{l+1}, \dots, a_r$ که جمع اعضایشان برابر $5$ است تعریف می‌کند. دقت کنید که یک زیر دنباله می‌تواند از دنباله اصلی با حذف برخی یا هیچ یک از عناصر ایجاد شود (بدون اینکه ترتیب عناصر باقی‌مانده تغییر کند).

دیو از صالح می‌خواهد که جمع همه $f(l, r)$ ها به ازای همه جفت‌های ممکن را حساب کند و باقیمانده آن را بر عدد $998244353$ به او بدهد. ازآنجایی که صالح قادر به حل این مسئله نیست، با محاسبه پاسخ این سوال به او کمک کنید تا از کابوسش فرار کند.

ورودی🔗

در خط اول ورودی، دو عدد $n$ و $S$ به شما داده می‌شود.

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

خروجی🔗

در تنها خط خروجی، جواب سوال را چاپ کنید.

محدودیت‌ها🔗

$1 \leq n \leq 3000$
$1 \leq S \leq 3000$
$1 \leq a_i \leq 3000$

مثال‌ها🔗

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

3 6
3 3 6

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

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

5 3
4 5 6 7 8

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

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

10 10
3 2 5 2 3 5 2 1 8 1

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

میراث

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

تاجر ثروتمندی به نام سینا صاحب یک ردیف شامل $n$ خانه متوالی به شماره‌های $1$ تا $n$ است. ارزش خانه $i$ ام برابر با $a_i$ است.
سینا می‌خواهد این ردیف را به $4$ بخش متوالی افراز کند و به هر یک از $4$ فرزند خود یکی از این بخش‌ها را به عنوان میراث بدهد.
همچنین او قصد دارد به طور عادلانه اینکار را انجام دهد. برای انجام این کار، سینا نیازمند است تا کمترین میزان اختلاف ممکن بین فرزندی که بیشترین ارث را می‌برد با فرزندی که کمترین ارث را می‌برد، مشخص کند.

به سینا کمک کنید تا وصیت‌نامه خود را بنویسد.

ورودی🔗

در خط اول عدد $n$ داده می‌شود.

سپس، در خط بعدی $n$ عدد که نشانگر دنباله $a_i$ ها است می‌آیند.

خروجی🔗

در تنها خط خروجی، کمترین اختلاف ممکن ارزش ارث بین فرزند با بیشترین ارث و فرزند با کمترین ارث را چاپ کنید.

محدودیت‌ها🔗

$4 \leq n \leq 2 \times 10^5$
$1 \leq a_i \leq 10^9$

مثال‌ها🔗

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

5
6 4 8 2 4

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

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

10
20 142 168 66 12 94 46 50 104 128

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

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

7
3 8 2 1000000000 9 2 1

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

999999997

جدول حریص

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

علی یک جدول $2×n$ دارد که هر سطر آن جایگشتی از اعداد $1$ تا $n$ است . او می خواهد تعدادی از خانه های جدول را حذف کند به شکلی که دو شرط زیر برقرار باشند:

• حداقل $k$ عدد دو به دو متمایز در جدول باقی بمانند.

• در هر ستون حداکثر یک عدد باقی بماند.

همچنین او می خواهد جمع اعداد باقی مانده در جدول بیشینه باشد. به او کمک کنید این مقدار بیشینه را بیابد

ورودی🔗

در خط اول ورودی دو عدد $n$ و $k$ داده می شوند. سپس، در خط دوم اعداد سطر اول جدول و در خط سوم اعداد سطر دوم جدول به شما داده می شوند.

خروجی🔗

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

محدودیت‌ها🔗

$1 \leq k \leq n \leq 5000$

مثال‌ها🔗

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

2 2
1 2
2 1

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

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

2 1
1 2
2 1

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

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

4 2
1 2 3 4
4 3 2 1