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

ویروس جدیدی به جان سیستم رهنما افتاده است. نام این ویروس «کاپی» بوده و با کپی کردن فایل‌ها حافظه را پر میکند! نحوه‌ی کپی کردن «کاپی» هم به این صورت است که ابتدا یک عدد $n$ به صورت تصادفی انتخاب کرده و سپس فایلی را انتخاب کرده و آن را کپی می‌کند. بعد نام این فایل جدید را به این صورت انتخاب می‌کند که به تعداد $n$ بار اول اسمش عبارت copy of می‌آورد و سپس نام فایل اولیه را می‌آورد؛ برای مثال اگر فایلی به نام you را بخواهد کپی کند و عدد انتخابی سه باشد، نام فایل کپی شده برابر copy of copy of copy of you خواهد شد. (دقت کنید که بعد از هر عبارت copy of یک فاصله‌ می‌آید.)

متاسفانه حملات پی در پی آنتی‌ویروس‌های رهنما «کاپی» را ضعیف کرده است. با دادن نام فایل و تعداد بار کپی کردن فایل، نام فایل کپی شده را خروجی دهید.

ورودی🔗

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

$0 \le n \le 100$

خروجی🔗

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

مثال🔗

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

3 copyof

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

copy of copy of copy of copyof

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

1 shoma

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

copy of shoma

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

نقطه‌بازی یک بازی قدیمی است. این بازی معمولا بین دو بازیکن در یک صفحه $N \times M$ که شامل $N$ ردیف است که در هر ردیف $M$ نقطه است، انجام می‌شود. ردیف‌ها را از بالا به پایین با ۱ تا $n$ و ستون‌ها را از چپ به راست با ۱ تا $m$ نامگذاری می‌کنیم.

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

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

ما از شما می‌خواهیم به ناصر کمک کنید و برنامه‌ای بنویسید تا صرفا با گرفتن حرکات، نتیجه نهایی را برای ما محاسبه کند. ** (برای فهم بیشتر، شکلی که برای ورودی نمونه دوم کشیده شده را نگاه کنید.) **

ورودی🔗

در خط اول $n$ و $m$ که ابعاد صفحه هستند داده می‌شود. در $2\times n \times m - n - m$ خط بعدی در هر خط چهار عدد مانند $(x_{1} , y_{1} , x_{2} , y_{2})$ به شما داده می‌شود که به معنای این است که نقطه‌ی سطر $x_{1}$ و ستون $y_{1}$ به نقطه سطر $x_{2}$ و ستون $y_{2}$ با یک پاره‌خط متصل شد. همچنین تضمین می‌شود که ناصر و یاسر تنها حرکات مجاز انجام می‌دهند.(یعنی همواره پاره‌خط بین دو نقطه‌ی مجاور است که تا به حال بین آنها خطی کشیده نشده است.)

همچنین داریم: $2 \le n , m \le 200$ $1 \le x_{1} , x_{2} \le n$ $1 \le y_{1} , y_{2} \le m$

خروجی🔗

در یک خط دو عدد (که با فاصله از هم جدا شده‌اند) چاپ کنید که عدد اول امتیاز ناصر و عدد دوم امتیاز یاسر باشد.

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

2 2
1 1 1 2
1 2 2 2
2 2 2 1
2 1 1 1

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

0 1

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

2 3
1 1 2 1
1 2 2 2
1 2 1 3
1 1 1 2
2 1 2 2
2 2 2 3
1 3 2 3

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

1 1

شکل زیر نمایانگر بازی ورودی نمونه دوم است:

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

امروز , سالگرد تأسیس شرکت رهنماست به همین منظور چنگیز که از قدیمی‌های رهنما است مأمور می‌شود تا بین برنامه‌نویسان رهنما هدایایی به رسم یادبود پخش کند. شرکت رهنما $N$ برنامه‌نویس دارد که به هر کدام یک عدد یکتا بین $1$ تا $N$ نسبت داده شده است. برای گرفتن هدایا , برنامه‌نویسان رهنما یک صف تشکیل می‌دهند و به ترتیب شماره‌شان در آن قرار می‌گیرند به این صورت که برنامه‌نویس با شماره ۱ در ابتدای صف و برنامه‌نویس با شماره $N$ در انتهای صف قرار می‌گیرد. از آنجایی که چنگیز امروز به شرکت نیامده , تیمور را برای پخش جوایز مأمور می‌کند اما از طریق تلگرام به او فرمان می‌دهد که در هر مرحله چه کاری انجام دهد.

