Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
mybook11.05.12.doc
Скачиваний:
15
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

Формат входного файла

Файл содержит целое число S (1 <= S <= 81).

Формат выходного файла

Файл должен содержать единственное число – значение миллиардной Функции Камиля в точке S.

Пример

Input.txt

Output.txt

1

10

var a,b:array[0..9,-100..100]of longint;

f:array[0..10]of longint;

c:array[0..9,0..9]of longint;

s,s1:longint;

ans:longint;

procedure init;

begin

read(s);

fillchar(a,sizeof(a),0);

if s=1 then ans:=10 else ans:=0;

end;

procedure solve;

var i,j,k,q,w:longint;

begin

if ans<>0 then exit;

f[0]:=1;

for i:=1 to 9 do

f[i]:=f[i-1]*i; вычисляем факториал

for i:=1 to 9 do

for j:=1 to i do

c[i,j]:=f[i] div(f[j]*f[i-j]); вычисляем c(n,k)

for i:=0 to 9 do c[i,0]:=1;

for q:=1 to 9 do begin

for i:=0 to 9 do a[i,0]:=1;

fillchar(b,sizeof(b),0);

for i:=1 to 9 do

for j:=1 to s do

for k:=1 to i do begin

if a[i-k,j-q*k]<>0 then

if j-q*k=0 then b[i,j]:=b[i,j]+c[i-1,k-1]*a[i-k,j-q*k]

else begin

b[i,j]:=b[i,j]+c[i,k]*a[i-k,j-q*k];

for w:=i-k-1 downto 1 do

if a[w,j-q*k]<>0 then begin

b[i,j]:=b[i,j]+c[i-1,k-1]*a[w,j-q*k]

end;

end;

end;

for i:=1 to 9 do

for j:=1 to s do

a[i,j]:=a[i,j]+b[i,j];

end;

for i:=1 to 9 do

ans:=ans+a[i,s];

end;

procedure out;

begin

write(ans);

end;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

init;

solve;

out;

close(input); close(output);

end.

Задачи Задача 56 Уравнение

Те кто решает олимпиадные задачи знает, что числа Фибоначчи появляются в решении совершенно неожиданно, после долгих поисков, как подарок судьбы. В нашей задаче они появятся в самом начале. Найдите количество целочисленных решений (x, y) уравнения Fnx+Fmy=c, где Fn и Fm n-е и соответственно m-е числа Фибоначчи, а с - целое число, для которых точки с координатами (x, y) принадлежат прямоугольнику, стороны которого параллельны осям координат и левая верхняя вершина имеет координаты (x1, y1), а правая нижняя (x2, y2). Точка считается принадлежащей прямоугольнику, если она находится на его границе или внутри прямоугольника.

Справка для тех, кто не знаком с числами Фибоначчи:

N

0

1

2

3

4

5

6

7

Fn

0

1

1

2

3

5

8

13

Входные данные:

В первой строке два натуральных числа n и m, разделенных пробелом (1n,m17).

Во второй строке целое число с -106 c 106.

В третьей строке четыре целых числа, разделенных пробелом x1, y1, x2, y2.

( -106 x1, y1, x2, y2 106).

Выходные данные:

одно целое число- количество искомых точек.

Пример:

Input.txt

Output.txt

1 2

2

0 4 7 1

3

Если просто пробежать от x1 до x2, перебирая все целые числа, то мы не успеем по времени. Идея решения в следующем. Движемся от x1 вправо перебирая последовательно целые числа и проверяя их на принадлежность заданной прямой. Для этого мы вычисляем y и проверяем является ли он целым числом. Запоминаем найденное значение x3. Движемся дальше пока не найдем еще одно такое значение x4. на всех остальных отрезках длиной x4-x3 количество нужных точек будет таким же. Теперь мы шагаем с длиной шага равной x4-x3, то есть гораздо быстрее.

x1 x3 x4 xi x2

Для этого случая, добежав до точки xi, остается пройти отрезок от xi до x2.

Возможных случаев пересечения прямо и прямоугольника может быть несколько. Остается только нарисовать все случаи, понять разницу и написать программу.

задачи

Задача 57 Последовательность Фибоначчи

