Задача 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.
Пусть количество пикселей в рисунке K, тогда объем памяти, занимаемой одним рисунком = (K*3)/1024 + 128 Кбайт.
X = 8*(K*3/1024 + 128)+2.5*1024
2. При использовании палитры из 2^16 цветов для хранения цвета 1 пикселя используется 16 бита = 2 байта.
Объем памяти, занимаемой одним рисунком = (K*2)/1024 + 128 Кбайт.
X = 20*(K*2/1024 + 128)
8*(K*3/1024 + 128)+2.5*1024 = 20*(K*2/1024 + 128)
К = 65536 (количество пикселей в рисунке)
X = 20*(K*2/1024 + 128) = 20*(65536*2/1024 + 128) Кбайт =
20*(128 + 128) Кбайт = 5120 Кбайт = 5120/1024 Мбайт = 5 Мбайт
//c циклом for
var s,i:integer;
begin
for i:=100 to 999 do
if i mod 77 = 0 then s:=s+i;
writeln('Сумма трехзначных кратных 77: ',s);
end.
Тестовое решение:
Сумма трехзначных кратных 77: 5929
// с циклом while
var s,i:integer;
begin
i:=100;
while i<=999 do begin
if i mod 77 = 0 then s:=s+i;
i:=i+1;
end;
writeln('Сумма трехзначных кратных 77: ',s);
end.