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

سینا می‌خواهد دیوار خانه‌اش را رنگ کند، دیوار او به صورت یک جدول $n \times m$ است. برای این کار در هر مرحله سطل رنگی برمی‌دارد و یک زیر جدول مربعی از دیوار را با آن رنگ رنگ‌آمیزی می‌کند. (ممکن است خانه‌ای چندین بار رنگ‌آمیزی شود) حال او کنجکاو شده که تعداد رنگ‌های مختلف روی دیوار را بیابد به او در یافتن این تعداد کمک کنید!

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

ورودی🔗

در خط اول ورودی به ترتیب $n$، $m$ و $k$ آمده که نشان دهنده‌ی تعداد ردیف‌های جدول، تعداد ستون‌های جدول و تعداد سطل‌های رنگی است که سینا استفاده می‌کند.

$1 \le n,m,k \le 50$

در خط $i$ام از $k$ خط بعدی به ترتیب $r_i$، $c_i$ و $l_i$ آمده که نشان دهنده‌ی شماره‌ی سطر و ستون خانه‌ی بالا چپ مربع و طول ضلع آن است.

$1 \le r_i \le n$ $1 \le c_i \le m$ $1 \le r_i + l_i - 1 \le n$ $1 \le c_i + l_i - 1 \le m$ $1 \le l_i \le \min(n, m)$

خروجی🔗

در تنها خط خروجی تعداد رنگ‌های مختلف روی دیوار را خروجی دهید.

مثال🔗

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

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

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

7

شکل دیوار به صورت زیر است: در هر خانه شماره سطل‌هایی که آن خانه توسط‌شان رنگ شده نوشته شده است. حال به ازای هر خانه رنگ آن را در نظر می‌گیریم (در واقع رنگ یک خانه مجموعه سطل‌هایی است که با آن رنگ شده) و مجموعه‌های مختلف ایجاد شده را میشماریم. $\{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1, 2, 3\}$

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

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

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

4

در این مثال رنگ‌های مختلف به صورت زیر است: $\{1\}, \{2\}, \{3\}, \{2,3\}$

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

آرپا در مسیر رشد خود در هاگوارتز $n$ مانع می‌بیند. هر کدام از این موانع که با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند، عددی به عنوان برچسب دارند به‌طوری‌که آرپا با حذف مانع $i$ام به اندازه حاصل ضرب برچسب مانع $i - 1$ و $i + 1$ انرژی می گیرد. دقت کنید او نمی‌تواند موانع اساسی که مانع اول و آخر هستند را حذف کند. بیشترین انرژی‌ای که آرپا پس از حذف $n - 2$ مانع می‌تواند داشته باشد چه‌قدر است؟

ورودی🔗

در خط اول ورودی عدد $n$ به شما داده می‌شود که نشان‌دهنده‌ی تعداد موانع است. در خط بعدی $n$ عدد که با فاصله از هم جدا شده‌اند به شما داده می‌شوند که عدد $a_i$ نشان‌دهنده‌ی برچسب مانع $i$ام است. $3 \le n \le 50$ $1 \le a_1, a_2, ... , a_n \le 1000$

خروجی🔗

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

مثال🔗

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

4
1 2 3 4

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

12

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

5
100 2 1 3 100

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

10400

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

میان‌ترم‌ها تمام شده ونمرات کلاس احتمال دکتر بابایی اصلن مطلوب نبوده‌است و استاد مطابق معمول یک پروژه ساده به بچه‌ها داده تا بتوانند حداقل ۲ نمره بیشتر به‌دست بیاورند.

پروژه به این صورت است که چند عدد صحیح در نظر گرفته‌ می‌شوند که میزان سود یا ضرر شرکت در روزهای متوالی است (واحد اعداد میلیون تومان است). در خروجی باید گفت بیشترین سود شرکت چقدر بوده است. مثلاً اگر داشته باشیم: $1,2,-5,4,-3,$.

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

ورودی🔗

در خط اول ورودی تعداد روزهایی که قرار است سود و ضرر و در ادامه آرایه‌ی سود و ضررها در این روزها گرفته می‌شود.

$1 \le n \le 4000$

