Решение задачи Расписание Алёны с Codeforces

С пояснением   Просмотров: 32


Алёна успешно сдала вступительные экзамены в университет и теперь с нетерпением ожидает начала учебы.

Одно занятие в университете традиционно называется парой, потому что длится два академических часа (академический час равен 45 минутам).

Университет работает таким образом, что каждый день в нём проводится ровно n пар. В зависимости от расписания у конкретной группы, в данный день в какие-то пары в самом деле могут проводиться занятия, а какие-то могут быть свободными (такие пары называются «окнами»).

На официальном сайте университета уже появилось расписание на завтра для группы Алёны. Таким образом, про каждую из n пар она знает, будет в это время занятие или нет.

Дом Алёны находится далеко от университета, поэтому не всегда в случае свободных пар она успевает сходить домой. Алёна успевает сходить домой, только если «окно» состоит из хотя бы двух свободных пар подряд, иначе она ожидает следующего занятия в университете.

Конечно, Алёна не хочет быть сонной во время занятий, поэтому она будет спать как можно дольше и придет только к первому занятию, которое у нее будет. Аналогично, если занятий больше нет, то Алёна сразу идет домой.

Алена очень ценит время, проведённое дома, поэтому она всегда идет домой, когда это возможно, и возвращается в университет только к началу следующего занятия. Помогите Алёне определить, сколько пар она будет находиться в университете. Заметим, что во время некоторых пар Алена может находиться в университете в ожидании предстоящего занятия.

Код

#include <bits/stdc++.h>
using namespace std;

const int N = 200;
int n, a[N], s;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i], s += a[i];
	for (int i = 1; i + 1 < n; i++)
		if (a[i] == 0 && a[i - 1] == a[i + 1] && a[i - 1] == 1)
			s++;
	cout << s << endl;
	return 0;
}

         

Администратор Photo Автор: Администратор


В этой задаче сначала нужно было выкинуть все нули на префиксе и суффиксе строки, после чего ответ был равен количеству единиц плюс количество нулей с двух сторон от которых стоят единицы. Асимптотическая сложность решения: O(n).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться