المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۵:سوال ۵

Kafsh

پژوهشگران بیوانفورماتیک(!)، وسیله‌ای به نام «مول‌یاب» ساخته‌اند تا برای همیشه کشاورزان را از معضل موش‌های کور، رهایی دهند. برای آزمایش این دستگاه، صفحه‌ی مختصاتی در نظر گرفته شده و موش‌کوری در یکی از نقطه‌های شبکه‌ای آن، پنهان شده است. شما باید برنامه‌ای بنویسید تا با قرار دادن مول‌یاب در نقطه‌های مختلف صفحه، مکان موش‌کور را پیدا کند. شما در هر مرحله می‌توانید مول‌یاب را روی یکی از نقطه‌های شبکه‌ای صفحه قرار دهید. اگر موش‌کور در نقطه‌ی $(x_1,y_1)$ و مول‌یاب در نقطه‌ی $(x_2,y_2)$ قرار داشته باشند، عدد $\left | x_1 - x_2\right | \bigoplus^1 \left | y_1 - y_2\right |$ روی دستگاه نمایش داده می‌شود. امتیاز برنامه‌ی شما با توجه به تعداد مرتبه‌هایی که از مول‌یاب استفاده می‌کند، محاسبه می‌شود.

نقطه‌ی $(x,y)$ را شبکه‌ای‌ می‌گوییم اگر هر دوی $x$ و $y$ صحیح باشند.

پیاده‌سازی

شما باید تابع $findMole()$ را پیاده‌سازی کنید. برنامه‌ی شما برای استفاده از مول‌یاب می‌تواند از تابع‌های $putMoleFinder(x,y)$ استفاده کند.

  • pair<int, int> findMole()

این تابع $t$ بار صدا زده خواهد شد. آن را طوری پیاده‌سازی کنید که مکان موش‌کور را برگرداند.

  • این تابع ورودی ندارد
  • int putMoleFinder(int x, int y)

این تابع یک واسط برای برقراری ارتباط با دستگاه مول‌یاب است. این تابع، عدد نشان‌داده شده بر روی مول‌یاب بعد از قرار دادن آن در نقطه‌ی $(x, y)$ را برمی‌گرداند.

  • $x$:طول نقطه‌ی مکان مول‌یاب
  • $y$:عرض نقطه‌ی مکان مول‌یاب

ارزیاب نمونه

ارزیاب نمونه ورودی را به صورت زیر می‌خواند:

در تنها خط ورودی دو عدد صحیح $x$ و $y$ آمده‌اند که به ترتیب نشان‌دهنده‌ی طول و عرض مکان موش‌کور هستند.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۲۰ نمره): $105 \le x$.
  • زیرمسئله‌ی دوم (۱۰ نمره): $71 \le x \le 104$.
  • زیرمسئله‌ی سوم (۳۱ نمره): $40 \le x \le 70$.
  • زیرمساله‌ی چهارم (حداکثر ۳۹ نمره): در این قسمت اگر $x \ge 40$ نمره‌ی شما برابر صفر و در غیر این‌صورت نمره‌ی شما برابر با $min(39, 71 - x)$ خواهد بود.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le t \le 1000$
  • طول و عرض مکان موش‌کور در بازه‌ی $[-10^9,10^9]$ قرار دارد.
  • برنامه‌ی شما تنها مجاز است دستگاه مول‌یاب را در نقطه‌‌ای که طول و عرضش در بازه‌ی $[-2 \times 10^9, 2 \times 10^9]$ است، قرار دهد.

ابزار صفحه