Решение задачи Расписание Алёны с Codeforces
С пояснением   Просмотров: 64
Алёна успешно сдала вступительные экзамены в университет и теперь с нетерпением ожидает начала учебы.
Одно занятие в университете традиционно называется парой, потому что длится два академических часа (академический час равен 45 минутам).
Университет работает таким образом, что каждый день в нём проводится ровно n пар. В зависимости от расписания у конкретной группы, в данный день в какие-то пары в самом деле могут проводиться занятия, а какие-то могут быть свободными (такие пары называются «окнами»).
На официальном сайте университета уже появилось расписание на завтра для группы Алёны. Таким образом, про каждую из n пар она знает, будет в это время занятие или нет.
Дом Алёны находится далеко от университета, поэтому не всегда в случае свободных пар она успевает сходить домой. Алёна успевает сходить домой, только если «окно» состоит из хотя бы двух свободных пар подряд, иначе она ожидает следующего занятия в университете.
Конечно, Алёна не хочет быть сонной во время занятий, поэтому она будет спать как можно дольше и придет только к первому занятию, которое у нее будет. Аналогично, если занятий больше нет, то Алёна сразу идет домой.
Алена очень ценит время, проведённое дома, поэтому она всегда идет домой, когда это возможно, и возвращается в университет только к началу следующего занятия. Помогите Алёне определить, сколько пар она будет находиться в университете. Заметим, что во время некоторых пар Алена может находиться в университете в ожидании предстоящего занятия.
Одно занятие в университете традиционно называется парой, потому что длится два академических часа (академический час равен 45 минутам).
Университет работает таким образом, что каждый день в нём проводится ровно n пар. В зависимости от расписания у конкретной группы, в данный день в какие-то пары в самом деле могут проводиться занятия, а какие-то могут быть свободными (такие пары называются «окнами»).
На официальном сайте университета уже появилось расписание на завтра для группы Алёны. Таким образом, про каждую из n пар она знает, будет в это время занятие или нет.
Дом Алёны находится далеко от университета, поэтому не всегда в случае свободных пар она успевает сходить домой. Алёна успевает сходить домой, только если «окно» состоит из хотя бы двух свободных пар подряд, иначе она ожидает следующего занятия в университете.
Конечно, Алёна не хочет быть сонной во время занятий, поэтому она будет спать как можно дольше и придет только к первому занятию, которое у нее будет. Аналогично, если занятий больше нет, то Алёна сразу идет домой.
Алена очень ценит время, проведённое дома, поэтому она всегда идет домой, когда это возможно, и возвращается в университет только к началу следующего занятия. Помогите Алёне определить, сколько пар она будет находиться в университете. Заметим, что во время некоторых пар Алена может находиться в университете в ожидании предстоящего занятия.
Пояснение к задаче
В этой задаче сначала нужно было выкинуть все нули на префиксе и суффиксе строки, после чего ответ был равен количеству единиц плюс количество нулей с двух сторон от которых стоят единицы. Асимптотическая сложность решения: O(n).