آشنایی با منچ


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

منچ یک بازی حداکثر ۴ نفره است. هر کدام از این ۴ بازیکن یکی از رنگ‌های «قرمز»، «آبی»، «سبز» و «زرد» را انتخاب می‌کنند و ۴ مهره با رنگ خودشان دارند که در ۴ گوشه‌ی صفحه قرار دارند. (جمعاً ۱۶ مهره) هدف این است که هر بازیکن ۴ مهره رنگ خودش را به ۴ خانه هم‌رنگ خودش در وسط صفحه برساند.

توضیح تصویر

بازی به نوبت انجام می‌شود، ابتدا نوبت بازیکن «قرمز»، سپس بازیکن «آبی»، بعد از آن بازیکن «سبز» و پس از آن نوبت بازیکن «زرد» است و همین ترتیب تکرار می‌شود.

هر کس در نوبت خودش تاس می‌اندازد. تاس عددی بین ۱ تا ۶ را نشان می‌دهد و می‌تواند مهره خودش را در جهت مشخص شده، به تعداد عدد ظاهر شده به جلو ببرد. هرکس برای اینکه یکی از مهره‌هایش را وارد نوار اصلی بازی کند، باید یک بار عدد ۶ بیاورد تا بتواند این کار را انجام دهد.

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

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

پروژه منچ: بخش ۱


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

از شما می‌خواهیم برنامه‌ای بنویسید که عدد ظاهر شده روی تاس را مانند ورودی‌های نمونه چاپ کند.

ورودی🔗

در تنها سطر ورودی، عدد صحیح و مثبت dd آمده، که نشان‌دهنده‌ی عدد ظاهر شده‌ی تاس است.

1d61 \leq d \leq 6

خروجی🔗

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

مثال🔗

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

1
Plain text

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

.....
.....
..o..
.....
.....
Plain text

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

2
Plain text

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

.....
...o.
.....
.o...
.....
Plain text

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

3
Plain text

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

.....
...o.
..o..
.o...
.....
Plain text

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

4
Plain text

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

.....
.o.o.
.....
.o.o.
.....
Plain text

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

5
Plain text

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

.....
.o.o.
..o..
.o.o.
.....
Plain text

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

6
Plain text

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

.....
.o.o.
.o.o.
.o.o.
.....
Plain text

پروژه منچ: بخش ۲


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

یکی از ابزارهایی که برای پیاده‌سازی بازی منچ به آن نیاز داریم، «تاس» است. به همین منظور، می‌خواهیم تابع get_dice را پیاده‌سازی کنیم. این تابع هیچ آرگومانی ورودی نمی‌گیرد. این تابع بعد از هر بار فرخوانی، مقدار عددی که روی تاس، بعد از انداختن ظاهر می‌شود را نشان می‌دهد.

برای رسیدن به این هدف، با داشتن سه عدد اول (primeprime) AA، BB و mm دنباله تصادفی XX را به این صورت می‌سازیم:

