Урок физкультуры
На уроке физкультуры первоклассники построились в шеренгу. После объяснения правил выполнения строевых команд последовала команда «налево». При ее исполнении некоторые школьники повернулись налево, а некоторые— направо, перепутав направление поворота. Ученики, которые оказались лицом к лицу со своим соседом, подумали, что совершили ошибку (хотя ошибку совершил кто-то один из школьников пары). Чтобы её исправить, каждый из них быстро повернулся на 180∘. Если описанная ситуация затем опять повторялась, то есть какие-то рядом стоящие школьники оказывались лицом друг к другу, то они снова поворачивались на 180∘. Эта процедура продолжалась, пока в шеренге оставалась хотя бы одна пара стоящих лицом друг к другу учащихся.
Вам нужно составить программу, которая по расположению школьников сразу после исполнения команды «налево» вычисляет количество пар учащихся, совершивших впоследствии развороты на 180∘ в соответствии с вышеописанной процедурой.
Формат входных данных
Входные данные состоят из двух строк. В первой строке записано число N(2≤N≤10^5)— количество школьников в шеренге. Во второй строке содержится последовательность из N символов, каждый из которых может быть либо символом ’<’, либо символом ’>’ (символ ’<’ означает ученика по команде повернувшегося налево, символ ’>’—ученика, повернувшегося направо).
Формат выходных данных
Выходные данные должны содержать либо одно число—количество развернувшихся пар, либо число −1, если процесс бесконечен.
1 Ответ
#include <vector>
#include <iostream>
using namespace std;
int and_all(const vector<int>& box, const pair<size_t, size_t>& interval) {
auto j = interval.first;
while (j < interval.second) {
if (box[j - 1] & box[j]) ++j;
else break;
}
return j == interval.second;
}
int main() {
size_t n;
cin >> n;
vector<int> box(n);
size_t q;
cin >> q;
vector<pair<size_t, size_t>> fox(q);
for (auto& x : box) cin >> x;
for (auto& [a, b] : fox) cin >> a >> b;
vector<int> res(q);
size_t i = 0;
for (const auto& interval : fox) res[i++] = and_all(box, interval);
for (auto x : res) cout << x << '\n';
}