Блог пользователя nehalem

Убей Соника! [Головоломка]
Автор nehalem, 15 лет назад, По-русски

Нашел хорошую головоломку( спасибо SkidanovAlex ). Вот она http://5kr.mosuzedu.ru/serobur10/sonic.htm . Описание там же) 

Поймать Соника действительно реально, нужно лишь подумать. Если у кого совсем не получается, разгадка здесь http://rghost.ru/2977408. Удачи!)

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
А после того, как решите эту задачу, предлагаю подумать над следующей: пусть шахты расположены не одна за другой, а образуют произвольный граф. Для каких графов существует алгоритм, позволяющий за конечное число выстрелов гарантированно подстрелить Соника?
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    между прочим, неплохая задача для контеста ;)
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      http://acm.mipt.ru/judge/problems.pl?problem=040&CGISESSID=ff17b9c9d83084ccdc3a67b5e68480f2
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ссылка на тему "всё уже придумано до нас"? =)
        → Ответить
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          да, что то типа того:) во всяком случае, можно потом проверить свое решение
          → Ответить
          • 15 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Вообще, я впервые видел эту задачу во всероссийской (а может, всесоюзной) олимпиаде по математике.
            → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Прикольная игра, вот только я не сразу понял как играть.

Открылась флеш и там чувак куда-то летит, чё делать не понятно совсем.

Потыкал мышкой - ноль эффекта. Клавиши понажимал, подождал пару минут. Снова потыкал - ноль. Потом случайно как-то вернувшись откуда-то заметил что внизу есть цыфры!. Гениальное сочетание цветов.

→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо! День начинается с крови нелюбимого мной ежа :)
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А чего это вы так не любите ежей? Они хорошие =D Или вы только Соника? ))
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кстати ежик не случайно бегает ИМХО, т.к. первая моя стратегия это бомбить в бункер номер 4. она даёт вероятность убить ежа более чем 0.7 но толку ноль полсе десятка попыток. Еж бегает не случайно. Обман!

→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "Возможно, вам после нескольких попыток покажется, что Соником управляет не только датчик псевдослучайных чисел... Не будем спорить."
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я не знаю почему они это написали, но я тоже не верю. Ве первых, если он случайно двигался, я бы не всегда убивал его последним выстрелов. По вторых, если он не случайно двигался, было бы трудно проверить стратегию, поэтому лучше поставить какие-то евристики вместе с генератором случайных чисел.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится 
        if(attacked[curPos - 1]) 
    curPos++; 
else{
    if(attacked[curPos + 1]) 
        curPos--; 
    else
        curPos += (rand() % 2 == 0) ? (1) :  (-1);
        }
        → Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Не смог придумать сам. Честно написал динамику по маске за 5 минут и пойал ежика.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    как за меньше чем 13 ракет поймать?
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вы не могли бы напомнить идею этой динамики? Просто полгода назад прочитал ваш пост и тоже написал динамику, а сейчас никак не могу вспомнить как именно:-)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите пожалуйста решение, а то я себе мозг сломал)
P.S. ссылку на разгадку удалили(
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обновил ссылку)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо, а можно какае-то доказательсто или почему оно так?)
Вобще не могу понять:(
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Нужно действовать итеративно. На первом шаге нет смысла стрелять в клетки с номерами, отличными от 2 и 7. В этом можно убедиться, рассмотрев все возможные выстрелы и посмотрев, где может находиться Соник после удара ракеты. Только в двух случаях количество вариантов расположения Соника уменьшится с 8 до 7. 

    Далее, так же рассмотрим варианты для второй ракеты. Теперь у нас окажется всего один вариант, в зависимости от того, куда мы стреляли в первый раз. Потом посмотрим на третий шаг и т.д. 

    После 6 очевидных выстрелов догадаться до остальных не составляет особого труда :) Это всего лишь набросок решения, если нужно подробнее, я могу попытаться рассказать)


    → Ответить