Ctrl K

Единиц больше квадрата нулей

Средняя
Дана строка bits из символов 0 и 1. Назовём подстроку *тяжёлой*, если число единиц в ней не меньше, чем **квадрат** числа нулей в ней. Например, 0111 тяжёлая (3 ≥ 1²), а 00111 — нет (3 < 2²). Верните количество непустых тяжёлых подстрок bits. Подстроки, стоящие в разных местах, считаются разными, даже если совпадают по содержимому.
Пример 1
bits="1101" → 9

Из 10 подстрок не подходит только одиночный 0 (нулей 1, единиц 0). Например, 101 годится: единиц 2 ≥ 1².

Пример 2
bits="0000" → 0

В каждой подстроке есть нуль и нет единиц, поэтому ответ 0.

Пример 3
bits="1001111" → 19
Ограничения
  • 1 ≤ len(bits) ≤ 4 · 10⁴
  • bits состоит только из символов 0 и 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиНечётное против чётного в окне СложнаяСамый длинный фрагмент без повторов СредняяОтрезок из двух букв СредняяПовторяющиеся участки гена СредняяОкно с ограниченным набором букв Средняя
загружаем Python…
Вход
bits="1101"
Ожидается
9

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 168 тестов на сервере, включая скрытые.