المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۱:سوال ۴

راهپیمایی در صحرای ارواح

روح خبیس که از حاضرجوابی ‎آیدین‎ خسته شده بود، او را به صحرای بزرگ ارواح برد و در آنجا رهایش کرد. ‎آیدین‎‎ که هنوز گیج بود، خودش را در صحرایی مه‌آلود یافت که کف آن به‌جای شن، گل و لای بود. تنها نکته مهم این بود که دقیقاً جلوی جایی که او افتاده بود، یک تابلوی راهنما قرار داده شده بود که بالای آن نوشته شده بود: «‎ فاصله تا خروج از صحرا: ‎$2000000000$‎ گام!». زیر تابلو اما، جزئیات بیشتری به شرح زیر نوشته شده بود: ‎

  • آیدین‎ به این راهنما اعتماد کن‎! (چاره‌ی دیگری هم نداری البته‎!‎)
  • ‎ تو الان در مختصات صفر و صفر (مرکز صحرا) هستی. این صحرا نامحدود هست. الان هم که این تابلو را داری می خوانی رویت به سمت شمال (‎$y$‎‎ بیشتر) است.
  • ‎ تو باید در هر گام ابتدا به سمتی که رویت هست یک گام برداری و بعد از پیمودن آن یک گام، دقیقاً ‎۹۰‎ درجه به سمت راست خودت بچرخی.
  • تو هرگز نباید به خانه‌ی تکراری بروی‎!‎ اگر دیدی با برداشتن گام به خانه‌ای می‌روی که قبلاً در آن بوده‌ای (جای پایت روی گل و لای مانده) باید به‌جای پیمودن گام، این بار ‎۱۸۰‎ درجه رویت را بچرخانی (تو گویی اصلاً از اول چرخشت به جای به سمت راست، سمت چپ بوده) و بعد گام را بپیمایی. می‌توانی مطمئن باشی که با این چرخش ‎۱۸۰‎ درجه حتماً جلویت یک خانه‌ی غیرتکراری خواهد بود و گام را می‌توانی برداری.
  • ‎۲۰۰۰۰۰۰۰۰۰ (دو میلیارد) گام بپیما. ما آن‌جا منتظرت هستیم‎!‎ ‎

آیدین‎ می‌دانست صدها سال طول می‌کشد تا دو میلیارد گام را بپیماید. اما دوست داشت بداند در پایان این گام‌ها در کجا خواهد بود که مستقیماً به آن مکان برود. اگر مکان پایانی را با مختصات ‎$(F_x,F_y)$‎ نشان دهیم، مقدار ‎$|F_x \times F_y|$ (قدر مطلق‌ حاصل‌ضرب دو مختصه‌ی نقطه‌ی نهایی) را ‎$D$‎ می‌نامیم. باقی‌مانده‌ی تقسیم ‎$D$‎ بر ‎$\Delta$‎ چند است؟

صرفاً برای رفع ابهام: در پایان گام‌های اوّل تا ششم، ‎آیدین‎ به ترتیب در خانه‌های ‎$(0,1)$‎، ‎$(1,1)$‎، ‎$(1,0)$‎، ‎$(2,0)$‎، ‎$(2,-1)$‎ و ‎$(1,-1)$‎ خواهد بود. ادامه مسیر را خودتان بیابید‎.‎


ابزار صفحه