Олимпиады по информатике (стр. 3 )

max, n,n1,n2,n3:Integer;

Begin

ClrScr;

Writeln('Введите строку:');

Readln(a);

n1:=0;n2:=0;n3:=0;

b:='з';c:='ж';d:='к';

While Pos(b, a)<>0 Do

Begin

Inc(n1);

b:=b+'з';

End;

While Pos(c, a)<>0 Do

Begin

Inc(n2);

c:=c+'ж';

End;

While Pos(d, a)<>0 Do

Begin

Inc(n3);

d:=d+'к';

End;

max:=n1;

If n2>max Then max:=n2;

If n3>max Then max:=n3;

Write(max,' - ');

If max=n1 Then Write(' зелёного цвета ');

If max=n2 Then Write('жёлтого цвета ');

If max=n3 Then Write('красного цвета');

Readln;

End.

Если ожерелье замкнуто, то в случае совпадения 1-го и последнего символов, необходимо было бы ещё подсчитать длину цепочки одинаковых бусинок в месте сцепления. Для подсчёта использована функция Copy, которая в качестве результата выдаёт подстроку, содержащуюся в строке.

Program olimp72; {ожерелье замкнуто}

Uses Crt;

Const nmax=20;

Var a, b,c, d:String;

i, k,max, n,n1,n2,n3:Integer;

Begin

ClrScr;

Writeln('Введите строку:');

Readln(a);

k:=Length(a);

n1:=0;n2:=0;n3:=0;

b:='з';c:='ж';d:='к';

While Pos(b, a)<>0 Do

Begin

Inc(n1);

b:=b+'з';

End;

While Pos(c, a)<>0 Do

Begin

Inc(n2);

c:=c+'ж';

End;

While Pos(d, a)<>0 Do

Begin

Inc(n3);

d:=d+'к';

End;

If a[1]=a[k] Then

Begin

n:=0;i:=1;

b:=a[1];

While Copy(a,1,i)=b Do

Begin

Inc(n);

Inc(i);

b:=b+a[1];

End;

b:=a[1];

i:=0;

While Copy(a, k-i, i+1)=b Do

Begin

Inc(n);

Inc(i);

b:=b+a[1];

End;

If (a[1]='з') And (n>n1) Then n1:=n;

If (a[1]='ж') And (n>n2) Then n2:=n;

If (a[1]='к') And (n>n3) Then n3:=n;

End;

max:=n1;

If n2>max Then max:=n2;

If n3>max Then max:=n3;

Write(max,' - ');

If max=n1 Then Write(' зелёного цвета ');

If max=n2 Then Write('жёлтого цвета ');

If max=n3 Then Write('красного цвета');

Readln;

End.

Ниже приведено ещё одно решение для незамкнутого ожерелья. Попробуйте в нём разобраться самостоятельно.

Program olimp73;

Uses Crt;

Const nmax=20;

Var a, b,s:String;

i, j,k, poz, max, n:Integer;

t1:Array[1..nmax] Of String;

t2:Array[1..nmax] Of Integer;

Procedure cvet;

Begin

If s[1]='з' Then Write(' зелёного цвета');

If s[1]='ж' Then Write(' жёлтого цвета');

If s[1]='к' Then Write(' красного цвета');

End;

Begin

ClrScr;

Writeln('Введите строку:');

Readln(a);

k:=Length(a);

b:=a[1]; j:=0;

For i:=1 To k-1 Do

Begin

If (a[i]<>'з') And (a[i]<>'ж') And (a[i]<>'к') Then Halt;

If a[i]=a[i+1] Then b:=b+a[i+1]

Else Begin

Inc(j);

t1[j]:=b;

t2[j]:=Length(b);

b:=a[i+1];

End;

End;

Inc(j);

t1[j]:=b;

t2[j]:=Length(b);

max:=t2[1];

poz:=1;

For i:=1 To j Do

If max<t2[i] Then Begin

max:=t2[i];

poz:=i;

End;

Write(max,' - ');

s:=t1[poz];

cvet;

For i:=1 To j Do

If (t2[i]=max) And (poz<>i) Then

Begin

Writeln;

Write(' или ');

s:=t1[i];

cvet;

End;

Readln;

End.

При решении данной задачи «продвинутые» учащиеся могли использовать технику работы с линейными однонаправленными списками и кольцевыми однонаправленными списками.

Дополнительная задача

Одно из возможных решений этой широко известной задачи приведено ниже. Боле подробно эта задача обсуждается в различных книгах и статьях. Желающие могут найти её различные решения в моей брошюре «Несколько каверзных задач».

Program dop;

Uses Crt;

Var a, b:Integer;

Begin

ClrScr;

Write('a= ');

Readln(a);

Write('b= ');

Readln(b);

a:=a+b;

b:=a-b;

a:=a-b;

Writeln('a=',a);

Writeln('b=',b);

Readln;

End.

Задачи районной олимпиады по информатике, 2003 год

Задача 1 «Таблица Пифагора»

Для заданного числа n (n<19) вывести на экран таблицу умножения Пифагора. Ширина у всех столбцов одинакова и минимальна. Между столбцами расстояние в один пробел.

Задача 2 «Окружности»

На плоскости заданы n (n<20) окружностей. Указать ту окружность, которая содержит в себе максимальное (ненулевое) количество других окружностей. Если таких окружностей несколько, то указать любую из них.

