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

Условие задачи: Карлсон на досуге занимается исследованием свойств чисел. Однажды ему захотелось узнать факториал числа 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

1

3

4

5

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;

if (br = 0) then

begin

snwe:=0;

exit;

end;

if (a[h] = x) then

begin

snwe:=h;

end

else

begin

if (a[h] > x) then

begin

n:=n-br;

end

else

begin

st:=st+br;

end;

snwe:=snwe (a, st, n, x, h);

end;

end;

begin

assign (input, 'c:\input.txt');

assign (output, 'c:\output.txt');

filemode:=2;

reset (input);

rewrite (output);

read (input, n, x);

for i:=1 to n do

begin

read (input, a[i]);

end;

close (input);

write (output, snwe (a, 1, n, x, h));

close (output);

end.

Задача

Input file: input.txt

Output file: output.txt

В файле in.txt даны координаты трех вершин A,B и С на трех строках соответственно. Координаты в файле разделены пробелом.

Необходимо определить существует ли треугольник АВС с указанными координатами вершин. Если существует, то вывести в файл out.txt слово «exist», иначе – «do not exist».

INPUT.TXT	OUTPUT.TXT
1 3 5 7 8 9	exist

Решение

Program triangle;

var

i,xa,xb,xc,ya,yb,yc,xAB,xBC,yAB,yBC: integer;

AB,BC: real;

f1,f2: text;

begin

assign(f1,'input.txt');

assign(f2,'output.txt');

reset(f1);

read(f1,xa,ya);

readln(f1);

read(f1,xb,yb);

readln(f1);

read(f1,xc,yc);

readln(f1);

close(f1);

xAB:=xb-xa;

yAB:=yb-ya;

xBC:=xc-xb;

yBC:=yc-yb;

rewrite(f2);

if xAB/xBC <> yAB/yBC then writeln(f2,'exist')

else writeln(f2,'do not exist');

close(f2);

end.

Тема: Элементы лексического и синтаксического разбора

Заданы две фразы. Определить наибольшую последовательность отличных от пробелов символов, входящую в обе фразы в одном и том же порядке.

Входные данные. В первой строке входного файла INPUT.TXT содержится первая фраза, во второй строке содержится вторая фраза.

Выходные данные. В файл OUTPUT.TXT выводится найденная последовательность символов.

Пример.

INPUT.TXT	OUTPUT.TXT
ПРИШЛА ВЕСНА РАССТАЯЛ СНЕГ	РЛСН

Решение

Program F1;

const k=255;

input='input.txt';

output='output.txt';

var x: array [1..k] of integer;

m,n,j: integer;

s1,s2,s: string;

f:text;

label 1;

{функция, которая на основе очередного сочетания

получает следующее по порядку сочетание}

function posl(m:integer):boolean;

var j,f:integer;

label 10,20;

begin

f:=0;

posl:=true;

for j:=m downto 1 do

if x[j]=n+j-m then f:=j

else

begin

inc(x[j]);

goto 10

end;

10: if f<>0 then if f=1 then

begin

posl:=false;

goto 20

end

else for j:=f to m do x[j]:=x[f-1]+j-f+1;

20:

end;

{процедура вывода результата на экран и записи в файл}

procedure prints(m:integer);

var i:integer;

z:string;

begin

write(m,': ');

for i:=1 to m do

z:=z+s1[x[i]];

writeln(z);

assign(f,output);

rewrite(f);

write(f,z);

close(f);

readln;

end;

{функция spc удаляет из переданной в неё строки пробелы.}

function spc(s:string):string;

var str:string;

i:integer;

begin

str:='';

for i:=1 to length(s) do

if s[i]<>' ' then str:=str+s[i];

spc:=str;

end;

{функция equal проверяет, входит ли очередная последовательность,

составленная из символов одной строки в другую}

function equal(m:integer):boolean;

var i,j:integer;

begin

j:=1;

