Задача 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.
b,c: string;
d,x,y: real;
i,j: integer;
begin
b:='ABCD'; c:='xy';
writeln('трапеция ABCD');
for i:=1 to 4 do
begin
writeln('координаты точки ',b[i],': ');
for j:=1 to 2 do
begin
write(' ',c[j],i,' = ');
readln(a[j,i]);
end;
end;
x:=(a[1,3]-a[1,2]+a[1,4]-a[1,1])/2;
y:=(a[2,3]-a[2,2]+a[2,4]-a[2,1])/2;
d:=sqrt(x*x+y*y);
writeln('длина средней линии: ',d:5:2);
end.
ввод - вывод
трапеция ABCD
координаты точки A:
x1 = 3
y1 = 2
координаты точки B:
x2 = 5
y2 = 5
координаты точки C:
x3 = 9
y3 = 5
координаты точки D:
x4 = 10
y4 = 2
длина средней линии: 5.50
1) Число 376 четное и трехзначное.
А = "Число 376 четное"
В = "Число 376 трехзначное"
А и В
2) Неверно, что Солнце движется вокруг Земли.
А = "Солнце движется вокруг Земли"
Не А
3) Земля имеет форму шара.
А = "Земля имеет форму шара"
А
4) На уроке математики старшеклассники отвечали на вопросы учителя и писали самостоятельную работу.
А = "На уроке математики старшеклассники отвечали на вопросы учителя"
В = "На уроке математики старшеклассники писали самостоятельную работу"
А и В
5) Если сумма цифр числа делится на 3, то число делится на 3.
А = "Сумма цифр числа делится на 3"
В = "Число делится на 3"
А стрелка к В
6) Число делится на 3 тогда и только тогда, когда сумма цифр числа делится на 3
А = "Число делится на 3 "
В = "Сумма цифр числа делится на 3"
А стрелка в обе стороны В