پس از بازگشت دامغانیاندی از عملیات موفق خود در قزاقستان، وی متوجه شد ناخواسته ویروس «۱۲۶-نا» (پسر عموی کرونا) را وارد دامغان کرده است.
دامغان، شهری به شکل دایرهاست که خانه دور آن قرار دارند. او متوجه شد که افراد دقیقا یکی از خانههای دامغان به این ویروس مبتلا شدهاند. وی برای نجات شهر خود، دست به دامن شاختک شد. شاختک به دامغانیاندی قول تعدادی بمب ضد ویروس را داد.
دامغانیاندی در هر مرحلهی پاکسازی، یک خانه را انتخاب کرده و یکی از بمبهای ضد ویروس را داخل آن خانه میاندازد. با این کار، خانهی مورد نظر و دو خانهی مجاور آن دور دایره، پاکسازی میشوند. (به بیانی دیگر، اگر ویروس در آن خانهها باشد میمیرد.)
ویروس ۱۲۶-نا بسیار هوشمند بوده و پس از مطلع شدن از انفجار یک بمب، در هر مرحله یا در خانهی فعلی میماند و یا به یکی از دو خانهی مجاور میجهد. توجه کنید زمانی که ویروس از خانهی به خانهی بجهد، اهالی خانهی دیگر به ویروس مبتلا نخواهند بود و تنها اهالی خانهی مبتلا هستند.
از آنجایی که بمبهای ضد ویروس بسیار پر هزینه هستند، دامغانیاندی قصد دارد کمینهی تعداد بمبهای لازم برای پاکسازی قطعی دامغان را برای خرید محاسبه کند. این مقدار را برای او به دست آورید.
در تنها سطر ورودی عدد داده میشود که تعداد خانههای دامغان میباشد.
در تنها سطر خروجی یک عدد چاپ کنید که کمینهی تعداد بمبهای ضد ویروس برای پاکسازی قطعی دامغان است.
توضیح:
ابتدا دامغانیاندی بر خانهی قرمز در شکل «۱» بمب میاندازد. حال اگر ویروس در سه خانهی سبز شکل «۲» باشد، میمیرد. پس در نظر بگیرید در خانهی غیر سبز باشد. پس از حرکت ویروس، میدانیم آن در خانهی سیاه شکل «۳» نمیتواند حضور داشته باشد. پس دامغانیاندی بر خانهی قرمز شده شکل «۳» بمب میاندازد تا مطمئن باشد ویروس میمیرد.
تولد پیرهرات نزدیک است و دامغانیاندی قصد تهیهی کادو برای او را دارد. پس از صحبتهای متعدد دامغانیاندی با آقا محمد، قرار بر این شد آرایهی به شکل برای پیرهرات تهیه کنند تا او را خوشحال کنند.
از آنجایی که پیرهرات بسیار دنیا دیده است، میداند تنها آرایههای خاصی هستند که ارزش معنوی دارند. در نظر وی، یک آرایه ارزش معنوی دارد اگر و تنها اگر جایگشتی از مانند وجود داشته باشد به طوری که به ازای هر ،
حال آقا محمد آرایهای خریده و زمان آن رسیده که دامغانیاندی بررسی کند که آیا آرایه ارزش معنوی دارد یا خیر. دامغانیاندی که در حال آمادهسازی باقی ملزومات تولد است، از شما خواسته در پیدا کردن جایگشتای که به شرح فوق باشد به او کمک کنید یا بگویید چنین جایگشتی وجود ندارد.
ورودی تنها شامل دو خط است که در آنها عدد طبیعی و آرایه به ترتیب آمده است.
در صورتی که آرایه ارزش معنوی دارد، جایگشت خواسته شدهی آن را چاپ و در غیر این صورت -۱ خروجی دهید. در صورت وجود چند جایگشت مطلوب، یکی را به دلخواه خروجی دهید.
پای رقابت تنگاتنگ هرات و دامغان به قزاقستان هم باز شده و پس از کلکلهای فراوان دامغانیاندی و پیرهرات، تصمیم بر آن شد که بر حرفهای خود جامهی عمل بپوشانند و با هم مسابقه دهند.
مسابقه بدین صورت انجام میشود که پیرهرات و دامغانیاندی ظرفی از میوه جلوی خود دارند. به ترتیب با شروع از پیرهرات، به نوبت عملیات زیر را انجام میدهند.
مسابقه زمانی تمام میشود که میوههای یکی از دو ظرف بازیکنان تمام شده باشد. کسی که میوههای ظرفش تمام شود میبازد.
برای مثال، فرض کنید پیرهرات ظرفی با ۷ میوه و دامغانیاندی ظرفی با ۴ میوه داشته باشد.
در نوبت اول، پیرهرات ۴ میوه از ظرف خود میخورد. حال پیرهرات ۳ میوه و دامغانیاندی ۴ میوه دارد.
در نوبت دوم، دامغانیاندی ۳ میوه از ظرف خود میخورد. حال پیرهرات ۳ میوه و دامغانیاندی ۱ میوه دارد.
در نوبت سوم، پیرهرات ۱ میوه از ظرف خود میخورد. حال پیرهرات ۲ میوه و دامغانیاندی ۱ میوه دارد.
در نوبت چهارم، دامغانیاندی میبایست ۲ میوه از ظرف خود بخورد. چون کمتر از این مقدار میوه دارد، یک میوه میخورد و مسابقه به پایان میرسد.
از آنجایی که پیرهرات هم از رقابت و هم از برد خوشش میآید، دوست دارد در نهایت یکی از ظرفها خالی و در ظرف دیگر دقیقا یک میوه باقی مانده باشد. به همین جهت، پیرهرات به یک جفت جفت «هراتپسند» میگوید اگر در صورتی که ظرف دامغانیاندی میوه و ظرف پیرهرات میوه داشته باشد، بازی به شکل بیان شده به پایان برسد.
حال در مراسم اختتامیهی عملیات فوق سری قزاقستان، ظرف میوه چیده شده که در ظرف ام، میوه قرار دارد. پیرهرات قصد دارد دو عدد و انتخاب کند که زوج هراتپسند باشد و حالِ دامغانیاندی را بگیرد. به همین جهت به شما گفته یا چنین زوجی برای او پیدا کنید، یا بگوید نمیتواند حال دامغانیاندی را بگیرد.
در خط اول ورودی، که تعداد ظرفهای میوه است داده میشود. در خط دوم، عدد داده میشوند که عدد ام، تعداد میوههای ظرف ام است.
در تنها خط خروجی، در صورتی که هیچ زوج هراتپسندی وجود نداشت کلمهی impossible
و در غیر این صورت دو عدد چاپ کنید که زوجی هراتپسند هستند.
دقت کنید که ترتیب اعداد خروجی داده شده اهمیت دارد.
پس از شنیدن خبر اعزام به قزاقستان، شاختک سریعا چمدان خود را جمع کرد تا به سمت شهر آستانه راهی شود. دریغ از آنکه در این عملیات فوق سری و گروهی او با پیرهرات و دامغانیاندی، برای سفر هوایی نیاز به پاسپورت داشتند و دامغانیاندی تا به حال چیزی از پاسپورت نشنیده بود. به همین جهت، تصمیم بر آن شد به صورت زمینی خود را به یکی از شهرهای مرزی قزاقستان به نام آلماتی برسانند و از آنجا تا آستانه را پیاده بروند.
حال که هر سه به آلماتی (شهر با شمارهی ۱) رسیدهاند، نقشهی قزاقستان را تهیه کرده و میخواهند به سمت آستانه (شهر با شمارهی ) حرکت کنند. نقشهی قزاقزستان از شهر و جادهی یکطرفه بین شهرها تشکیل شدهاست. هر جاده بین دو شهر قرار دارد و ممکن است از یک شهر به خودش جادهای باشد و یا از شهر به شهر بیش از یک جاده موجود باشد. به دلایلی نامعلوم، هر جاده با تعدادی از رنگ موجود رنگ شده است.
به دلیل پیچیده بودن نقشه، هر سه نفر توافق کردند تا به شکل زیر حرکت کنند:
پیرهرات و دامغانیاندی که از سفر زمینی بسیار خسته شدهاند، قصد دارند در دیرترین زمان ممکن به آستانه برسند (یا کاری کنند که هیچگاه نتوان به آستانه رسید)، اما شاختک که بسیار مشتاق است، دوست دارد در نزدیکترین زمان ممکن به آستانه برود. در صورتی که هر دو گروه بازی بهینهای انجام دهند، تعیین کنید چه زمانی به آستانه میرسند. (یا بگویید هیچگاه به آستانه نمیرسند.)
در خط اول ورودی، سه عدد تعداد شهرها، تعداد جادهها و تعداد رنگهای به کار رفته در نقشه داده میشوند.
در خط بعدی، در هر دو خط توضیح یکی از جادهها داده شده است.
مجموع ها برای تمام جادهها کوچکتر یا مساوی میباشد.
دقت کنید که جادهها یکطرفه هستند.
دقت کنید ممکن است چند جاده از شهر به شهر وجود داشته باشد. همچنین ممکن است از شهری به خودش جاده وجود داشته باشد. ممکن است دو شهر و ای وجود داشته باشند که نتوان از به با استفاده از جادهها رسید.
در تنها سطر خروجی، زمانی که طول میکشد گروه از آلماتی (شهر با شمارهی ۱) به آستانه (شهر با شمارهی ) برسد را چاپ کنید. در صورتی که هیچگاه نمیتوان از آلماتی به آستانه رسید، عبارت impossible
را چاپ کنید.
فراموش نکنید که جادهها یکطرفه هستند.
شاختک که برای عملیاتی حیاتی به قزاقستان دو بعدی رفته بود، ناگهان یک دل نه صد دل عاشق پرنسسی شد و عملیات به کلی از یادش رفت.
پرنسس در ۱۲۶ امین طبقهی قلعهای بسیار بلند زندگی میکند و شاختک قصد دارد نامهی عاشقانهی خود را به دست او برساند. به همین جهت، مستطیل تهیه کرده تا با روی هم چیدن آنها، بتواند برجی بسازد تا خود را به پنجرهی اتاق پرنسس برساند.
از آنجایی که قزاقستان دو بعدی کشور زلزلهخیزی است، برای ساخت برج به نحوی که برج نریزد، قوانین زیر میبایست رعایت شوند.
شاختک هنگام خرید مستطیلها، دقت کرده روشی وجود داشته باشد که مستطیل مورد نظر با رعایت قوانین فوق بتوانند روی هم قرار گیرند.
شاختک که از ارتفاع طبقهی ۱۲۶ ام قلعهی پرنسس اطلاعی ندارد، قصد دارد با مستطیلهای خریداری شده بلندترین برج ممکن را بسازد. به او کمک کنید و طول بلندترین برج قابل ساخت را محاسبه کنید.
در خط اول ورودی، عدد آمده که نشان دهنده تعداد مستطیلهاست. در خط بعدی، در هر خط ۲ عدد و آمده که نشاندهندهی طول و عرض مستطیل ام است.
توجه کنید که ممکن است مشخصات دو مستطیل یکسان باشد.
طول بلندترین برج ممکن را خروجی دهید به طوری که تمام قوانین رعایت شود.
پس از سفر به قزاقستان و چشیدن طعم نونماستیهای قزاق، پیرهرات، شاختک و دامغانیاندی از هیچ تلاشی برای یافتن دستور پخت آن دریغ نمیکردند.
با تحقیقات میدانی بسیار، آنها متوجه شدند کتاب آشپزی بسیار نادری در غار دیو سپید وجود دارد که دستور پخت نونماستی در آن موجود است. برای به دست آوردن این کتاب سه قهرمان داستان باید به جنگ دیو سپید رفته و کتاب را از چنگ او خارج کنند.
از آنجایی که قهرمانان و دیو سپید از نبردهای خونین دل خوشی ندارند، تصمیم گرفتند با یک بازی، برندهی نبرد را تعیین کنند.
سه قهرمان در یک تیم، و دیو سپید در تیم مقابل قرار دارند. دو تیم بر جدولی بازی زیر را انجام میدهند.
پس از بحث و جدلهای فراوان با دیو سپید، قرار بر این شد تیم سه قهرمان بازی را شروع کند.
به خانهای از جدول، «آشپزباشی» گوییم هرگاه اگر تیم قهرمانان نونماستی اول خود را در آن خانه قرار دهد استراتژی برد داشته باشد. (به بیانی دیگر، در صورتی که نونماستی اول را در خانهی مورد نظر قرار دهد، مجزا از نحوهی بازی تیم مقابل همواره بتواند برنده باشد.)
حال جدول بازی به شما داده شده است. تعداد خانههای آشپزباشی جدول را بیابید و به تیم قهرمانان بگویید.
خط اول ورودی شامل دو عدد و که به ترتیب تعداد سطرها و ستونهای جدول است داده شده است.
هر یک از خط بعدی ورودی شامل رشتهای به طول میباشد. امین کاراکتر رشتهی ام، وضعیت ابتدایی خانهی سطر و ستون را نشان میدهد. اگر این کاراکتر برابر #
باشد، یعنی خانهی مورد نظر پر است و در صورتی که برابر .
باشد، یعنی خانهی مورد نظر خالی است.
در تنها سطر خروجی، یک عدد چاپ کنید که برابر تعداد خانههای برندهی جدول است.