Задача
Задана последовательность целых чисел $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.
Напишите программу, на вход которой поступает последовательность из $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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; #define AMNT 15 int main() { int p, k; int current, previous; cin >> p; while ( p--) { cin >> k; int isl = 0; cin >> current; // ввод 1-го элемента последовательности previous = current; for ( int j = 1; j < AMNT ; j++ ){ cin >> current; //ввод остальных элементов if ( current > previous ) { isl++; } previous = current; } cout << k << " " << isl << endl; } return 0; } |
Решение
Для решения задачи следует выявить закономерность образования острова в последовательности. Рассмотрим подробно.
Начнем с набора наибольших чисел в последовательности. С двух сторон от него идут числа, меньшие на $1$, которые образуют между собой уже другой остров. И так пока по краям не будут нули. Соответственно, чтобы узнать количество островов в последовательности, необходимо посчитать сколько раз элемент последовательности (подпоследовательности) больше предыдущего.
Ссылки
- Код на ideone
- Задача на e-olymp
- Засчитанное решение на e-olymp