المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۲

سلطان در نقطه‌ی ۰ از محور اعداد صحیح قرار گرفته است و گرفتار ۹ غول خطرناک با شماره‌های ۱ تا ۹ شده است. غول‌ها دو نوع هستند: دسته‌ی نخست، غول‌های راست‌گرا که دستور می‌دهند سلطان ۲ واحد به راست برود و دسته‌ی دوم غول‌های چپ‌گرا که دستور می‌دهند سلطان ۱ واحد به چپ برود.

کار در ۹ مرحله انجام می‌شود. در مرحله‌ی $i$ ام، غول شماره‌ی $i$، دستور مورد نظر را (بر اساس راست‌گرا یا چپ‌گرا بودنش) به سلطان می‌دهد. سلطان می‌تواند به دستور غول عمل کند یا این که غول را بکشد و جابه‌جا نشود. اگر سلطان یکی از غول‌ها را بکشد، خسته می‌شود و ۲ غول بعدی را نمی‌تواند بکشد. در صورتی که در انتها، سلطان در خانه‌ی ۰ مختصات باشد، آزاد می‌شود و در غیر این صورت، زندانی می‌ماند. سلطان تنها می‌داند که $k$ تا از غول‌ها راست‌گرا هستند و $9-k$ غول دیگر، چپ‌گرا هستند، اما شماره‌ی غول‌ها را نمی‌داند و طبیعتا از ابتدا نمی‌داند که در مرحله‌ی $i$ ام چه غولی دستور خواهد داد. به ازای چند عدد صحیح $k$ با شرط $0\leq k \leq 9$ ، سلطان الگوریتمی دارد که بتواند به طور تضمینی آزاد شود؟

  1. ۱
  2. ۲
  3. ۰
  4. ۳
  5. ۴

ابزار صفحه