.لینک‌های مفید برای شرکت در مسابقه:

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

زمین ترب


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

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

زمینی که علی خریده است یک مستطیل n×mn \times m است. این زمین دارای nmnm قطعه است. قطعات این زمین به صورت یک جدول با nn سطر و mmستون است. در هر قطعه از این زمین می‌توان یک ترب کاشت یا آن را خالی گذاشت.

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

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

ورودی🔗

در تنها سطر ورودی سه عدد صحیح nn و mm و ss با فاصله از هم آمده است که نشان دهنده ابعاد زمین علی و تعداد قطعاتی است که می‌خواهد در آن‌ها ترب بکارد. 1n,m1001 \le n, m \le 100 0snm0 \le s \le nm

خروجی🔗

در خط اول خروجی در صورت امکان پذیر بودن این کار کلمه possible و در صورت ممکن نبودن کلمه impossible را چاپ کنید.

در صورت امکان پذیر بودن باید در nn سطر بعدی و در هر سطر یک رشته از mm کاراکتر بدون فاصله چاپ شود.اگر در قطعه سطر iiام ستون jjام ترب کاشته شود کاراکتر T و در صورت خالی بودن آن کاراکتر E را چاپ کنید.

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

مثال🔗

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

3 3 5
Plain text

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

possible
TTT
ETE
ETE
Plain text

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

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

4 4 1
Plain text

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

impossible
Plain text

هیچ روشی برای کاشتن ترب در زمین کشاورزی وجود ندارد.

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

2 3 1
Plain text

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

possible
EEE
ETE
Plain text

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

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

2 2 2
Plain text

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

possible
TE
TE
Plain text

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

قسمت آموزشی🔗

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

راهنمایی ۱

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

راهنمایی ۲

اگر nn و mm زوج باشند، می‌دانیم که حتما ss هم باید زوج باشد تا بتوانیم جدول مورد نظر را بسازیم. در این صورت می‌توانیم سطرها را به دو نیمه بالا و پایین تقسیم کنیم و به هر قسمت، نیمی از ترب‌ها را اختصاص دهیم.

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

راهنمایی ۳

حال به بررسی حالاتی می‌پردازیم که حداقل یکی از nn و mm فرد است. فرض کنیم nn فرد است (اگر نبود، همه این کارها را به صورت ستونی انجام دهید).

در ابتدا سطر وسط را در نظر می‌گیریم و شروع به پر کردن آن می‌کنیم. اگر ترب‌ها در سطر وسط جا می‌شدند که همه را همان‌جا می‌گذاریم. در غیر این صورت،‌ بیشترین تعداد ترب را در آن‌جا می‌گذاریم به‌طوری که تعداد ترب‌های باقی‌مانده زوج باشد (این تعداد بسته به زوجیت ss تعیین می‌شود و برابر mm یا m1m - 1 است).

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

ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.