Даулеткулов А.Б. Олимпиады по информатике: Учебно-методическое пособие
Подождите немного. Документ загружается.
111
if i=Chisla[j] then Flag:=true;
if Flag=False then writeln(f,i);
end;
close(f);
end;
Begin
init;
work;
exi;
end.
program z6;
var i,n,k:longint;
f: text;
procedure init;
begin
write(“ N -”);
readln(n);
end;
Procedure work;
begin
assign(f,’posled.out’);
rewrite(f);
K:=0;
for i:=1 to n do
begin
if (i mod 2)=1 then
begin
inc(k);
write(f,k,’ “);
end
else
write(f,n-k+1,’ “);
end;
close(f);
end;
Procedure exi;
begin
end;
Begin
init;
work;
exi;
end.
Program z7;
112
Var
F : Text;
A : Array [0..13000] Of Longint;
Num,E,i,j,n,max,m : Integer;
Begin
Assign(f,’pOS.iN’);
Reset(F);
FillChar(A,siZeoF(A),0);
While Not Eof(F) Do Begin
ReadLn(F,Num);If Num>m Then M:=Num;
Inc(A[Num]);If A[Num]>Max Then Max:=A[Num];
End;
Close(F);
Assign(F,’pos.out’);
ReWrite(F);
For i:=1 to M Do If A[i]=Max Then WriteLn(F,i);
Close(F);
End.
Program Z8;
Var
F : text;
i,j,N,M : Byte;
Cnt : Integer;
A : Array [0..202] Of String;
Begin
Assign(F,’kvadraty.in’);
Reset(F);i:=0;
While Not Eof(F) Do Begin
Inc(i);
ReadLn(F,A[i]);M:=Length(A[i]);
End;
Close(F);N:=i;i:=0;
While (i<=M) Do Begin Inc(i);A[0]:=A[0]+’0';End;
For i:=0 to N do A[i]:=’0'+A[i];
Cnt:=0;
For i:=1 to N do
For j:=2 to M+1 do
If (A[i,j]=’1')and(A[i-1,j]=’0')and(A[i,j-1]=’0') Then
Inc(Cnt);
Assign(F,’kvadraty.Out’);
ReWrite(F);
WriteLn(F,Cnt);
Close(F);
End.
Program z9;
var a,b,c:real;
113
rez:string[3];
procedure init;
begin
write(“input a -”);
readln(a);
write(“input b -”);
readln(b);
write(“input c -”);
readln(c);
end;
Procedure work;
begin
Rez:=’no’;
if ((a+b)>c) and ((a+c)>b) and ((c+b)>a) then Rez:=’yes’;
end;
Procedure exi;
begin
writeln(rez);
end;
Begin
init;
work;
exi;
end.
Program z10;
var m,k,MaxCol,Max,i,Col:longint;
f :text;
procedure init;
begin
assign(f,’pos.in’);
eset(f);
read(f,m);
Max:=m;
MaxCol:=1;
Col:=1;
while not Eof(f) do
begin
read(f,k);
if m=k then
begin
inc(Col);
if Col>MaxCol then
begin
MaxCol:=Col;
Max:=k;
114
end;
end
else
Begin
Col:=1;
M:=k;
end;
end;
close(f);
end;
Procedure exi;
begin
assign(f,’pos.out’);
rewrite(f);
write(f,MaxCol,’ “,Max);
close(f);
end;
Begin
init;
exi;
end.
program z11;
var
j,i,k,m,n :longint;
begin
readln(n,m);
readln(k);
i:=((k-1) div m)+1;
j:=k-(i-1)*m;
if i>1 then write(k-m,’ “);
if j<M then write(k+1,’ “);
if i<N then write(k+m,’ “);
if j>1 then write(k-1,’ “);
end.
Var
F : text;
i,j,N,M,K,L : Byte;
Max : Integer;
A : Array [0..201] Of String;
Begin
Assign(F,’kvadraty.in’);
Reset(F);i:=0;
115
While Not Eof(F) Do Begin
Inc(i);
ReadLn(F,A[i]);M:=Length(A[i]);
End;
Close(F);N:=i;i:=0;
While (i<=M+1) Do Begin Inc(i);A[0]:=A[0]+’0';End;
While (i<=M+1) Do Begin Inc(i);A[N]:=A[N]+’0';End;
For i:=0 to N do A[i]:=’0'+A[i];
For i:=0 to N do A[i]:=A[i]+’0';
Max:=1;
For i:=1 to N do
For j:=2 to M+1 do
If (A[i,j]=’1')and(A[i-1,j]=’0')and(A[i,j-1]=’0') Then
begin
K:=0;
while A[i,j+k]=’1' do inc(k);
L:=0;
while A[i+l,j]=’1' do inc(L);
if Max<L*K then Max:=L*K;
end;
Assign(F,’kvadraty.Out’);
ReWrite(F);
WriteLn(F,Max);
Close(F);
End.
Program z12;
var m,k,MaxCol,Max,i,Col:longint;
f :text;
procedure init;
begin
assign(f,’pos.in’);
reset(f);
read(f,m);
Max:=m;
MaxCol:=1;
Col:=1;
while not Eof(f) do
begin
read(f,k);
if m=k then
begin
inc(Col);
if Col>MaxCol then
begin
MaxCol:=Col;
116
Max:=k;
end;
end
else
Begin
Col:=1;
M:=k;
end;
end;
close(f);
end;
Procedure work;
begin
end;
Procedure exi;
begin
assign(f,’pos.out’);
rewrite(f);
write(f,MaxCol,’ “,Max);
close(f);
end;
Begin
init;
work;
exi;
end.
Program z13;
var
Name,Kol :array[1..15000] of integer;
i,j,n,k,index,max :integer;
f :text;
Flag : boolean;
begin
assign(f,’pos.in’);
reset(f);
i:=1;
readln(f,Name[1]);
Kol[1]:=1;
while not eof(f) do
begin
readln(f,k);
Flag:=False;
for J:=1 to i do
117
if k=Name[j] then
while A[i+l,j]=’1' do inc(L);
if Max<L*K then Max:=L*K;
end;
Assign(F,’kvadraty.Out’);
ReWrite(F);
WriteLn(F,Max);
Close(F);
End.
Program z12;
var m,k,MaxCol,Max,i,Col:longint;
f :text;
procedure init;
begin
assign(f,’pos.in’);
reset(f);
read(f,m);
Max:=m;
MaxCol:=1;
Col:=1;
while not Eof(f) do
begin
read(f,k);
if m=k then
begin
inc(Col);
if Col>MaxCol then
begin
MaxCol:=Col;
Max:=k;
end;
end
else
Begin
Col:=1;
M:=k;
end;
end;
close(f);
end;
Procedure work;
begin
end;
118
Procedure exi;
begin
assign(f,’pos.out’);
rewrite(f);
write(f,MaxCol,’ “,Max);
close(f);
end;
Begin
init;
work;
exi;
end.
Program z13;
var
Name,Kol :array[1..15000] of integer;
i,j,n,k,index,max :integer;
f :text;
Flag : boolean;
begin
assign(f,’pos.in’);
reset(f);
i:=1;
readln(f,Name[1]);
Kol[1]:=1;
while not eof(f) do
begin
readln(f,k);
Flag:=False;
for J:=1 to i do
if k=Name[j] then
for i:=1 to n do
if (i mod 2)=0 then write(f,Stroka[i]) else write(f,Stroka[n-i+1]);
close(f);
end.
Program z16;
var
x,y :array[1..201] of real;
i,n : byte;
S : real;
f :text;
begin
S:=0;
assign(f,’mnogoyg.in’);
119
reset(f);
i:=0;
while not eof(f) do
begin
inc(i);
readln(f,x[i],y[i]);
end;
close(f);
n:=i;
x[n+1]:=x[1];
y[n+1]:=y[1];
for i:=1 to n do
S:=s+(x[i+1]-x[i])*(y[i+1]+y[i])/2;
writeln(s);
end.
120
Часть II. Подготовка к олимпиаде
ВВЕДЕНИЕ
Вторая часть книги “Олимпиады по информатике” посвящена вопросам, связанным с подготов-
кой учащихся к соревнованиям.
Готовя участника к олимпиаде, необходимо помнить о триединстве основных компонент:
- тренировка логического мышления;
- работа над техникой реализации;
- психологическая подготовка.
Я считаю, что основное при подготовке ребят - необходимость выработки у них логически-
структурного мышления: умение выбрать из условия задачи главное; разбить основную задачу на
подзадачи; определить, к какому классу можно их отнести; выбрать наилучший метод (алгоритм)
решения.
Данная книга не является учебником по алгоритмизации в полном понимании, вопросы техниче-
ской подготовки рассматриваются лишь в той мере, в какой они могут быть использованы при реше-
нии задач, обычно присутствующих на олимпиадах по информатике. Ряд методов и алгоритмов ре-
шения задач рассмотрены менее подробно, другие - более. Это, в основном, связано с анализом работ
наших ребят, трудностей, с которыми они сталкиваются, и ошибок, которые они допускают при ре-
шении олимпиадных задач.
В процессе психологической подготовки необходимо настроить участника на желание и умение
максимально реализовать свои потенциальные возможности (заметьте - не победить, а макси-
мально реализовать) в экстремальных условиях, которые предъявляет олимпиада.
2.1 Техническая подготовка
2.1.1 О структурном программировании
В чем преимущества структурного подхода к программированию?
1. Можно ожидать, что логика работы программы будет более понятна программирующему.
2. Если Вы пока не знаете, как реализовать какой-либо модуль, всегда можно поставить “умозри-
тельную” машину, которая ничего не делает.
3. Возможность “работать” (программировать) с отдельным модулем.
4. Независимость “умозрительных” машин одного уровня позволяет независимо модифициро-
вать блоки программы без затрагивания других блоков. Как отмечал Э. Дейкстра: “…модификации
программ могут быть теперь представлены заменой одной (умозрительной) машины другой подхо-
дящей машиной”.
5. Проведение отладки структурированных программ намного легче, чем не структурированных.
6. Можно ожидать, что это оградит нас от ненужной работы. Если нет заварки, наша программа
просто завершит работу.
7. “Структурный подход” позволяет проводить целенаправленную подготовку к участию в
олимпиадах по информатике. Если модули независимы друг от друга, то можно заранее подготовить
машины нижнего уровня, например, блок сортировки, блок поиска в глубину, поиска в ширину, блок
обработки входной информации. Отработав их в подготовительный период, на олимпиаде, исходя из
задачи, использовать в том или ином сочетании.
Небольшое замечание. Часто, сравнивая языки программирования, говорят, что Паскаль –
структурированный язык. А, например, Бейсик – нет. Что один язык лучше другого. Хочется напом-
нить таким спорщикам следующее: каждый язык программирования наиболее удобен для опре-