Замечания

1 Окружность задаётся координатами центра и радиусом (считать, что это – целые числа)

2 Если окружности пересекаются, то ни одна из них не содержит другую

3 Если окружности касаются внутренним образом, то можно считать, что одна из них содержит другую.

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

1-я строка содержит единственное число n – количество окружностей

2-я строка содержит координаты центра 1-й окружности и радиус, введённые через пробел

……………………………………

(n+1)-я строка содержит координаты центра n-й окружности и радиус, введённые через пробел

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

Единственная строка, которая содержит координаты центра и радиус искомой окружности через пробел, если такая окружность существует, и слово НЕТ – в противном случае.

Задача 3 «День недели»

Как известно, високосными являются года, номер которых делится на 4 за исключением тех, номера которых делятся на 100 и не делятся на 400. Даны три числа D, M,G (1950<G<2150), обозначающие номера дня, месяца и года соответственно. Определить день недели, соответствующий этому дню.

Задача 4 «Хитрая последовательность»

Последовательность 1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,… строится следующим образом

1.  1-й элемент равен 1

2.  В полученной последовательности находят m–максимальный элемент и к последовательности добавляют элементы 1,2,…,m+1

3.  Пункт 2 повторяют бесконечное число раз

4.  Найти n-ый (n<=1000000) элемент последовательности.

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

Единственная строка, содержащая n.

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

Единственная строка, содержащая значение n-го элемента

Задача 5 «Запутанное выражение»

Дано выражение, состоящее из чисел, переменных, знаков арифметических действий (+,-,*,/) и содержащее скобки следующих типов: (), [], {}. Определить правильность расстановки скобок.

Замечания

1.  Выражение в целом построено корректно за исключением возможно лишь расстановки скобок

2.  Скобки считаются расставленными правильно, если выполняются следующие условия

1)  Выражение содержит одинаковое количество открывающихся и закрывающихся скобок.

2)  Если количество скобок ненулевое, то любой открывающейся скобке можно поставить в соответствие закрывающуюся скобку того же типа.

3)  При выполнении п.2) выражение, ограниченное скобками одного и того же типа, должно удовлетворять пунктам 1)-3).

Решения задач районной олимпиады по информатике

Задача 1

Самые большие числа, которые будут получаться при умножении, являются трёхзначными. Учитывая, что между числами должен быть один пробел, приходим к заключению, что для вывода на экран каждого числа необходимо отводить четыре позиции. Почему n<19? Ответ прост: чтобы выводимая строка умещалась на одной экранной строке. Приведённое ниже решение под силу практически всем и не содержит никаких технических трудностей.

Program olimp1;

Uses Crt;

Var i, j,n:Integer;

Begin

Write('n=');

Readln(n);

ClrScr;

Write(' ':4); {левая верхняя клетка таблицы}

For j:=1 To n Do Write(j:4); {номера столбцов}

Writeln;

For i:=1 To n Do

Begin

Write(i:4); {номер строки}

For j:=1 To n Do Write(i*j:4); {строка таблицы}

Writeln;

End;

Readln;

End.

Задача 2

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

ОМ≤ОО1+О1М≤ОО1+R1≤R.

Здесь R1– радиус внутренней, R – внешней

окружностей.

Запишем полученное условие в виде: ОО1≤R-R1 или ОО12≤(R-R1)2. Квадрат расстояния между двумя точками О(x0,y0) и О1(x1,y1) находится по формуле ОО12=(x1-xo)2+(y1-y0)2. А дальше всё уже просто: в цикле для каждой окружности считаем, сколько же окружностей содержатся внутри неё. Для этой цели заводим массив m, элементы которого предварительно зануляем. Затем находим максимальный элемент полученного массива и его индекс (номер). Если максимальный элемент не равен нулю, то по полученному номеру максимального элемента выводим на экран координаты центра и радиус окружности. Если максимальный элемент равен нулю, то ни одна из окружностей не содержится внутри другой, и на экран выводим слово «Нет». Желающим больше узнать о взаимном расположении окружностей, можно порекомендовать, ставшую библиографической редкостью замечательную книгу Ж. Адамара «Элементарная геометрия», которая содержит ряд фактов, обычно не упоминаемых в школьном курсе геометрии, но часто используемых при решении олимпиадных задач. Приведу одну из теорем:

1. Если две окружности расположены одна вне другой, то расстояние между их центрами больше суммы радиусов, и обратно.

2. Если они касаются друг друга внешним образом, то расстояние между их центрами равно сумме радиусов, и обратно.

3. Если они пересекаются, то расстояние между их центрами заключается между суммой радиусов и их разностью, и обратно.

4. Если они касаются друг друга внутренним образом, то расстояние между их центрами равно разности радиусов, и обратно.

5. Если одна окружность лежит внутри другой, то расстояние между их центрами меньше разности радиусов, и обратно.

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

Возможное решение задачи приведено ниже.

Program olimp2;

Uses Crt;

Const nmax=19;

Var i, k,n, max, kmax:Integer;

x, y,r, m:Array[1..nmax] Of Integer;

Begin

ClrScr;

Write('n= ');

Readln(n);

Writeln('Введите координаты центра и радиусы окружностей');

For k:=1 To n Do Readln(x[k],y[k],r[k]);

For k:=1 To n Do m[k]:=0;

For k:=1 To n Do