نجات دامغان

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

محدودیت حافظه: 256 مگابایت

پس از بازگشت دامغانیاندی از عملیات موفق خود در قزاقستان، وی متوجه شد ناخواسته ویروس «۱۲۶-نا» (پسر عموی کرونا) را وارد دامغان کرده است.

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

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

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

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

ورودی

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

1 <= n <= 100

خروجی

در تنها سطر خروجی یک عدد چاپ کنید که کمینه‌ی تعداد بمب‌های ضد ویروس برای پاک‌سازی قطعی دامغان است.

ورودی نمونه ۱

4

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

2

توضیح:

ابتدا دامغانیاندی بر خانه‌ی قرمز در شکل «۱» بمب می‌اندازد. حال اگر ویروس در سه خانه‌ی سبز شکل «۲» باشد، می‌میرد. پس در نظر بگیرید در خانه‌ی غیر سبز باشد. پس از حرکت ویروس، می‌دانیم آن در خانه‌ی سیاه شکل «۳» نمی‌تواند حضور داشته باشد. پس دامغانیاندی بر خانه‌ی قرمز شده شکل «۳» بمب می‌اندازد تا مطمئن باشد ویروس می‌میرد.

ورودی نمونه ۲

7

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

4

ورودی نمونه ۳

2

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

1

تولد پیرهرات

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

محدودیت حافظه: 256 مگابایت

تولد پیرهرات نزدیک است و دامغانیاندی قصد تهیه‌ی کادو برای او را دارد. پس از صحبت‌های متعدد دامغانیاندی با آقا محمد، قرار بر این شد آرایه‌‌ی a به شکل <a₁,a₂,...,a_n> برای پیرهرات تهیه کنند تا او را خوش‌حال کنند.

از آنجایی که پیرهرات بسیار دنیا دیده است، می‌داند تنها آرایه‌های خاصی هستند که ارزش معنوی دارند. در نظر وی، یک آرایه ارزش معنوی دارد اگر و تنها اگر جایگشتی از {1,2,...,n} مانند <p₁,p₂,...,p_n> جود داشته باشد به طوری که به ازای هر

a_i + a_pi = a_j + p_j i,j ∈{1,2,3,...,n}

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

ورودی

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

1 <= n <= 2*10⁵

0 <= a <= 10⁹

خروجی

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

ورودی نمونه ۱

5
4 2 5 1 3

خروجی نمونه ۱

2 1 4 3 5

ورودی نمونه ۲

3
2 2 3

خروجی نمونه ۲

-1

میوه‌خوری باستانی

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

محدودیت حافظه: 256 مگابایت

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

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

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

مسابقه زمانی تمام می‌شود که میوه‌های یکی از دو ظرف بازیکنان تمام شده باشد. کسی که میوه‌های ظرفش تمام شود می‌بازد.

برای مثال، فرض کنید پیرهرات ظرفی با ۷ میوه و دامغانیاندی ظرفی با ۴ میوه داشته باشد.

1- در نوبت اول، پیرهرات ۴ میوه از ظرف خود می‌خورد. حال پیرهرات ۳ میوه و دامغانیاندی ۴ میوه دارد.

2- در نوبت دوم، دامغانیاندی ۳ میوه از ظرف خود می‌خورد. حال پیرهرات ۳ میوه و دامغانیاندی ۱ میوه دارد.

3- در نوبت سوم، پیرهرات ۱ میوه از ظرف خود می‌خورد. حال پیرهرات ۲ میوه و دامغانیاندی ۱ میوه دارد.

4- در نوبت چهارم، دامغانیاندی می‌بایست ۲ میوه از ظرف خود بخورد. چون کمتر از این مقدار میوه دارد، یک میوه می‌خورد و مسابقه به پایان می‌رسد.

از آنجایی که پیرهرات هم از رقابت و هم از برد خوشش می‌آید، دوست دارد در نهایت یکی از ظرف‌ها خالی و در ظرف دیگر دقیقا یک میوه باقی مانده باشد. به همین جهت، پیرهرات به یک جفت (a, b) جفت «هرات‌پسند» می‌گوید اگر در صورتی که ظرف دامغانیاندی a میوه و ظرف پیرهرات b یوه داشته باشد، بازی به شکل بیان شده به پایان برسد.

