دارا و سارا (ترکیبیات) -- مرحله ی دوم سیزدهمین المپیاد کامپیوتر ایران --

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#1
دارا و سارا مشغول یک بازی هستند. در ابتدا یک صفحه ی شطرنجی نامتناهی خالی دارند و سارا 900 مهره دارد. در هر مرحله یکی از این دو عمل انجام می شود:
الف) سارا یک سطر از جدول انتخاب می کند و تعداد دلخواهی از مهره های خود را در خانه های دلخواهی از آن سطر قرار می دهد
ب)دارا یک ستون را انتخاب می کند و تعداد دلخواهی از مهره های آن ستون را برمی دارد.
بازی وقتی تمام می شود که همه ی مهره ها به دارا برسد.
شرط بازی آن است که هیچوقت نباید تعداد مهره های موجود در صفحه از 36 بیشتر شود. دارا و سارا می خواهند هرچه سریعتر این بازی را تمام کنند و به سراغ عروسک بازی بروند!!
الف) روشی ارائه دهید که دارا و سارا با استفاده از آن بتوانند با 230 تا 240 حرکت به مقصود برسند.
ب) روشی ارائه دهید که این کار را در کمتر از 230 حرکت انجام دهند.
 

Goharshady

New Member
ارسال ها
2,239
لایک ها
166
امتیاز
0
#2
راهنمایی :
با این روش می توان این کار را در 300 مرحله انجام داد
ابتدا سارا مهره ها را به صورت 6×6 بگذارد ، سپس دارا آنها را بردارد. یعنی برای هر 36 مهره 12 حرکت.
 
بالا