Дана последовательность натуральных чисел. Найти минимальное из тех чисел последовательности, номера которых являются числами Фибоначчи. (Числа Фибоначчи F1=1, F2=1, при N>2 FN =FN-1+FN-2

Входной файл Input.txt представляет собой последовательность целых чисел из диапазона -2147483648 .. 2147483647. Длина последовательности - не менее 1 и не превышает 10000 чисел. Любые два числа разделены одним или несколькими пробелами и(или) одним или несколькими символами перевода строки.

Выходной файл Output.txt должен содержать одно число - минимальное из тех чисел последовательности, номера которых являются числами Фибоначчи.

Пример:

Input.txt

Output.txt

6 4 10 2 13 11 30 8 9 -1

4

Program Posled_F;

Var

PrevF1, PrevF2, nextF, curnum : Word;

minval, curval : longint;

Begin

assign (input,'input.txt'); reset (input);

assign (output, 'output.txt'); rewrite (output);

read (MinVal);

prevF1 := 1; prevF2 := 1;

nextF := 2;

curnum := 2; текущий номер числа последовательности

While Not SeekEof do

Begin

Read (curval); считываем очередное число последовательности

If curnum = nextf then

Begin

prevF1 := prevF2;

prevF2 := nextF;

nextF := PrevF1 + PrevF2;

If curval < minval then minval := curval;

End;

Inc (curnum);

End;

Write (minval);

End.

задачи

Задача 58 Теорема Цеккендорфа

Чудаков на свете много. Один чудак- миллионер купил остров и решил выпустить свои деньги под названием фантики. Когда-то он занимался теорией чисел и очень любил теорему Цеккендорфа ( каждое натуральное число имеет единственное представление в виде суммы чисел Фибоначчи, в которой два соседних числа Фибоначчи никогда не используются.), поэтому решил выпустить деньги номиналом совпадающими с числами Фибоначчи и приказал кассиру платить зарплату своим сотрудникам этими купюрами, причем так, чтобы выполнялось условие теоремы Цекендорфа и купюра каждого номинала встречалась в выплаченной сумме один раз. У кассира возникла проблема: как выплатить сумму в N рублей. Помогите кассиру.

Дано натуральное число N (1N1018 ). Представить его в виде суммы N=Fk1+Fk2+…Fkr , где Fi число Фибоначчи и в этой сумме нет двух рядом стоящих чисел из последовательности чисел Фибоначчи и одинаковых чисел из этой последовательности.

Справка для тех, кто не знаком с числами Фибоначчи:

N

0

1

2

3

4

5

6

7

Fn

0

1

1

2

3

5

8

13

Входные данные: одно натуральное число N – размер зарплаты.

Выходные данные: Несколько чисел Фибоначчи, дающие в сумме число N. Все числа разделены пробелом и выписаны в порядке возрастания.

Пример:

Input.txt

Output.txt

2

2

Алгоритм решения следующий. 90 чисел Фибоначчи забиваем в массив констант. Все они умещаются в тип int64. Ищем в этом массиве наибольшее число Фибоначчи меньшее данного и запоминаем его. Вычетаем из данного числа найденное и получаем туже задачу, но с меньшим числом. И делаем так до тех пор пока само число не станет числом Фибоначчи. При получении следующего числа надо проверять не является ли оно соседним в последовательности Фибоначчи с найденным на предыдущем шаге.

program cekkendor2;

{$APPTYPE CONSOLE}

{$O-}

uses

SysUtils;

const f:array[1..90]of int64=(1,1,2,3,5,8,13,21,

34,55,89,144,233,377,610,987,

1597,2584,4181,6765,10946,17711,28657,46368,

75025,121393,196418,317811,514229,832040,1346269,2178309,…

3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,

165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,

1779979416004714189,2880067194370816120);

var

i,j,m,k:int64;

a:array[1..30] of int64;

s,n:int64;

t,r:integer;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

m:=1;

r:=0;

repeat

i:=90;

while (f[i]>n)and(i>1) do dec(i); ищем нужное число Фибоначчи

if f[i]=n если само число стало числом Фибоначчи

then begin inc(r);a[r]:=f[i]; break;end запоминаем его и выходим из цикла

else

begin inc(r);a[r]:=f[i]; n:= n-f[i]; end; иначе уменьшаем данное число

until (f[i]<n)or(i=1);

for t:=r downto 1 do выводим результат

write(a[t],' ');

close(output);

end.

задачи

Задача 59 Номера страниц нет решения

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]