Тесты для проверки к задаче №2:

№ варианта	Исходные данные	Выходные данные
1	12	10101
2	2101	1010001000001000
3	29	1010000
4	935	10101000000100
5	5	1000
6	687	10000101000001
7	17	100101
8	354	101001010100
9	10	10010
10	512	1001010010101
11	42	10010000
12	1024	100000010000100
13	11	10100
14	2112	1001001010100010
15	13	100000
16	2013	1001000010001000
17	20	101010
18	1096	100001000101010
19	44	10010010
20	1825	1000010101010000

Код программы (Pascal)

program bif;

uses crt;

var a,b,c,j,n,i:longint;

f:array [1..100] of longint; {massiv dlia riada fibonacchi}

ind:array [1..100] of integer; {massiv dlia coda fibonacchi}

begin

clrscr; write ('chislo'); readln(n);

{vyraschivaem ryad do chisla n }

f[1]:=1; f[2]:=2 ;

i:=2;

while f[i]<=n do

begin

i:=i+1;

f[i]:=f[i-1]+f[i-2];

end;

{obnulyaem massiv coda}

for j:=1 to i do ind[j]:=0 ;

{stroim cod. Dlia etogo idem po ryady fibonacchi vniz i nahodim naibol'shii

element riada men'shii ili ravnii chislu n. V massiv index stavim edinicu,

i vichitaem iz chisla naidennyi element ryada. I tak do teh por, poka chislo ne

obnulim. CChtoby n ne portit' my rabotaem

c ego copyey a }

b:=i; a:=n;

while a>0 do

begin

while a< f[b] do b:=b-1; ind[b]:=1; a:=a-f[b];

end;

write ('cod Fibonacchi=');

for j:=i-1 downto 1 do

write (ind[j]);

end.

Задача №3 «Криптографические ключи» (max 100 баллов)

(Автор: доцент кафедры информатики и защиты информации ВлГУ, кандидат физико-математических наук Александров Алексей Викторович)

Недавно одна компания “X” разработала принципиально новый алгоритм шифрования данных, который практически невозможно взломать, но и одновременно абсолютно не ресурсоемкий. Все шифрование строится на симметричном K-ключе, то есть на числе, в двоичной записи которого ровно K единиц. Все принципиальное отличие от предыдущих алгоритмов заключалось в том, что ключ не был одним и тем же на все время соединения, а менялся после некоторых определенных интервалов времени на другой K-ключ. Также одной из особенностей разработанного алгоритма была необходимость того, чтобы каждый следующее число, соответствующее K-ключу, было больше предыдущего. Более того, специалисты компании установили, что для увеличения помехоустойчивости разница между следующим K-ключом и предыдущим K-ключом должна быть минимальна. Под разницей K-ключей понимается абсолютная разница соответствующих им чисел.

Вы работаете в этой компании, и Вам предстоит разработать алгоритм получения из исходного K-ключа следующего K-ключа в соответствии со всеми описанными выше требованиями.

Формат входных данных

В первой и единственной строке входного файла находится одно натуральное число N (1 ≤ N ≤ 10¹⁸) – соответствующий K-ключ.

Формат выходных данных

В первой и единственной строке выходного файла должно находится одно натуральное число – следующий K-ключ за соответствующим K-ключом N.

Пример входного и выходного файлов

Пример входных данных	Пример выходных данных
2	4
22	25
1536	2049

Критерии оценивания задачи: каждому участнику олимпиады выдается два теста с одним небольшим (не больше тысячи) и одним большим числом. Тест с небольшим числом оценивается в 40 баллов, с большим числом оценивается в 60 баллов. Максимальное количество баллов 100.