Задача A288
Условие задачи
Даны целые числа [latex]a_{1}[/latex], …, [latex]a_{n}[/latex], каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, –, +, –, или –, +, –, +, … ), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <vector> #include <iostream> using namespace std; int main() { vector <int> a, b; bool alternate = true; //переменная, которая изменяет свое значение, в зависимости от того, чередуются знаки (true) или нет (false) int a1; //первый элемент cin >> a1; int tester = a1; //в переменной хранится значение, с которым будут сравниваться последующие if (a1 > 0){ b.push_back(a1); } else if (a1 < 0){ a.push_back(a1); b.push_back(a1); } int n; while (cin >> n){ if (n > 0){ b.push_back(n); } if (n < 0){ a.push_back(n); b.push_back(n); } if (tester*n > 0) alternate = false; //если встретили два значения подряд одного знака tester = n; } if (alternate == true){ for (int i = 0; i < b.size(); i++){ cout << b[i] << " "; } } if (alternate == false){ for (int i = 0; i < a.size(); i++){ cout << a[i] << " "; } } return 0; } |
Тесты
| Входные данные | Выходные данные |
| 5 5 3 1 2 7 8 100000 | |
| -9 -5 -1 -3 -7 -4198 -852 | -9 -5 -1 -3 -7 -4198 -852 |
| 5 -3 1 81 3 -7 1 -5 6 | -3 -7 -5 |
| -1 2 -8 995 -3 777 -42 | -1 2 -8 995 -3 777 -42 |
Решение
Для решение данной задачи я воспользовался следующим алгоритмом. Заводим два целочисленных вектора, булеву переменную, которую мы будем проверять при печати и целочисленную переменную, которая будет являться первым элементом последовательности, а также начальным значением переменной [latex]tester[/latex], с которой будет сравниваться следующий элемент, а после этого его значение мы снова положим в [latex]tester[/latex]. В ходе цикла мы положительные числа кладем в один вектор, а отрицательные в оба. И в зависимости от того чередовались ли знаки или нет (значение переменной [latex]alternate[/latex]), мы печатаем нужный вектор.
Решение принял. Правда предполагался другой алгоритм.
Все элементы читаются в вектор пока выполняется чередование. Если чередование не нарушено, то это и есть результат. Если чередование нарушено, то удаляются из уже прочитанной части все неотрицательные элементы. При дальнейшем чтении только отрицательные записываются в вектор.
В этом алгоритме будет одна важная практическая задача — как эффективно удалить часть элементов вектора? Если хотите, можете попытаться разобраться с этим.
P.S. Как Вы трактуете нулевые элементы? Их нужно просто игнорировать или они нарушают любое чередование?