المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۰:سوال ۷

لاک‌پشت‌های عاشق

سه لاک‌پشت با شماره‌های ۱ و ۲ و ۳ به ترتیب در مختصات $(1024,2010)$ و $(-1381,138)$ و $(1,2010)$ (روی صفحه محورهای مختصات) قرار گرفته‌اند. می‌دانیم لاک‌پشت شماره‌ی ۱، عاشق لاک‌پشت شماره‌ی ۲ است! شماره‌ی ۲ هم عاشق ۳ است و شماره‌ی ۳ عاشق شماره‌ی ۱!

هر لاک‌پشتی قصد دارد به معشوقش برسد! برای این منظور در ابتدای هر ثانیه سرش را بالا می‌گیرد و بسته به مکان معشوقش، یا همان سر جای خود و یا یکی از ۸ خانه مجاورش را به عنوان مقصدش انتخاب می‌کند. سپس در انتهای ثانیه، سرش را پایین می‌اندازد و به مقصد خود می‌رود.

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

برای مثال در پایان ثاینه اول سه لاک‌پشت به ترتیب در مختصات $(1023,2009)$ (اولی) و $(-1380,139)$ (دومی) و $(2,2010)$ (سومی) خواهند بود.

می‌خواهیم بدانیم در پایان چندمین ثانیه، لاک‌پشت‌ها به پایداری می‌رسند (و بعد از آن دیگر هرگز هیچ‌کدام‌شان تکان نخواهند خورد). اگر پایداری در پایان ثانیه‌ی $S$‌ رخ می‌دهد، باقی‌مانده‌ی $S^6$ بر $\Delta$‌ چند است؟


ابزار صفحه