خروجی🔗

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

مثال🔗

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

12
7 -1 -2 1 5 -11 9 1 4 -1 3 -10

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

16

توضیح خروجی: بیشترین سود شرکت در روزهای ۷ تا ۱۱ است که مجموع اعداد شماره ۷ تا ۱۱ برابر ‍۱۶ است.

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

5
-5 -2 -9 -1 -3

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

0

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

سینا متقاضی عضویت در انجمن علمی است. در روز سوم مصاحبه، سازمان ادبیات او را مورد بررسی قرار داده است.

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

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

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

ورودی🔗

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

سپس در $5n$ سطر بعدی، پنج بار و هر بار در $n$ سطر و در هر سطر یک بیت از شعر آمده است. ابیات را با اعداد صحیح متمایز بین ۰ و $10^9$ مشخص میکنیم.

$1 \le n \le 20000$

خروجی🔗

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

ورودی نمونه🔗

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

خروجی نمونه🔗

1
2
3
4
5

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

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

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

مغازه‌ی ای که سینا در آن کار میکند تیله‌ها را در $n$ اندازه مختلف عرضه میکند و هر تیله میتواند دارای پر باشد یا نباشد. پس در این مغازه میتوان $2n$ نوع تیله مختلف یافت.

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

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

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

ورودی🔗

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

در سطر دوم ورودی عدد $m$ آمده است که نمایانگر تعداد مشتری‌های ثابت مغازه‌ی سینا است.

سپس در $i$مین سطر از هریک از $m$ سطر بعدی، فهرست انواع تیله‌هایی که مشتری ثابت $i$م دوست میدارد توصیف میشود. در ابتدای سطر عدد $k_i$ آمده که برابر تعداد انواع تیله‌هاییست که این مشتری دوست میدارد. سپس $k_i$ نوع تیله بصورت دو عدد اندازه و پردار بودن توصیف شده اند. اندازه عددی طبیعی و حداکثر برابر $n$ است و پردار بودن اگر برابر ۱ بود، یعنی این مشتری تیله‌ی پردار از این اندازه را دوست میدارد و اگر برابر ۰ بود، یعنی تیله بی‌پر از این اندازه را دوست میدارد. (ممکن است مشتری از یک اندازه هم تیله‌ی پردار و هم تیله‌ی بی‌پر را دوست داشته باشد. این در دو توصیف مختلف در این سطر، گفته میشود. یکی برای تیله‌ی پردار با این اندازه و دیگری برای توصیف تیله‌ی بی‌پر با این اندازه.)

تضمین میشود هر مشتری حداکثر یک نوع تیله‌ی پردار را دوست دارد و هیچگاه یک نوع تیله دوبار در فهرست علایق یک مشتری ظاهر نمیشود.

$1 \le n, m \le 2000$

$1 \le k_i \le 3000$

$\sum_{i = 1}^m k_i \le 3000$

خروجی🔗

اگر نمیتوان بدون ناراحت کردن مشتری‌های ثابت فهرست تیله‌ها را انتخاب کرد، خروجی باید تنها شامل کلمه‌ی IMPOSSIBLE شود.

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

مثال🔗

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

1
2
1 1 0
1 1 1

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

IMPOSSIBLE

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

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

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

1 0 0 0 0

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

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

ورودی🔗

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

خروجی🔗

در تنها خط خروجی باید ترتیب مناسبی از کتاب ها برای این که خر ما گاز بزند چاپ شود و اگر چنین ترتیبی وجود نداشت عبارت "Impossible" چاپ شود.

مثال🔗

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

5 2

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

1 4 2 5 3

اگر خر ما کتاب ها را به این ترتیب گاز بزند اختلاف اعداد کتاب های متوالی به ترتیب ۳، ۲، ۳ و ۲ می‌شود و بنابراین اعداد کتاب های متوالی حداقل ۲ تا اختلاف خواهند داشت.

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

2 2

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

Impossible

در این صورت چه کتاب ها به ترتیب [2, 1] و چه به ترتیب [1, 2] گاز زده شوند، اختلاف اعداد کتاب اول و دوم کمتر از ۲ می‌شود.