double arrow

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



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

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

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

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

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

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

Пример:

INPUT. TXT OUTPUT.TXT
5 3

Указания к решению. Очевидное решение состоит в просмотре всего ряда снитчей сначала до конца, что требует времени, пропорционального числу снитчей. Однако этот алгоритм не использует того факта, что веса снитчей уже отсортированы. Наилучший метод поиска состоит в том, чтобы проверить, стоит ли нужный мяч в середине ряда. Если да, то ответ получен. Если вес 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.TXT содержится первая фраза, во второй строке содержится вторая фраза.

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



Пример.

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

Решение

Program F1;

constk=255;

input='input.txt';

output='output.txt';

 

varx: array[1..k] ofinteger;

m,n,j: integer;

s1,s2,s: string;

f:text;

label1;

 

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

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

functionposl(m:integer):boolean;

varj,f:integer;

label10,20;

Begin

f:=0;

posl:=true;

forj:=m downto1 do

ifx[j]=n+j-m thenf:=j

Else

Begin

inc(x[j]);

goto10

end;

10: iff<>0 then iff=1 then

Begin

posl:=false;

goto20

End

else forj:=f tom dox[j]:=x[f-1]+j-f+1;

20:

end;

 

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

procedureprints(m:integer);

vari:integer;

z:string;

Begin

write(m,': ');

fori:=1 tom do

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

writeln(z);

 

assign(f,output);

rewrite(f);

write(f,z);

close(f);

readln;

 

end;

 

 

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

functionspc(s:string):string;

varstr:string;

 

i:integer;

Begin

str:='';

fori:=1 tolength(s) do

ifs[i]<>' ' thenstr:=str+s[i];

spc:=str;

end;

 

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

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

functionequal(m:integer):boolean;

vari,j:integer;

Begin

j:=1;

fori:=1 tolength(s2) do

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

ifj>m thenequal:=true elseequal:=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 begins:=s1; s1:=s2; s2:=s end;

n:=length(s1);

form:=n downto1 do

Begin

forj:=1 tom dox[j]:=j;

Repeat

ifequal(m) then

Begin

prints(m);

goto1;

end;

until notposl(m);

end;

1:

 

end.

 

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

 

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

 

Условие задачи: В арифметическом выражении разрешается использовать только число 1, действия сложения и умножения и скобки. Какое минимальное количество единиц необходимо использовать, чтобы получить заданное натуральное число N (1≤ N ≤ 5000)?

 

INPUT. TXT Значение N
OUTPUT.TXT Минимальное количество единиц

Комментарии: Для решения данной задачи применяем методы «динамических структур», т.е. для того, чтобы найти ответ для N, сначала необходимо найти наименьшее количество единиц для значений 1..N-1. Рассмотрим соответствующие выражения для нескольких начальных значений N:

Значение N Наименьшее количество 1 Арифметическое выражение
1+1
1+1+1
(1+1)*(1+1)
1+ (1+1)*(1+1)
(1+1)*(1+1+1)
1+(1+1)*(1+1+1)

 

Динамическая структура строится следующим образом:

для N=1 количество единиц будет x[1]=1;

каждое следующее x[N] будет наименьшим из двух величин:

a=x[N-1]+1;

b=min(x[i] + x[N div i]).

Самого арифметического выражения программа не выдает, только минимальное количество единиц.

 

Решение:

Program olimp2;

сonst

_N=5000;

var

N: integer;

x: array[1.._N] of byte;

fD, fs: Text;

procedure init;

begin

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

reset(fD);

readln(fD, N);

close(fD);

end;

procedure Run;

var i, a, b, m: word;

begin

Fillchar(x, Sizeof(x), 0);

x[1]:=1;

for M:=2 to N do

begin

a:=N;

for i:=1 to M div 2 do

if x[i] +x[M-i]< a then a:=x[i]+x[M-i];

b:=N;

for i:=2 to M div 2 do

if (M mod i=0) and (x[i]+x[M div i]<b) then b:=x[i]+x[M div i];

if a<b then x[M]:=a else x[M]:=b;

end;

end;

procedure Done;

begin

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

rewrite(fs);

write(fs, x[N]);

close(fs);

end;

begin

init;

run;

done

end.

 

 

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

 

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

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

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

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

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

Пример:

INPUT.TXT OUTPUT.TXT

 

programFactorial;

typetlargenumber=record

number:array[1..3000]ofbyte;

power:word;

end;

varfact:tlargenumber;

n:word;

i:word;

f:text;

procedureproduct(n:word);

vartemp:tlargenumber;

i,p:word;

procedureadd(n:word;power:word);

vart,s,d,e:byte;

first:word;

Begin

t:=n div1000;

s:=(n mod1000)div100;

d:=(n mod100)div10;

e:=n mod10;

first:=1+power;

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

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

temp.number[first]:=temp.number[first]mod10;

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

temp.number[first+1]:=temp.number[first+1]mod10;

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

temp.number[first+2]:=temp.number[first+2]mod10;

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

temp.number[first+3]:=temp.number[first+3]mod10;

end;

Begin

fori:=1 to3000 dotemp.number[i]:=0;

temp.power:=0;

p:=fact.power;

fori:=0 top do

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

iftemp.number[p+4]<>0 thentemp.power:=p+4

Else

iftemp.number[p+3]<>0 thentemp.power:=p+3

Else

iftemp.number[p+2]<>0 thentemp.power:=p+2

Else

iftemp.number[p+1]<>0 thentemp.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;

fori:=2 ton do

Begin

product(i);

 

end;

assign(f,'out.txt');

rewrite(f);

fori:=fact.power downto1 dowrite(f,fact.number[i]);

close(f);

end.

Задача «Треугольник»



Сейчас читают про: