ای سی ام کار تازه وارد

لینک سوال

مفهوم سوال

سوال یه بازی دو نفره معرفی می کنه به این شکل:

یه صفحه N*N داریم و انگشت نفر اول روی خونه (1,1) این جدول قرار داره.

تو هر دور نفر دوم یه عدد مثل K اعلام می کنه و نفر اول باید دقیقا K بار انگشت خودش رو حرکت بده. تو هر حرکت فقط می تونه به یکی از 4 خونه همسایه که هنوز حذف نشدند بره.

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

سوال به ما N رو میده و می خواد به عنوان نفر دوم یه استراتژی ارائه کنیم که در آخر فقط 1 خونه باقی مونده باشه.

N < 100 و N <= K < 300

حل

اول برای هر خونه از جدول زوجیت رو به این شکل تعریف می کنیم:

خونه (i,j) رو زوج میگیم اگر زوجیت i,j با هم یکی باشه و در غیر این صورت خونه(i,j) رو فرد میگیم.

واضحه که اگه فرد حرکت انجام بدیم، زوجیت خونه ای که انگشت روش قرار داره عوض میشه.(در ابتدا روی خونه زوج قرار داره)

برای حالت های زوج و فرد از N مساله رو حل می کنیم.

اگر N زوج باشه:

شکل رو به صورت قطرهای فرعی درنظر بگیرید، اینجوری زوجیت قطرهای کنار هم با هم فرق داره.

مثلا برای N = 4

  1   2    3    4

  5   6    7    8

  9  10  11  12

13  14  15  16

اول N حرکت می کنیم، اینجوری همه خونه های با فاصله بیشتر از N از (1,1) رو می تونیم حذف کنیم.

بعد از 4 حرکت ، قطرهای (16) و (12,15) رو بدون مشکل می تونیم حذف کنیم.

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

حالا کافیه N+1 رو اعلام کنیم، اینجوری الان میدونیم انگشت روی یه خونه فرد قرار داره و می تونیم قطر (8,11,14) رو حذف کنیم. به همین ترتیب می تونیم اعداد فرد متوالی رو اعلام کنیم تا به قطر اول برسیم.

اگر N فرد باشه:

شکل رو لایه لایه(مثل پیاز) درنظر بگیرید.

مثلا برای N = 5

  1   2    3    4   5

  6   7    8    9  10

11  12  13  14  15

16  17  18  19  20

21  22  23  24  25

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

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

با تکرار این عمل چون N فرده، می تونیم به حالت 1 خونه ای برسیم.