حال در مراسم اختتامیه‌ی عملیات فوق سری قزاقستان، n ظرف میوه چیده شده که در ظرف iام,jام میوه قرار دارد.

پیرهرات قصد دارد دو عدد i, j انتخاب کند که زوج (a_i, a_j) هرات‌پسند باشد و حالِ دامغانیاندی را بگیرد. به همین جهت به شما گفته یا چنین زوجی برای او پیدا کنید، یا بگوید نمی‌تواند حال دامغانیاندی را بگیرد.

ورودی

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

2 <= n <= 10⁵

1 <= a_i <= 10⁶

خروجی

در تنها خط خروجی، در صورتی که هیچ زوج هرات‌پسندی وجود نداشت کلمه‌ی impossible در غیر این صورت دو عدد i, j چاپ کنید که زوجی هرات‌پسند هستند.

ورودی نمونه ۱

4
1 12 67 8

خروجی نمونه ۱

impossible

ورودی نمونه ۲

5
1 1 12 67 8

خروجی نمونه ۲

2 1

ورودی نمونه ۳

6
1 5 6 7 90 8

خروجی نمونه ۳

2 6

تنبلی تیم فوق سری

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

محدودیت حافظه: 1024 مگابایت

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

حال که هر سه به آلماتی (شهر با شماره‌ی ۱) رسیده‌اند، نقشه‌ی قزاقستان را تهیه کرده و می‌خواهند به سمت آستانه (شهر با شماره‌ی n) حرکت کنند. نقشه‌ی قزاقزستان از n شهر و m اده‌ی یک‌طرفه بین شهر‌ها تشکیل شده‌است. هر جاده بین دو شهر قرار دارد و ممکن است از یک شهر به خودش جاده‌ای باشد و یا از شهر u به شهر v یش از یک جاده موجود باشد. به دلایلی نامعلوم، هر جاده با تعدادی از k رنگ موجود رنگ شده است.

به دلیل پیچیده بودن نقشه، هر سه نفر توافق کردند تا به شکل زیر حرکت کنند:

زمانی که در شهری مانند v قرار دارند، ابتدا شاختک یکی از k رنگ استفاده شده در نقشه را انتخاب کند. سپس پیرهرات و دامغانیاندی یکی از جاده‌هایی که از v شروع می‌شوند و رنگ انتخاب شده‌ی شاختک در آن‌ها به کار رفته است را برگزینند و هر سه از آن جاده بگذرند.

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

ورودی

در خط اول ورودی، سه عدد n تعداد شهر‌ها، m عداد جاده‌ها و k تعداد رنگ‌های به کار رفته در نقشه داده می‌شوند. در 2m خط بعدی، در هر دو خط توضیح یکی از جاده‌ها داده شده است.

در خط اول توضیح هر جاده، سه عدد u,vوt آمده که به ترتیب، شهر ابتدای جاده، شهر انتهای جاده، و مدت زمانی که طول می‌کشد از جاده عبور کنند می‌باشد.

در خط دوم، ابتدا یک عدد l نمایانگر تعداد رنگ‌های به کار رفته در جاده‌ی داده شده و سپس، l عدد a₁,a₂,...,a_l داده می‌شوند که شماره‌ی رنگ‌های به کار رفته در کشیدن جاده می‌باشند.

1 <= n,m <= 5*10⁵

1 <= k <= 1000

1 <= u,v <= n

1 <= t <= 10⁶

1 <= l <= k

1 <= a_i <= k,i ∈ {1,2,...,l}

مجموع l ها برای تمام جاده‌ها کوچک‌تر یا مساوی 5*10⁵ می‌باشد.

دقت کنید که جاده‌ها یک‌طرفه هستند.

دقت کنید ممکن است چند جاده از شهر u به شهر v وجود داشته باشد. همچنین ممکن است از شهری به خودش جاده وجود داشته باشد. ممکن است دو شهر x و y ای وجود داشته باشند که نتوان از x به y با استفاده از جاده‌ها رسید.

