سوال ۱۰

علیرضا در صفحه‌ی مختصات قرار دارد. او در هر حرکت می‌تواند از نقطه‌ی با مختصات صحیح $(a, b)$ به یکی از نقاط $\big((2a)\%1024,b\big)$ و یا $\big(a,(2b)\%1024\big)$ برود که در آن‌ها منظور از $x\%y$ باقی‌مانده‌ی تقسیم $x$ بر $y$ است. علیرضا یک نقطه‌ی $(x, y)$ برای شروع انتخاب می‌کند که $0 \le x \le 50, 0 \le y \le 100$ باشد. اگر $(u, v)$ نقطه‌ای با بیش‌ترین مجموع مختصه‌ها ($u+v$ بیشینه) در بین تمامی نقاط قابل رسیدن با حرکات بالا باشد، باقی‌مانده تقسیم $u+v$ بر $5$ چند است؟

  1. $0$
  2. $1$
  3. $2$
  4. $3$
  5. $4$

پاسخ

گزینه (۱) درست است.

در هر گام مولفه‌ی مورد تغییر مقدارش در نمایش مبنای دو یک واحد به سمت چپ شیفت پیدا می‌کند. پس بیش‌ترین $x$ قابل دسترسی به ازای مقدار اولیه‌ی ۶۳ است. به همین ترتیب برای $y$ ها ۳۱ است. لذا نقطه‌ی $(u,v)$ برابر (1008,992) است. لذا جواب برابر $0$ است.