مهسا.ق
کاربر فوقحرفهای
- ارسالها
- 1,098
- امتیاز
- 3,218
- نام مرکز سمپاد
- دبیرستان فرزانگان 1
- شهر
- تهران
- مدال المپیاد
- برنز کامپیوتر ۱۳۹۳
- دانشگاه
- دانشگاه تهران
- رشته دانشگاه
- نرم افزار
پاسخ : سوالات مرحله 2 - تشریحی
ولی کلا برا این که اثبات کنی نمی شه خیلی راحت می تونی انجام بدی! همین که ثابت کنی اول ترتیب انجام اعمال تاثیری نداره
بعد این طوری بگی که مثلا که a تا k داریم
مرحله اول یکی k نگه می داریم و a-1 تا k+1 تا اضافه می شه و a-1 تا 2k
مرحله بعدی یه دونه از هر کدوم از قبلیا حداکثر می مونه و می شه a-2 تا از k+2 , 2k+2, 2k+1 , 4k
حالا a-2 تا 2k+1 اگه a بیشتر از 3 باشه باید تغییر کنه که می شه a-3 تا 2k+2 , 4k+2
حالا تعداد 2k+2 ها می شه تا اینجا 2a-5
که مثلا اگه a بیشتر از 5 باشه می بینیم تعداد مساوی ها داره تو یه سری از این حرکات زیاد می شه و تا بی نهایت ادامه پیدا می کنه
اگه مساوی 5 باشه هم حتی درسته چون تعداد مساوی ها تغییری نمی کنه بازم ما می مونیم و 5 تا 2k+2
ینی الان با این استدلال ادعا می کنی می شه یا نمی شه؟به نقل از Rich for ever :بدون اکسترمال حل شد. :)
آخرین خونه ای که مهره داره رو در نظر میگیریم ، خونه i یعنی.
از ۱ تا i حرکتی که رو سوال میخواد روی همه خونه ها پیاده میکنیم.
حالا دوباره آخرین خونه ای رو در نظر بگیرید توش مهره هست به اسم j.
از i تا j دوباره کاری رو که میخواد سوال انجام میدیم روش.
توی این مرحله فاصله بین خونه هایی که توش مهره هست. یک هست.
یعنی اینکه خونه ها مجاور نیستن.
توی مرحله های بعدی فاصله های به ترتیب میشن ۲ و ۴ و ۸ و ۱۶ و ... یعنی توانی از دو.
تو هر مرحله تو خونه ی i + 1 تعداد مهره هایی که میره x - 1 تاعه. توی i + 2 تعداد مهره ها x - 2 تاس.
ولی اگه توی اون خونه ها مهره باشه تعداد مهره ها بیشتر میشه.
همینطور که جلو تر میریم تعداد مهره ها ۲ برابر میشه.
و تعداد خونه ها و تعداد مهره ها نامتناهیه.
خیلی بد توضیح دادم میدونم ولی خودتون فکر کنید ذیگه)
ولی کلا برا این که اثبات کنی نمی شه خیلی راحت می تونی انجام بدی! همین که ثابت کنی اول ترتیب انجام اعمال تاثیری نداره
بعد این طوری بگی که مثلا که a تا k داریم
مرحله اول یکی k نگه می داریم و a-1 تا k+1 تا اضافه می شه و a-1 تا 2k
مرحله بعدی یه دونه از هر کدوم از قبلیا حداکثر می مونه و می شه a-2 تا از k+2 , 2k+2, 2k+1 , 4k
حالا a-2 تا 2k+1 اگه a بیشتر از 3 باشه باید تغییر کنه که می شه a-3 تا 2k+2 , 4k+2
حالا تعداد 2k+2 ها می شه تا اینجا 2a-5
که مثلا اگه a بیشتر از 5 باشه می بینیم تعداد مساوی ها داره تو یه سری از این حرکات زیاد می شه و تا بی نهایت ادامه پیدا می کنه
اگه مساوی 5 باشه هم حتی درسته چون تعداد مساوی ها تغییری نمی کنه بازم ما می مونیم و 5 تا 2k+2
دوره بیست روز اول رو تا سوال 18، پاسخ تشریحی گذاشتیم ! 
![/m\](/forum/styles/yahmas/smiles/rock_on.gif "Rock On /m\")
یکم شک دارم)