خروجی

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

ورودی نمونه ۱

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

خروجی نمونه ۱

14

ورودی نمونه ۲

3 4 3
1 2 300
2 1 2
2 1 2000
2 3 1
1 3 80
2 2 1
2 2 42
1 2

خروجی نمونه ۲

impossible

شاختک و ۱۲۶ مشکل

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

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

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

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

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

1- هر مستطیل روی یک مستطیل دیگر و یا روی زمین باید قرار داشته باشد.

2- هر مستطیل را می‌توان هم به صورت عمودی و هم به صورت افقی‌ روی برج قرار داد. (به شرطی که تمام قوانین دیگر رعایت شوند.)

3- تنها یک مستطیل می‌تواند روی زمین باشد.

4- برای هر مستطیل A می‌توان مستطیل B را روی آن گذاشت اگر و تنها اگر ضلعی که از مستطیل B روی ضلع مستطیل A قرار می‌گیرد، اکیدا از آن کوچک‌تر باشد.

5- همه مستطیل‌ها باید استفاده شوند.

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

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

ورودی

در خط اول ورودی، عدد آمده که نشان دهنده تعداد مستطیل‌‌هاست. در n خط بعدی، در هر خط ۲ عدد a و b آمده که نشان‌دهنده‌ی طول و عرض مستطیل iام است.

1 <= n <= 250 000

1 <= a,b <= 10⁹

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

خروجی

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

ورودی نمونه ۱

3
50000 160000
50000 100000
50000 100000

خروجی نمونه ۱

200000

شاختک و ۱۲۶ مشکل

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

محدودیت حافظه: ۱۰۲۴ مگابایت

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

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

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

سه قهرمان در یک تیم، و دیو سپید در تیم مقابل قرار دارند. دو تیم بر جدولی n * m ازی زیر را انجام می‌دهند.

1- ابتدا هر خانه از جدول پر یا خالی است.

2- هر تیم در نوبت خود یکی از خانه‌های خالی جدول را انتخاب کرده و نون‌ماستی‌ای در آن قرار می‌دهد. پس از این عمل، آن خانه دیگر پر محسوب می‌شود. هر نون‌ماستی‌، به غیر از نون‌ماستی‌ اول، می‌بایست در خانه‌ای مجاور با نون‌ماستی‌ای که تیم مقابل در نوبت قبلی قرار داده گذاشته شود. دو خانه را مجاور در نظر گیرید هرگاه ضلعی مشترک داشته باشند. تیم اول، اولین نون‌ماستی‌ را در خانه‌ای خالی و دلخواه می‌تواند قرار دهد.

3- بازی زمانی تمام می‌شود که بازیکنی نتواند نون‌ماستی‌ خود را در جدول قرار دهد. در چنین شرایطی، بازیکنی که نتوانسته است نون‌ماستی‌ را در جدول قرار دهد بازنده اعلام می‌شود.

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

به خانه‌ای از جدول، «آشپز‌باشی» گوییم هرگاه اگر تیم قهرمانان نون‌ماستی‌ اول خود را در آن خانه قرار دهد استراتژی برد داشته باشد. (به بیانی دیگر، در صورتی که نون‌ماستی‌ اول را در خانه‌ی مورد نظر قرار دهد، مجزا از نحوه‌ی بازی تیم مقابل همواره بتواند برنده باشد.)

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

ورودی

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

هر یک از n خط بعدی ورودی شامل رشته‌ای به طول m می‌باشد. j امین کاراکتر رشته‌ی i ام، وضعیت ابتدایی خانه‌ی سطر i و ستون j را نشان می‌دهد. اگر این کاراکتر برابر # باشد، یعنی خانه‌ی مورد نظر پر است و در صورتی که برابر . باشد، یعنی خانه‌ی مورد نظر خالی است.

1 <= n,m < 50

خروجی

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

ورودی نمونه ۱

3 3
..#
...
...

خروجی نمونه ۱

0

ورودی نمونه ۲

0

خروجی نمونه ۲

0

ورودی نمونه ۳

1 4
...#

خروجی نمونه ۳

2