المپدیا

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

ابزار کاربر

ابزار سایت


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

خرگوش نامرئی

۱۳۹۱ سکو در یک ردیف قرار دارند و یک خرگوش نامرئی روی یکی از سکوها نشسته است. می‌خواهیم این خرگوش را شکار کنیم. در هر مرحله می‌توانیم به یکی از این سکوها شلیک کنیم. اگر خرگوش روی سکویی که به آن شلیک شده نشسته باشد، شکار می‌شود؛ در غیر این صورت به علت ترس از صدای تیراندازی، روی یکی از دو سکوی مجاورش (در صورت وجود) می‌پرد. روشی برای تیراندازی‌ها ارائه دهید که مطمئن باشیم بعد از حداکثر ۱۰۰۰۰ شلیک، خرگوش حتما شکار می‌شود.

پاسخ

سکو‌ها را از چپ به راست به ترتیب با اعداد $1$ تا $1391$ شماره گذاری می‌کنیم.
نکته: با هر بار شلیک ما زوجیت سکوای که خرگوش در آن است تغییر می‌کند.
حال الگوریتم زیر را اجرا می‌‎کنیم:
در بخش اول به ترتیب به سکو‎های $1$ تا $1391$ شلیک می‌کنیم. سپس در بخش دوم دوباره به ترتیب به سکوهای $1$ تا $1391$ شلیک می‎کنیم.

اثبات کارآمدی الگوریتم: روی سکو اولیه‎ای خرگوش حالت بندی می‌کنیم.

  • در اول کار خرگوش روی سکو‌ای فرد است: پس با هرباری که ما به سکو‌ای با شماره فرد شلیک می‌‌کنیم، خرگوش در سکو‌ای فرد و وقتی که ما به سکو‌ای زوج شلیک می‌کنیم خرگوش در سکو‌ای زوج است. حال چون ما در بخش اول الگوریتم از چب به راست به تمامی سکو‌ها شلیک می‌کنیم و پس طبق پیوستگی گسسته ما به سکوای با فاصله کمتر مساوی $1$ از سکو خرگوش شلیک خواهیم کرد. چون زوجیت سکوای که ما به آن شلیک می‎‌کنیم و سکو خرگوش یکسان است پس این فاصله نمی‌تواند $1$ باشد. پس حتماً $0$ خواهد بود. یعنی خرگوش کشته می‌شود.
  • اگر سکو اولیه خرگوش سکوای زوج باشد: بعد از $1391$ حرکت اول زوجیت سکو خرگوش تغییر خواهد کرد و سپس مانند استدلال قسمت بالا، اگر هم در بخش اول الگوریتم خرگوش کشته نشود، قطعاً در بخش دوم می‌شود.


در آخر تعداد حرکات ما $ 2 \times 1391 = 2782 $ و کمتر $10000$ خواهد بود.


ابزار صفحه