for i:=1 to length(s2) do

if (s1[x[j]]=s2[i])and(j<=m) then j:=j+1;

if j>m then equal:=true else equal:=false;

end;

{тело программы}

begin

assign(f,input);

reset(f);

readln(f,s1);

read(f,s2);

close(f);

s1:=spc(s1); s2:=spc(s2);

if (length(s2)<length(s1)) then begin s:=s1; s1:=s2; s2:=s end;

n:=length(s1);

for m:=n downto 1 do

begin

for j:=1 to m do x[j]:=j;

repeat

if equal(m) then

begin

prints(m);

goto 1;

end;

until not posl(m);

end;

1:

end.

В этой программе процедура prints печатает найденную последовательность символов и её длину, функция equal проверяет, входит ли очередная последовательность, составленная из символов одной строки в другую, функция spc удаляет из переданной в неё строки пробелы. Работу полученной программы можно значительно ускорить, если добавить в неё часть, в которой перед началом перебора из обеих строк удалялись бы те символы, которые встречаются только в одной из них. (Например, заданные в условии строки после такого преобразования приняли бы вид: РЛАЕСНА и РАСАЛСНЕ).

 

Тема: Эффективные структуры данных.

Условие задачи: В преддверии начала 13-го чемпионата страны по футболу в 1-й лиге организаторы решили провести жеребьевку календаря. Секретарь федерации предоставил списки команд с учетом занятых мест в 12-м чемпионате, но для того, чтобы жеребьевка прошла непредвзято и корректно необходимы списки команд по алфавиту, независимо от их достижений в прошлом году. Составить программу, преобразующую турнирную таблицу 12-го чемпионата, состоящую из N команд, в алфавитный список.

INPUT. TXT	8 Реал Барселона Атлетико Депортиво Сельта Севилья Гранада Валенсия	Количество команд (N) Названия команд
OUTPUT.TXT	Атлетико Барселона Валенсия Гранада Депортиво Реал Севилья Сельта

Решение:

Program olimp1;

var

x: array[1..32] of string;

y: string;

i, j, n: integer;

Fd, Fs: Text;

begin

assign(Fd, ‘D:\input.txt’);

reset(Fd);

assign(Fs, ‘D:\output.txt’);

rewrite(Fs);

readln(Fd, N);

for i:=1 to N do

begin

readln(Fd, x[i]);

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i]>x[j] then

begin

y:=x[i];

x[i]:=x[j];

x[j]:=y;

end;

for i:=1 to n do

writeln (Fs, i:2,’.’+x[i]);

end.

Тема: Эффективные структуры данных.

Условие задачи: В преддверии начала 13-го чемпионата страны по футболу в 1-й лиге организаторы решили провести жеребьевку календаря. Секретарь федерации предоставил списки команд с учетом занятых мест в 12-м чемпионате, но для того, чтобы жеребьевка прошла непредвзято и корректно необходимы списки команд по алфавиту, независимо от их достижений в прошлом году. Составить программу, преобразующую турнирную таблицу 12-го чемпионата, состоящую из N команд, в алфавитный список.

INPUT. TXT	8 Реал Барселона Атлетико Депортиво Сельта Севилья Гранада Валенсия	Количество команд (N) Названия команд
OUTPUT.TXT	Атлетико Барселона Валенсия Гранада Депортиво Реал Севилья Сельта

Решение:

Program olimp1;

var

x: array[1..32] of string;

y: string;

i, j, n: integer;

Fd, Fs: Text;

begin

assign(Fd, ‘D:\input.txt’);

reset(Fd);

assign(Fs, ‘D:\output.txt’);

rewrite(Fs);

readln(Fd, N);

for i:=1 to N do

begin

readln(Fd, x[i]);

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[i]>x[j] then

begin

y:=x[i];

x[i]:=x[j];

x[j]:=y;

end;

for i:=1 to n do

writeln (Fs, i:2,’.’+x[i]);

end.