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

For i:=1 To n Do

If (i<>k) And (r[k]>r[i]) And

(Sqr(x[k]-x[i])+Sqr(y[k]-y[i])<=Sqr(r[k]-r[i])) Then Inc(m[k]);

max:=m[1]; kmax:=1;

For k:=2 To n Do

If m[k]>max Then

Begin

max:=m[k];

kmax:=k;

End;

If max=0 Then Writeln('Нет')

Else Writeln('Окружность: ',x[kmax],' ',y[kmax],' ',r[kmax]);

Readln;

End.

Задача 3

Каждый компьютер имеет часы и календарь, поэтому у него можно спросить, который час и какое сегодня число, а при желании и подправить дату. Для работы со временем и датой на Паскале необходимо использовать модуль Dos. В этом модуле имеется восемь процедур, предназначенных для работы с датой и временем. Позволю себе привести 2 процедуры этого модуля:

GetDate – узнать дату,

SetDate – установить дату.

Для использования этих процедур необходимо придумать имена переменным, обозначающим дату:

god – год (с 1980-го по 2099-й),

mes – месяц (1-12),

den – день месяца (1-31),

den_ned – номер дня недели от 0 (воскресенье) до 6 (суббота).

Эти переменные должны быть целочисленными типа Word (но не Integer). Напомню, что переменная типа Word – целое значение из диапазона 0-65535.

Текст программы приведён ниже и в комментариях не нуждается. Ограничение на год (с 1980-го по 2099-й) связано с особенностями календаря, встроенного нынче в компьютер. Однако, при проверке, по крайней мере, для дат, ближайших за крайними, результат приведенной программой выдаётся верный.

Program olimp3;

Uses Crt, Dos;

Var god, mes, den, den_ned, god1,mes1,den1,den_ned1:Word;

t:String;

Begin

ClrScr;

Getdate(god, mes, den, den_ned);

Write('Введи число, месяц и год: ');

Readln(den1,mes1,god1);

SetDate(god1,mes1,den1);

GetDate(god1,mes1,den1,den_ned1);

Case den_ned1 Of

0:t:='воскресенье';

1:t:='понедельник';

2:t:='вторник';

3:t:='среда';

4:t:='четверг';

5:t:='пятница';

6:t:='суббота';

End;

Writeln(den1,'.',mes1,'.',god1,' - ',t);

SetDate(god, mes, den);

Readln;

End.

Можно поступить и по-другому: просчитывать последовательно даты назад и вперёд, начиная, скажем, с сегодняшнего дня. Вперёд, это хорошо. А вот назад, не совсем хорошо. Как учесть проводившиеся реформы календарей? Поэтому любой из таких алгоритмов будет считать давно прошедшую дату по «новому стилю». Попробуйте реализовать этот способ самостоятельно. Известны также специальные формулы, с помощью которых можно вычислять день недели. Попробуйте их найти, либо придумать такую формулу самостоятельно. Один из таких алгоритмов, который действителен, по крайней мере, с 1 марта 1900 года по 28 февраля 2100 года, я приведу. Согласно этому алгоритму, надо найти значение следующего выражения: Y=[365,25*G]+[30,6*I]+J-694,066. В этом выражении [ ] – целая часть числа, Y – число дней, прошедших с 1 марта 1900 г до дня с заданными J, M, A, где J – день, M – месяц, A – год. Значения G и I находятся из соотношений: если M<3, то G=A-1, I=M+13; если M≥3, то G=A, I=M+1. Остаток от деления [Y] на 7 образует номер дня недели: 0 – воскресенье, 1– понедельник и т. д. Программа, составленная по этому алгоритму, приведена ниже.

Program olimp31;

Uses Crt;

Var god, mes, den, g,y, i:LongInt;

Begin

ClrScr;

Write('Введи число, месяц и год: ');

Readln(den, mes, god);

If mes<3 Then

Begin

g:=god-1;

i:=mes+13;

End

Else

Begin

g:=god;

i:=mes+1;

End;

y:=Trunc(Trunc(365.25*g)+trunc(30.6*i)+den-694.066);

y:=y mod 7;

Case y Of

0:Writeln('воскресенье');

1:Writeln('понедельник');

2:Writeln('вторник');

3:Writeln('среда');

4:Writeln('четверг');

5:Writeln('пятница');

6:Writeln('суббота');

End;

Readln;

End.

Задача 4

Можно придумать формулу для вычисления n-го члена заданной последовательности. Сделаем проще, используя цикл. Решение представлено ниже и не содержит никаких технических трудностей. Разберитесь в этом решении, выполняя вручную программу по отдельным шагам для небольших значений n. После этого, если и были какие-либо вопросы, то они отпадут сами собой.

Program olimp4;

Uses Crt;

Var n, i,j, max:LongInt;

Begin

ClrScr;

Write('n=');

Readln(n);

j:=1;

max:=1;

i:=1;

While i<n Do

Begin

If j<max Then Begin

i:=i+1;

j:=j+1;

End

Else Begin

j:=0;

max:=max+1;

End;

End;

Writeln(n,'-й элемент равен ',j);

Readln;

End.

Задача 5