Xk={Bk=1(A.Xk1+B)modmk>1 X_k = \left\{ \begin{array}{lr} B & k = 1 \\ (A.X_{k-1} + B) \mod m & k > 1 \\ \end{array} \right.

حال از روی دنباله‌ی XX عدد ظاهر شده در پرتاب kkام را که با dicekdice_k نشان می‌دهیم؛ از این رابطه بدست می‌آید:

dicek=(Xkmod6)+1dice_k = (X_k \mod 6) + 1

از شما می‌خواهیم تابع get_dice را طوری پیاده‌سازی کنید که بعد از kk بار صدا کردن مقدار dicekdice_k را چاپ کند. یعنی در اولین فراخوانی get_dice، مقدار dice1dice_1، در دومین فراخوانی get_dice، مقدار dice2dice_2 و... برگردانده شود.

ورودی🔗

در سطر اول ورودی، به‌ترتیب سه عدد اول AA، BB و mm داده می‌شود. 2A,B<m9972 \leq A, B < m \leq 997

در سطر دوم ورودی، عدد صحیح و مثبت nn داده می‌شود. 1n1000001 \leq n \leq 100 \, 000

خروجی🔗

خروجی nn سطر دارد، عدد نوشته شده در سطر kkام مقدار تابع get_dice بعد از kk بار فرخوانی است.

مثال🔗

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

37 71 101
10
Plain text

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

6
1
3
5
4
3
4
4
3
4
Plain text

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

479 139 911
8
Plain text

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

2
2
1
2
5
4
6
4
Plain text

پروژه منچ: بخش ۳


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

در این بخش از پروژه، فرض کنید یک بازیکن داریم که تنهایی منچ بازی می‌کند. به‌طور دقیق‌تر، این بازیکن رنگ «قرمز» را انتخاب می‌کند؛ ۴ مهره قرمز، در ۴ خانه‌ی گوشه بالا سمت راست، قرار می‌دهد. این چهار مهره را با رشته‌‌های R1، R2، R3 و R4 نشان می‌دهیم.

این بازیکن qq درخواست دارد. هر درخواست در یک سطر ورودی داده می‌شود.

پرتاب تاس🔗

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

dice
Plain text

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

اگر عدد ظاهر شده از پرتاب‌های قبلی وجود دارد که هنوز حرکت متناسبی برای آن انجام نشده، پیام invalid dice rolling را در یک سطر چاپ کنید.

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

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

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

ورود مهره🔗

این درخواست یعنی بازیکن قرمز، می‌خواهد مهره‌ی mm را وارد بازی کند.

enter <m>
Plain text

تضمین می‌شود m یکی از مقدارهای R1، R2، R3 یا R4 باشد.

  • اگر مهره‌ی mm، در این لحظه در جریان بازی باشد؛ پیام that is in را در یک سطر چاپ کنید.
  • اگر در پرتاب‌های قبلی تاس، عدد ۶ ظاهر نشده باشد تا آن را برای ورود مصرف کنیم، پیام you need six را در یک سطر چاپ کنید.
  • اگر خانه‌ی اولیه برای شروع با مهره‌ی قرمز دیگری اشغال شده باشد، پیام busy starting cell را در یک سطر چاپ کنید.

اگر چند مورد از شرایط بالا برقرار بود، موردی که زودتر بیان شد را در نظر بگیرید و پیام آن را چاپ کنید.

در صورتی که هیچ‌کدام از حالت‌های بالا اتفاق نیافتد، یکی از ۶‌های ظاهر شده در پرتاب تاس را حذف کنید و مهره‌ی mm را وارد خانه اولیه قرمز (خانه ۱) کنید و شماره‌ی خانه‌ای که مهره وارد آن شده را در یک سطر چاپ کنید.

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

حرکت مهره🔗

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

move <m> <s>
Plain text

تضمین می‌شود m یکی از مقدارهای R1، R2، R3 یا R4 باشد. همجنین تضمین می‌شود s یکی از اعداد ‍11 تا 66 باشد.

  • این درخواست زمانی معتبر است که عدد ss در یکی از پرتاب‌های قبلی تاس، ظاهر شده باشد ولی از آن استفاده نشده باشد. اگر این درخواست معتبر نبود، پیام invalid move را در یک سطر چاپ کنید.
  • اگر مهره‌ی mm در چهار خانه‌ی گوشه جدول است، پیام it is not in را در یک سطر چاپ کنید.
  • اگر ss خانه بعدی آن وجود نداشته باشد. (به خانه‌های پایانی نزدیک باشیم.) پیام you can not move را در یک سطر چاپ کنید.
  • اگر خانه‌ی مقصد، توسط مهره‌ی قرمز دیگری اشغال شده است، پیام destination is busy را در یک سطر چاپ کنید.

اگر چند مورد از شرایط بالا برقرار بود، موردی که زودتر بیان شد را در نظر بگیرید و پیام آن را چاپ کنید.

در صورتی که هیچ‌کدام از حالت‌های بالا اتفاق نیافتد، یکی از ssهای ظاهر شده در پرتاب تاس را حذف کنید و مهره‌ی mm را ss واحد به جلو ببرید و شماره‌ی خانه‌ای که مهره وارد آن شده را چاپ کنید.

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

رها کردن🔗

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

giveup
Plain text

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

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

ورودی🔗

در سطر اول ورودی، به‌ترتیب سه عدد اول AA، BB و mm داده می‌شود. 2A,B<m9972 \leq A, B < m \leq 997

در سطر دوم ورودی، عدد صحیح و مثبت qq داده می‌شود. 1q1000001 \leq q \leq 100 \, 000

در qq سطر بعدی، در هر سطر، یکی از چهار درخواست که توضیح آن در متن سوال آمده می‌آید.

خروجی🔗

خروجی متناسب با هر درخواست را در یک سطر جداگانه چاپ کنید.

مثال🔗

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

37 71 101
14
dice
enter R2
move R2 1
dice
move R2 3
dice
move R2 5
dice
move R2 4
dice
giveup
move R2 3
dice
move R2 4
Plain text

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

6 1
1
2
3
5
5
10
4
14
3
invalid move
4
18
Plain text

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

479 139 911
8
move R3 2
enter R2
dice
dice
enter R4
giveup
enter R4
dice
Plain text

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

invalid move
you need six
2
invalid dice rolling
you need six
you need six
2
Plain text

پروژه منچ: بخش ۴


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

در این بخش می‌خواهیم بازی را برای چهار بازیکن پیاده‌سازی کنیم.

مهره‌های بازیکن «قرمز» R1، R2، R3 و R4 هستند که در ابتدا به ترتیب در خانه‌های 4141، 4242، 4343 و 4444 قرار دارند. خانه‌ی شروع برای «قرمز» 11 است. هدف بازیکن قرمز این است که این ۴ مهره را (به هر ترتیبی) به‌خانه‌های 4545، 4646، 4747 و 4848 ببرد.

مهره‌های بازیکن «آبی» B1، B2، B3 و B4 هستند که در ابتدا به ترتیب در خانه‌های 4949، 5050، 5151 و 5252 قرار دارند. خانه‌ی شروع برای «آبی» 1111 است. هدف بازیکن قرمز این است که این ۴ مهره را (به هر ترتیبی) به‌خانه‌های 5353، 5454، 5555 و 5656 ببرد.

مهره‌های بازیکن «سبز» G1، G2، G3 و G4 هستند که در ابتدا به ترتیب در خانه‌های 5757، 5858، 5959 و 6060 قرار دارند. خانه‌ی شروع برای «سبز» 2121 است. هدف بازیکن قرمز این است که این ۴ مهره را (به هر ترتیبی) به‌خانه‌های 6161، 6262، 6363 و 6464 ببرد.

مهره‌های بازیکن «زرد» Y1، Y2، Y3 و Y4 هستند که در ابتدا به ترتیب در خانه‌های 6565، 6666، 6767 و 6868 قرار دارند. خانه‌ی شروع برای «قرمز» 3131 است. هدف بازیکن قرمز این است که این ۴ مهره را (به هر ترتیبی) به‌خانه‌های 6969، 7070، 7171 و 7272 ببرد.

نکاتی که باید در این حالت در نظر بگیریم.

قوانین نوبت🔗

نوبت‌ها به ترتیب برای رنگ‌های «قرمز»، «آبی»، «سبز» و «زرد» است و بعد از یک دور گردش نوبت‌ها، مجدداً به همین ترتیب نوبت آن‌ها می‌شود. این روند تا آخر ادامه دارد.

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

سپس باید با سه درخواست «ورود مهره»، «حرکت مهره» و «رها کردن» همه‌ی حرکات تاسی که انداخته را تمام کند.

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

اگر نوبت یک رنگ باشد هر درخواستی که بخواهد باعث تغییر در وضعیت مهره‌های دیگر ایجاد کند باید با پیام it is not your turn را چاپ کنید.

قوانین حذف🔗

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

درخواست‌ها🔗

در خواست‌ها همان حالت‌های بخش قبلی را دارند ولی حالت‌های مهره (mm) می‌تواند هر کدام از ۱۶ رشته‌ی بالا باشد.

ورودی🔗

در سطر اول ورودی، به‌ترتیب سه عدد اول AA، BB و mm داده می‌شود. 2A,B<m9972 \leq A, B < m \leq 997

در سطر دوم ورودی، عدد صحیح و مثبت qq داده می‌شود. 1q10001 \leq q \leq 1000

در qq سطر بعدی، در هر سطر، یکی از چهار درخواست که توضیح آن در متن سوال آمده می‌آید.

خروجی🔗

خروجی متناسب با هر درخواست را در یک سطر جداگانه چاپ کنید.

مثال🔗

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

41 41 997
7
dice
enter R2
move R2 6
move R2 2
dice
enter B1
move B1 3
Plain text

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

6 6 2
1
7
9
6 3
11
14
Plain text

پروژه منچ: بخش ۵


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

در این بخش از پروژه، می‌خواهیم بعد از هر عملیات، چه موفق چه ناموفق وضعیت صفحه‌ی بازی نمایش داده شود.

صفحه بازی بدون مهره‌ها به صورت زیر است.

xx.xx.......oo.oo.oo.......xx.xx
xx.xx.......oo.xx.oo.......xx.xx
............oo.xx.oo............
............oo.xx.oo............
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
xx.xx.......oo.xx.oo.......xx.xx
xx.xx.......oo.oo.oo.......xx.xx
Plain text

هر دو خانه‌ی oo و xx یکی از خانه‌ها را نشان می‌دهد و . خالی بودن صفحه را نشان می‌دهد.

حال از شما می‌خواهیم وضعیت مهره‌ها در صفحه را به این صورت نمایش دهید.

مثال🔗

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

41 41 997
7
dice
enter R2
move R2 6
move R2 2
dice
enter B1
move B1 3
Plain text

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

6 6 2
R1.R2.......oo.oo.oo.......B1.B2
R3.R4.......oo.xx.oo.......B3.B4
............oo.xx.oo............
............oo.xx.oo............
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
Y1.Y2.......oo.xx.oo.......G1.G2
Y3.Y4.......oo.oo.oo.......G3.G4
1
R1.xx.......oo.oo.oo.......B1.B2
R3.R4.......oo.xx.oo.......B3.B4
............oo.xx.oo............
............oo.xx.oo............
R2.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
Y1.Y2.......oo.xx.oo.......G1.G2
Y3.Y4.......oo.oo.oo.......G3.G4
7
R1.xx.......oo.oo.oo.......B1.B2
R3.R4.......oo.xx.oo.......B3.B4
............R2.xx.oo............
............oo.xx.oo............
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
Y1.Y2.......oo.xx.oo.......G1.G2
Y3.Y4.......oo.oo.oo.......G3.G4
9
R1.xx.......R2.oo.oo.......B1.B2
R3.R4.......oo.xx.oo.......B3.B4
............oo.xx.oo............
............oo.xx.oo............
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
Y1.Y2.......oo.xx.oo.......G1.G2
Y3.Y4.......oo.oo.oo.......G3.G4
6 3
R1.xx.......R2.oo.oo.......B1.B2
R3.R4.......oo.xx.oo.......B3.B4
............oo.xx.oo............
............oo.xx.oo............
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
Y1.Y2.......oo.xx.oo.......G1.G2
Y3.Y4.......oo.oo.oo.......G3.G4
11
R1.xx.......R2.oo.B1.......xx.B2
R3.R4.......oo.xx.oo.......B3.B4
............oo.xx.oo............
............oo.xx.oo............
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
Y1.Y2.......oo.xx.oo.......G1.G2
Y3.Y4.......oo.oo.oo.......G3.G4
14
R1.xx.......R2.oo.oo.......xx.B2
R3.R4.......oo.xx.oo.......B3.B4
............oo.xx.oo............
............oo.xx.B1............
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
oo.xx.xx.xx.xx....xx.xx.xx.xx.oo
oo.oo.oo.oo.oo.xx.oo.oo.oo.oo.oo
............oo.xx.oo............
............oo.xx.oo............
Y1.Y2.......oo.xx.oo.......G1.G2
Y3.Y4.......oo.oo.oo.......G3.G4
Plain text