Loading [MathJax]/jax/output/HTML-CSS/jax.js

سوال ۱۰

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

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

پاسخ

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

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