Сначала из вводимой строки формируем новую строку, состоящую только из скобок в том порядке, в котором они идут. Затем из этой строки последовательно удаляем идущие рядом парные скобки. Если парных скобок не найдено, то находим длину оставшейся строки. Если она равна нулю (строка пустая), то скобки были расставлены правильно. Если длина строки не равна нулю, то скобки были расставлены неверно.

Program olimp5;

Uses Crt;

Var k, n,m, m1,m2,m3:Integer;

s, s1:String;

mn:Set Of Char;

Begin

ClrScr;

Write('s=');

Readln(s);

n:=Length(s);

s1:='';

mn:=['(',')','[',']','{','}'];

For k:=1 To n Do

If s[k] In mn Then s1:=s1+s[k];

m:=1;

While m<>0 Do

Begin

If Pos('()',s1)=0 Then m1:=0

Else Begin

m1:=1;

Delete(s1,Pos('()',s1),2);

End;

If Pos('[]',s1)=0 Then m2:=0

Else Begin

m2:=1;

Delete(s1,Pos('[]',s1),2);

End;

If Pos('{}',s1)=0 Then m3:=0

Else Begin

m3:=1;

Delete(s1,Pos('{}',s1),2);

End;

m:=m1+m2+m3;

End;

If Length(s1)=0 Then Writeln('Да')

Else Writeln('Нет');

Readln;

End.

Задачи областной олимпиады по информатике

(система профтехобразования), 2003 год

1 день

Задача 1. Треугольник (5 баллов)

Вычислите, в какой координатной четверти расположен треугольник, образованный прямой, заданной уравнением y= ax + b, и осями координат.

Задача 2. Уравнение (5 баллов)

Написать программу для решения уравнения xy + x + y = 1000 в целых числах.

Задача 3 . Число π (5 баллов)

Вычислить значение числа π с точностью до тысячных методом Монте-Карло (используя генератор случайных чисел).

Задача 4 . Муравей (5 баллов)

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

Технические условия:

Данные хранятся во внешнем файле mur. dat следующим образом: в первой строке записывается количество звеньев ломаной; вторая строка – координаты муравья; в каждой последующей строке записывается четыре числа – координаты двух клеток, между которыми проходит граница.

Второй день

Задача 1. Произведение (10 баллов)

Дано натуральное число N. Вычислить произведение первых N сомножителей.

Задача 2. Роботландия (10 баллов)

Сообщество роботов живет по следующим законам:

– один раз в начале года они объединяются в группы по три или пять роботов;

– за год группа из 3 роботов собирает 5 новых, а группа из 5 роботов собирает 9 новых;

– роботы собираются так, чтобы собрать за год наибольшее количество;

– каждый робот живет три года после сборки.

Известно начальное количество роботов К (K>7) и все они только что собраны. Сколько роботов будет через N лет?

Задача 3. Физическая лаборатория (10 баллов)

При проведении физического эксперимента по фиксации траектории движения частиц с помощью ЭВМ детекторы сгруппированы следующим образом:

Д Д...Д

Д Д... Д

...............

Д Д... Д

Перекрытая детекторами область отображается в памяти ЭВМ двумерным массивом M[1:N,1:K], элементы которого представляют собой цифровую фотографию исследуемой области. При фиксации элементарной частицы детекторами в позиции (i, j) соответствующий элемент матрицы M принимает значение 1, в противном случае 0. Определите, содержит ли данная цифровая фотография информацию, которая может быть интерпретирована как след прямолинейной траектории, начинающейся и заканчивающейся за пределами фотографии.

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

Первый день

Задача 1

Ясно, что если a=0 или b=0 (или оба числа равны нулю), то прямая вместе с осями координат не образует никакого треугольника. Поэтому считаем, что a и b не равны нулю. В этом случае прямая проходит через точки (-b/a;0) и (0,b), лежащие на осях координат. Нарисовав прямую, легко заметить, что четверть, в которой лежит треугольник, определяется знаками чисел a и b. При a<0 и b>0 треугольник лежит в I четверти, при a>0 и b>0 – во II четверти, при a<0 и b<0 – в III четверти, при a>0 и b<0 – в IV четверти.

Program obl1;

Uses Crt;

Var a, b :real;

Begin

ClrScr;

Write('Введи a и b:');

Readln(a, b);

If (a=0) or (b=0)

Then Writeln('Треугольник не существует')

Else Begin

If (a>0) and (b>0)

Then Writeln('Треугольник во II четверти');

If (a>0) and (b<0)

Then Writeln('Треугольник в IV четверти');

If (a<0) and (b>0)

Then Writeln('Треугольник в I четверти');

If (a<0) and (b<0)

Then Writeln('Треугольник в III четверти');

End;

Readln;

END.

Задача 2

Легко запрограммировать переборное решение, но возникает проблема: в каком диапазоне должны меняться x и y? Выясним это. Прибавим число 1 к каждой из частей уравнения. Тогда левая часть легко раскладывается на два множителя. Получим:

x + 1 + xy + y = 1001 [ (x + 1)(y + 1) = 1001 (*)

Разложим число 1001 на простые множи=7∙11∙13.

Тогда возможны следующие случаи, позволяющие легко найти решения и без программирования:

x+1=1; y+1=1001;

x+1=-1; y+1=-1001;

x+1=7; y+1=143;

x+1=-7; y+1=-143;

x+1=11; y+1=91;

x+1=-11; y+1=-91;

x+1=13; y+1=77;