Строку фибоначчи f(k) для натуральных чисел k определим так: f(1) = 'a', f(2) = 'b', f(k) = f(k - 1) + f(k - 2) при k > 2, где "+" означает конкатенацию строк. требуется найти количество вхождений строки s, состоящей из символов a и b, в строку фибоначчи f(n).
ограничения: длина s от 1 до 25, 1 < = n < = 45.
примечание. длина f(45) равна 1 134 903 170.
входные данные
в первой строке содержится число n, во второй - строка s.
выходные данные
выводится одно число - количество вхождений строки s в строку фибоначчи f(n).
i, x: integer;
begin
writeln('введите элементы массива A: ');
for i := 1 to 25 do begin
read(A[i]);
if A[i] mod 3 = 0 then
begin
x := x + 1;
B[x] := A[i];
end;
end;
write('элементы массива A, кратные трём: ');
for i := 1 to x do begin
write(B[i], ' ');
end;
end.
2) var A, B, C: array[1..10000] of integer;
i, n, x: integer;
begin
writeln('введите размеры обоих массивов: ');
read(n);
write('введите элементы массива A: ');
for i := 1 to n do begin
x := x + 1;
read(A[i]);
end;
write('введите элементы массива B: ');
for i := 1 to n do begin
read(B[i]);
end;
write('элементы массива C: ');
for i := 1 to x do begin
C[i] := A[i];
write(C[i], ' ');
C[i] := B[i];
write(C[i], ' ');
end;
end.
Воспользуемся расширенной записью числа
87=an²+bn+2 → an²+bn-85=0
Известно, что если многочлен с целочисленными коэффициентами имеет хотя бы один вещественный корень, то он находится среди делителей свободного члена. Нас интересуют только натуральные делители, большие 2, поскольку n - основание системы счисления и в этой системе имеется цифра 2.
85 = 5 × 17. Число 17 не подходит, потому что 17>10 и двухзначное десятичное число в системе счисления с основанием, большим 10, не может иметь в записи больше двух знаков. Следовательно, n=5.
Для проверки переводим 87 в систему счисления по основанию 5.
87 / 5 = 17, остаток 2
17 / 5 = 3, остаток 2
3 / 5 = 0, остаток 3.
Выписываем остатки в обратном порядке: 322
87₁₀ = 322₅ - в числе три разряда и оно оканчивается двойкой.
ответ: N=5