Задача D. Найди две единицы Ограничение по времени: 0.5 секунд
Ограничение по памяти: 256 мегабайт
При записи чисел в фибоначчиевой системе счисления в качестве цифр используются только 0
и 1. Будем использовать ноль в записи, если очередное число из последовательности Фибоначчи
(1, 2, 3, 5, 8, 13, 21, . . .) не используется, и единицу — для тех что используются. Тогда, например,
17 = 13 + 3 + 1 = 100101f ib. Для однозначности представления в такой записи не должно быть двух
единиц подряд, иначе, например, 17 = 8 + 5 + 3 + 1 = 11101. Такие числа подлежат нормализации.
Вам требуется в строке, которая является каким то представлением числа в фибоначчиевой
системе, для каждой позиции, кроме последней, найти ближайшее к ней справа место, на котором
стоят как минимум две единицы подряд, и выдать расстояние до него или −1, если, начиная с
текущей позиции, правее двух единиц подряд нет. Например, для строки 10111001101 программа
должна выдать: «2 1 0 0 3 2 1 0 -1 -1».
Причем эффективная по времени программа должна находить ответ с одного цикла,
без использования стандартных функций и методов, работающих за длину строки.
Формат входных данных
На вход программе подается одна строка, состоящая из символов 0 или 1, начинающаяся с 1.
Длина строки N не превосходит 100 000 символов.
Формат выходных данных
Выведите в строку через пробел или в столбец N − 1 число — ответ на задачу для каждой из
первых N − 1 позиций строки.
Примеры
стандартный ввод стандартный вывод
10111001101 2 1 0 0 3 2 1 0 -1 -1
11111 0 0 0 0
Замечание
Как минимум в 40% тестов длина строки не превосходит 1000.
1
Объяснение:
Программа выдаст "Yes" , если любое из условий сработает. Либо s будет больше 10, либо t больше A.
Мы сразу определяем сколько раз сработает первое условие: (10,2) , (11,12).
Получается нам осталось ещё, чтобы второе условие сработало 6 раз.
Мы видим, что если в переменную А записать число 1, то второе условие сработает на числах : (1,2) , (1,12) (-11,12) (-12,11) (10,10) (10,5)
В сумме с первым условием (s>10) получается, что программа выдаст "Yes" как раз 8 раз, не выполнится только ввод чисел (-11,-12)
1) прямоугольник, первый вариант:
import turtle
b=40
l=b+20
turtle.shape('turtle')
turtle.goto(l,0)
turtle.goto(l,b)
turtle.goto(0,b)
turtle.goto(0,0)
turtle.penup()
turtle.goto(100,0)
1) прямоугольник, второй вариант:
import turtle
b=40
l=b+20
turtle.shape('turtle')
turtle.forward(l)
turtle.left(90)
turtle.forward(b)
turtle.left(90)
turtle.forward(l)
turtle.left(90)
turtle.forward(b)
turtle.penup()
turtle.forward(b)
2) птичка
import turtle
turtle.shape('turtle')
turtle.goto(50,-20)
turtle.goto(0,30)
turtle.goto(-10,30)
turtle.goto(-15,25)
turtle.goto(-10,20)
turtle.goto(-10,0)
turtle.goto(0,-10)
turtle.goto(20,-15)
turtle.goto(35,-15)
turtle.goto(50,-20)
turtle.penup()
turtle.goto(100,0)