چنگیز به شدت رفیق باز است و ممکن است در صف دست ببرد.

چنگیز دو نوع فرمان به تیمور می‌دهد :

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

نوع دوم: به تیمور می‌گوید که برنامه‌نویس شماره $i$ را پیدا کند و به سر صف بیاورد.

بدیهی است که ممکن است یک نفر چند بار جایزه بگیرد.

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

ورودی🔗

در خط اول به شما دو عدد $N , C$ داده می‌شود که $N$ تعداد برنامه‌نویسان رهنماست و $C$ تعداد دستورات چنگیز است. در $C$ خط بعدی دستورات بعدی به شما داده می‌شود. در هر خط یک عدد مانند $x$ به شما داده می‌شود. اگر $x$ برابر صفر بود یعنی دستور نوع اول است در غیر اینصورت دستور از نوع دوم است و به این معناست که نفر $x$ ام باید به سر صف بیاید. $1 \le N \le 1\ 000\ 000\ 000$ $1 \le C \le 1\ 000$ $0 \le x \le N$ به محدوده $N$ توجه کنید.

خروجی🔗

به ازای هر دستور نوع اول , شما باید شماره فردی را که هدیه می‌گیرد در یک خط چاپ کنید. ( تعداد خط های خروجی برابر تعداد دستورات نوع اول می‌شود)

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

100000 6
0 
0 
10000
0
0
20

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

1
2
10000
3

در دو دستور اول به نفرات اول و دوم هدیه داده میشود. در دستور سوم نفر $1000$ ام به سر صف میاید. در دستور چهارم کسی که سر صف است , نفر $1000$ ام , هدیه اش را میگیرد و به ته صف میرود. در دستور پنجم نفر سوم که اکنون سر صف است هدیه میگیرد و به ته صف میرود. در دستور ششم هم نفر $20$ ام به سر صف میاید.

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

4 6
0
1
0
3
0
0

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

1
1
3
2

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

شرکتی اتاقی دارد که کف آن به شکل مستطیلی به ابعاد $h \times w$ می‌باشد و شرکت می‌خواهد آن را کاشی‌کاری کند. بچه های شرکت کاشی‌های یکسانی به شکل مربع خریده‌اند و باید تمام اتاق را با این کاشی‌ها بپوشانند. برای شروع این پروژه , آن‌ها مراسمی ترتیب دادند و شخص کارشناسی آمد تا کلنگ اولیه را بزند؛ اما چون با این کار زمین اتاق خراب می‌شود به جای اینکار اولین کاشی را در جای دلخواه خود قرار داد و شرکت تصمیم گرفت که تمام کاشی‌های دیگر در این اتاق را طوری بچیند که موازی با این کاشی باشد؛ یعنی ضلع‌های آن‌ها با ضلع‌های این کاشی موازی باشند. همچنین برای محکم شدن کاشی‌ها باید شرط زیر برقرار شود:

هر ضلع از هر کاشی باید حداکثر با یک کاشی دیگر مجاورت داشته باشد؛ یعنی مثلا حالت‌ زیر برای کاشی‌ها قابل قبول نیست:

در حالی که حالت‌ زیر قابل قبول است:

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

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

** دقت کنید که تنها کاشی‌هایی را بشمارید که یک ناحیه‌ی ناتهی از اتاق (مستطیل) را می‌پوشانند. (اشتراک خط یا نقطه تهی حساب می‌شود.) **

ورودی🔗

در سطر اول ورودی دو عدد $w$ و $h$ آمده است که به ترتیب نمایانگر طول و عرض کف اتاق می‌باشد.

