e-olymp 6387. Острова в потоке данных

by

6

Задача

Задана последовательность целых чисел $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.

prb6387

Напишите программу, на вход которой поступает последовательность из $15$ неотрицательных целых чисел, где каждое число отличается от предыдущего не более чем на $1$, и выводит количество островов в последовательности.

Входные данные

Первая строка содержит количество тестов $p \ (1 \leqslant p \leqslant 1000)$.

Каждый тест состоит из одной строки. Она содержит номер теста $k$, за которым следует $15$ неотрицательных целых чисел, разделенных пробелом. Первое и последнее число последовательности равны $0$. Каждое число отличается от предыдущего не более чем на $1$.

Выходные данные

Для каждого теста вывести в отдельной строке его номер $k$, пробел, и количество островов в последовательности.

Тесты

№ Входные данные Выходные данные
1 4
1 0 0 1 1 2 2 1 1 0 1 2 2 1 1 0
2 0 1 2 3 4 3 2 1 2 3 4 3 2 1 0
3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0		 1 4
2 7
3 7
4 7
2 3
1 0 1 2 3 2 1 0 1 2 3 4 3 2 1 0
2 0 0 1 2 2 2 1 1 1 0 0 1 1 0 0
3 0 1 1 1 2 2 2 2 3 4 3 2 2 1 0		 1 7
2 3
3 4
3 6
1 0 1 2 2 2 3 4 5 6 5 4 3 2 1 0
2 0 1 0 0 0 0 1 1 1 0 1 2 1 1 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 1 2 3 4 5 6 7 6 5 4 3 2 1 0
5 0 1 0 1 2 1 0 1 2 2 2 1 0 0 0
6 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0		 1 6
2 4
3 0
4 7
5 5
6 2

Код

Решение

Для решения задачи следует выявить закономерность образования острова в последовательности. Рассмотрим подробно.
Начнем с набора наибольших чисел в последовательности. С двух сторон от него идут числа, меньшие на $1$, которые образуют между собой уже другой остров. И так пока по краям не будут нули. Соответственно, чтобы узнать количество островов в последовательности, необходимо посчитать сколько раз элемент последовательности (подпоследовательности) больше предыдущего.

Ссылки

Related Images:

6 thoughts on “e-olymp 6387. Острова в потоке данных”

    • Код по всем ссылкам должен совпадать с кодом в статье.
    • Метки (хештеги, ключевые слова) — это не перечень категорий.
    • Лучше описывать алгоритм, а не код. Простой код лучшее описание самого себя. Можно, конечно отметить какие-то особенности реализации, но лучше всего это делать в комментарии к коду. А в описании… Ну, пишите вы про цикл for, а в коде их четыре.
    • Вы используете 16 как т.н. magic number. Определите его при помощи #define
    • В 20-й строке цикл выполняется пока j<16. Значит в 21-й строке последнее значение x[i][j+1] будет выходить за пределы массива из 16-и элементов — x[i][16]. Выход за пределы массива может привести к непредсказуемым последствиям. Например, как у Вас — повезло и ничего не случилось. Но надо исправить.
    • Зачем Вам понадобился динамический многомерный массив? Каждый тест не зависит от остальных. Значит всего-то нужен массив на 16 элементов.
    • Зачем Вам понадобился массив на 16 элементов? 🙂 Если нужно сравнить числа, то это нужно делать сразу при чтении, а не запоминать их все.
    • «Если последующий элемент больше предыдущего, то образуется остров». Вы сделали замечательное наблюдение, что количество островов совпадает с тем, сколько раз последовательность возрастает. Это без шуток гениально. Но нигде не объяснили почему. Именно это и нужно сделать в объяснении. Вместо этого Вы просто пересказываете код. Если есть тонкий момент в коде — пишите в нем комментарии. В объяснении опишите алгоритм.
    • Почему в тестах нет теста с e-olymp? Вы нашли в нем ошибку?

    • Спасибо за подробное описание недочетов. Постаралась исправить все по-максимуму, но решение получилось только все же с использованием массива.
      Первый тест в таблице и есть тест с e-olymp, в нем ошибок я не находила.

    • Я обязан подробно объяснять 🙂

      • С тестом. Понял. Видимо, я что-то перепутал.
      • По поводу массива. В сравниваете первый элемент со вторым. И никогда больше не возвращаетесь к первому. потом сравниваете второй с третьим. И никогда больше не возвращаетесь ко второму. Зачем Вам их всех хранить? Если все еще не ясно, давайте представим себе, что Вам нужно посчитать сколько раз в толстой книге встречаются две одинаковые буквы подряд. Нужно ли Вам для этого будет сначала выучить всю книгу наизусть и уметь называть любую букву по ее номеру? Нет конечно! Значит массив здесь ненужен. Вот и у Вас так.
      • Выберите, пожалуйста, правильную категорию.
      • Очень важно выработать навык понятно объяснять сложные вещи. Пожалуйста, сделайте еще одну попытку объяснить свою идею решения. Сейчас объяснение ошибочно. Вы в нем никак не используете важные вещи в условии задачи. Именно они и позволяют так просто ее решить.
      • Старайтесь не пустословить в комментариях. Например, вместо «счетчик отвечающий за кол-во островов» лучше писать «счетчик островов».
      • Для количества тестов и номера теста автор задачи уже выбрал имена переменных. Нет никакого смысл их менять. И нет необходимость описывать это в коде повторно. Если есть необходимость или желание это сделать, описывайте каждую переменную в отдельной строке и коротко комментируйте. Например, «количество тестов» или «номер теста».

    • Еще раз большое спасибо. Исправила.

    • Спасибо. Сделаю все возможное.

Добавить комментарий