Тема: Работа с большими числами

Условие задачи: Карлсон на досуге занимается исследованием свойств чисел. Однажды ему захотелось узнать факториал числа 100. Напишите программу, помогающую Карлсону решить эту проблему для любого N (0<N<103).

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

Исходный файл содержит одно число N.

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

В выходной файл вывести факториал заданного числа

Пример:

INPUT.TXT OUTPUT.TXT

50 30414093201713378043612608166064768844377641568960512000000000000

program Factorial;

type tlargenumber=record

number:array[1..3000]of byte;

power:word;

end;

var fact:tlargenumber;

n:word;

i:word;

f:text;

procedure product(n:word);

var temp:tlargenumber;

i,p:word;

procedure add(n:word;power:word);

var t,s,d,e:byte;

first:word;

begin

t:=n div 1000;

s:=(n mod 1000)div 100;

d:=(n mod 100)div 10;

e:=n mod 10;

first:=1+power;

inc(temp.number[first],e);

inc(temp.number[first+1],d+(temp.number[first]div 10));

temp.number[first]:=temp.number[first]mod 10;

inc(temp.number[first+2],s+(temp.number[first+1]div 10));

temp.number[first+1]:=temp.number[first+1]mod 10;

inc(temp.number[first+3],t+(temp.number[first+2]div 10));

temp.number[first+2]:=temp.number[first+2]mod 10;

inc(temp.number[first+4],temp.number[first+3]div 10);

temp.number[first+3]:=temp.number[first+3]mod 10;

end;

begin

for i:=1 to 3000 do temp.number[i]:=0;

temp.power:=0;

p:=fact.power;

for i:=0 to p do

add(fact.number[i+1]*n,i);

if temp.number[p+4]<>0 then temp.power:=p+4

else

if temp.number[p+3]<>0 then temp.power:=p+3

else

if temp.number[p+2]<>0 then temp.power:=p+2

else

if temp.number[p+1]<>0 then temp.power:=p+1

else

temp.power:=p;

fact:=temp;

end;

begin

assign(f,'in.txt');

reset(f);

read(f,n);

close(f);

fact.number[1]:=1;

fact.power:=1;

for i:=2 to n do

begin

product(i);

end;

assign(f,'out.txt');

rewrite(f);

for i:=fact.power downto 1 do write(f,fact.number[i]);

close(f);

end.

Тема: Сортировка и выбор

Условие задачи: Для игры в квидич используются мячи - снитчи. Проблема заключается в том, что они разного размера. Для проведения матча требуется выбрать снитч нужного веса. Перед началом матча все снитчи выстраиваются в ряд в порядке неубывания весов и Гарри Поттер должен как можно быстрее найти снитч с весом ровно Х кг или сообщить судье об отсутствии нужного мяча.

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

В первой строке входного файла записаны через пробел два целых числа N и X. В следующих N строках записаны веса мячей в порядке неубывания (по одному числу в строке). Веса – целые числа, не превосходящие 100, 0<N£50000.

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

В выходной файл вывести номер снитча, имеющего вес X или число 0, если такого снитча нет.

Лимит времени: 1 секунда на тест.

Пример:

INPUT. TXT OUTPUT.TXT

5 3

9 2

Указания к решению. Очевидное решение состоит в просмотре всего ряда снитчей сначала до конца, что требует времени, пропорционального числу снитчей. Однако этот алгоритм не использует того факта, что веса снитчей уже отсортированы. Наилучший метод поиска состоит в том, чтобы проверить, стоит ли нужный мяч в середине ряда. Если да, то ответ получен. Если вес x меньше веса среднего снитча, то мы можем применить тот же метод поиска к отсортированному подряду слева от среднего элемента; аналогично, если x больше веса среднего мяча, то в дальнейшем мы будем рассматривать правую половину ряда.

Код возможного решения:

program tt;

const bl = 32;

type mass = array [1..bl] of integer;

var i, n, h, x: integer;

a: mass;

input, output: text;

function snwe (a: mass; st, n, x, h: integer): integer;

var i, br: integer;

begin

br:=round ((n-st)/2);

h:=br+st;