سپس در سه سطر،‌ در هر سطر مختصات دکارتی یک گوشه از کاشی اولیه داده می‌شود. نحوه‌ی دادن مختصات این سه نقطه هم به این صورت است که نقطه‌ی پایین چپ مستطیل را نقطه‌ی $(0,0)$ قرار داده و طول و عرض مستطیل را به ترتیب محور $x$ و $y$ صفحه مختصات دکارتی در نظر می‌گیریم. حال در این صفحه‌ی مختصات، مختصات سه گوشه‌ی کاشی اولیه را می‌دهیم.

تمام مختصات‌های ورودی و ابعاد مستطیل صحیح می‌باشد. تضمین می‌شود که کاشی اولیه به طور کامل در داخل مستطیل جا می‌شود؛ یعنی حتی با اضلاع مستطیل هم برخورد نمی‌کند.

$3 \le h, w \le 100$

خروجی🔗

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

مثال🔗

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

4 3
1 1
2 1
2 2

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

12

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

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

5 4
1 2
2 1
2 3

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

15

توضیحات نمونه‌ی دوم:

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

خسرو که یکی از کارمندان منظم شرکت رهنما است، هر روز صبح نیم ساعت قبل از شروع ساعت کاری در شرکت حاضر شده و تا شروع ساعت کاری $minesweeper$ بازی می‌کند، اما اغلب اوقات بازی وی نیمه تمام می‌ماند.

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

** هر خانه از یک جدول $minesweeper$ : **

• یا شامل یک بمب است که در این صورت با کاراکتر ′∗′ نمایش داده می‌شود.

• یا شامل بمب نیست و تعداد ناصفری از خانه‌های مجاور رأسی آن (۸ خانه همسایه‌اش) شامل بمب‌اند که در این صورت با تعداد بمب های خانه‌های مجاور رأسی‌اش نشان داده می‌شود.

• یا نه خود شامل بمب است نه خانه های مجاور رأسی‌اش که در این صورت با کاراکتر ′.′ (نقطه) نمایش داده می‌شود.

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

*دقت کنید که شما فقط باید خانه‌های مجهول جدول را تکمیل کنید (تبدیل به ′.′ یا ′∗′ و یا عددی بین ۱ تا ۸ ) و باقی خانه‌ها را بدون تغییر رها کنید. دقت کنید که باید تمام خانه‌های مجهول را پر کنید. *

*برای آشنایی بیشتر با بازی minesweeper می‌توانید به اینجا مراجعه کنید. *

نمره‌دهی🔗

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

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

ورودی🔗

در خط اول ورودی دو عدد $n$ و $m$ که به ترتیب طول و عرض جدول است به شما داده می‌شود. $1 \le n, m \le 100$ در $n$ خط بعدی در هر خط $m$ کاراکتر می‌آید که جدول نیمه کاره $minesweeper$ را توصیف می‌کند.

اگر خانه‌ای حاوی بمب باشد کاراکتر ′*′

اگر خانه‌ای حاوی بمب نباشد و همچنین مجاور هیچ بمبی نباشد کاراکتر ′.′

اگر خانه‌ای مجاور تعدادی بمب باشد تعداد بمب های مجاور آن خانه (که عددی بین $1$ تا $8$ است)

و در نهایت اگر خانه‌ای هنوز باز نشده باشد و مجهول باشد کاراکتر ′?′ گذاشته می‌شود.

تضمین می‌شود که حداقل یک راه برای تکمیل جدول به صورتی که با شرایط گفته شده مطابقت کند وجود دارد.

خروجی🔗

در خط اول خروجی حداکثر تعداد بمب‌ها را چاپ کنید.

در $n$ خط بعدی در هر خط با $m$ کاراکتر جدول نهایی (حل شده) را مشخص کنید.

*جدول خروجی باید از کاراکتر‌های '.' و '' و اعداد ۱ تا ۸ تشکیل شده باشد و به ازای هر خانه شامل عدد تعداد خانه‌های مجاور رأسی شامل بمب آن خانه از عدد آن خانه بیشتر نباشد. **

مثال🔗

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

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

2 3
???
???

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

6
***
***

البته این خروجی هم یک جدول درست است:

0
888
888

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

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

3 3
?3*
*6*
***

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

6
13*
*6*
***

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

5 5
221..
?*?..
????.
***??
2321?

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

7
221..
**2..
**41.
***1.
2321.