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

Автор NALP, 14 лет назад, По-русски

Задача А -  "Внеземной разум"


Эта задача является на этом раунде "утешительной", и я надеюсь, что все ее решили. Но для тех, у кого по каким-либо причинам не получилось это сделать, давайте разберем ее решение.

Пусть входная последовательность называется a, а ее длина равна n. Тогда в некоторый массив запишем индексы x1, ..., xk в возрастающем порядке  - все позиции, где в последовательности a стоят символы '1'.

Тогда нужно проверить последовательность x1, ..., xk на то, является ли она арифметической прогрессией. Проще всего это сделать так: записать некоторую переменную d = x2 - x1, и проверить, выполняется ли для всех 1 ≤ i < k свойство d = xi + 1 - xi.

Если выполняется --- вывести "YES", иначе "NO".
Разбор задач Codeforces Beta Round 36
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как же все элементарно. А я не вчитался в задачу. Решал жестче: брал интервал между первым и вторым и вторым и третим и проверял повторяются эти интервалы в порядке, который задают первые три сигнала. 100101100101100101 - Yes.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Бывает :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Кстати, если руководствоваться конкретным смыслом задачи, то Вася не совсем точен.
      100101100101100101 - периодичность есть, а Вася посчитал бы их глупыми. Но это так лирическое отступление.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вася считает, что он нашел внеземной разум, если все полученные внеземные сигналы приходили с некоторой периодичностью, т. е. все интервалы между последовательными полученными сигналами равны между собой.

        вроде, все четко написано :)
        ну бывает-бывает :)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Написано четко, а человеческой невнимательности пофиг четко или не четко написано.) В общем закрыли тему: в флуд перетекет скоро.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я кстати при первом чтении тоже решил - тут надо проверять, что последовательность интервалов между соседними сигналами образует периодическую строку. Такая жесть, к счастью, не сходится с семплами :)