Hse</code>s.com
Решение задачи "Расписание Алёны" с Codeforces
С пояснением Просмотров: 21
Алёна успешно сдала вступительные экзамены в университет и теперь с нетерпением ожидает начала учебы.
Одно занятие в университете традиционно называется парой, потому что длится два академических часа (академический час равен 45 минутам).
Университет работает таким образом, что каждый день в нём проводится ровно n пар. В зависимости от расписания у конкретной группы, в данный день в какие-то пары в самом деле могут проводиться занятия, а какие-то могут быть свободными (такие пары называются «окнами»).
На официальном сайте университета уже появилось расписание на завтра для группы Алёны. Таким образом, про каждую из n пар она знает, будет в это время занятие или нет.
Дом Алёны находится далеко от университета, поэтому не всегда в случае свободных пар она успевает сходить домой. Алёна успевает сходить домой, только если «окно» состоит из хотя бы двух свободных пар подряд, иначе она ожидает следующего занятия в университете.
Конечно, Алёна не хочет быть сонной во время занятий, поэтому она будет спать как можно дольше и придет только к первому занятию, которое у нее будет. Аналогично, если занятий больше нет, то Алёна сразу идет домой.
Алена очень ценит время, проведённое дома, поэтому она всегда идет домой, когда это возможно, и возвращается в университет только к началу следующего занятия. Помогите Алёне определить, сколько пар она будет находиться в университете. Заметим, что во время некоторых пар Алена может находиться в университете в ожидании предстоящего занятия.
Одно занятие в университете традиционно называется парой, потому что длится два академических часа (академический час равен 45 минутам).
Университет работает таким образом, что каждый день в нём проводится ровно n пар. В зависимости от расписания у конкретной группы, в данный день в какие-то пары в самом деле могут проводиться занятия, а какие-то могут быть свободными (такие пары называются «окнами»).
На официальном сайте университета уже появилось расписание на завтра для группы Алёны. Таким образом, про каждую из n пар она знает, будет в это время занятие или нет.
Дом Алёны находится далеко от университета, поэтому не всегда в случае свободных пар она успевает сходить домой. Алёна успевает сходить домой, только если «окно» состоит из хотя бы двух свободных пар подряд, иначе она ожидает следующего занятия в университете.
Конечно, Алёна не хочет быть сонной во время занятий, поэтому она будет спать как можно дольше и придет только к первому занятию, которое у нее будет. Аналогично, если занятий больше нет, то Алёна сразу идет домой.
Алена очень ценит время, проведённое дома, поэтому она всегда идет домой, когда это возможно, и возвращается в университет только к началу следующего занятия. Помогите Алёне определить, сколько пар она будет находиться в университете. Заметим, что во время некоторых пар Алена может находиться в университете в ожидании предстоящего занятия.
A PHP Error was encountered
Severity: Notice
Message: Undefined index: first_name
Filename: templates/tasksdecision_view.php
Line Number: 133
Backtrace:
File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler
File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view
File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once
Администратор Photo" />
Автор:
A PHP Error was encountered
Severity: Notice
Message: Undefined index: first_name
Filename: templates/tasksdecision_view.php
Line Number: 133
Backtrace:
File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler
File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view
File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once
Пояснение к задаче
В этой задаче сначала нужно было выкинуть все нули на префиксе и суффиксе строки, после чего ответ был равен количеству единиц плюс количество нулей с двух сторон от которых стоят единицы. Асимптотическая сложность решения: O(n).