Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Условия 1 тура
Тур 1 15.11.98-29.11.98г.

Обращение жюри.

Поздравляем с началом олимпиады!
На первом туре Вам предлагается решить 5 простых задач. Для их решения требуется знание только стандартных алгоритмов, изучаемых в школе. При решении задач обратите особое внимание на эффективность работы Вашей программы. Если задачи покажутся Вам слишком легкими, не бросайте олимпиаду, в следующих турах Вам будет над чем подумать.
Пожалуйста, строго соблюдайте требования к вводу и выводу данных и оформлению писем с решениями задач.

Задача 1A

"Простые числа"

Многие свойства простых чисел поражали древних мыслителей и удивляют современных математиков до сих пор.При изучении их свойств сегодня применяются сложнейшие математические методы. Мы предлагаем задачу, которая раскрывает еще не исследованные свойства простых чисел.Определите, какая из цифр в десятичной записи всех простых чисел из заданного диапазона встречается чаще всего. Если таких цифр несколько, найдите наименьшую из них. Ваша программа должна считать исходные данные из файла TASK1A.DAT. В первой строке этого файла находится число A, во второй - число B. Числа A и B - целые, (1<A<B<10000). Ваша программа должна решить задачу для интервала A<=P<=B. Известно, что в этом интервале имеется хотя бы одно простое число. Ваша программа должна записать найденную цифру в файл TASK1A.SOL. Примеры входных и выходных данных:
TASK1A.DAT:
10
20
TASK1A.SOL:
1

Максимальное количество баллов: 20

Задача 1B

"Мера"

Понятие меры расширяет бытовые понятия длины, площади, объема. Решив эту задачу, Вы найдете меру Лебега объединения отрезков на прямой. Дано N отрезков на прямой. Определите длину части прямой покрытой отрезками. Ваша программа должна считать исходные данные из файла TASK1B.DAT. В первой строке этого файла находится число N - количество отрезков (1<N<10000). В каждой i-ой из последующих N строк находятся два действительных числа Ai и Bi - координаты левого и правого конца i-го отрезка
(-100.0<Ai<Bi<100.0).
Ваша программа должна определить длину части прямой, покрытой отрезками и записать ее в файл TASK1B.SOL.
Примеры входных и выходных данных:

TASK1B.DAT:
4
11.0 13.0
4.0 8.0
10.0 13.0
2.0 5.0

TASK1B.SOL:
9.0
Максимальное количество баллов: 30

Задача 1C


"Симметрия"

На Востоке симметрия олицетворяет смерть. Чтобы с ней не столкнуться слишком рано, нужно научиться быстро определять симметричность. Дана последовательность целых чисел X1, X2, ..., Xn. Ее подпоследовательность Xi, Xi+1, ..., Xj называется симметричной, если Xi=Xj, Xi+1=Xj-1, ..., Xj=Xi. Найдите симметричную подпоследовательность максимальной длины. Если таких окажется несколько, достаточно найти одну из них.
Ваша программа должна считать исходные данные из файла TASK1C.DAT. В первой строке этого файла находится число n - количество элементов в последовательности (1<n<1000). В следующих n строках записаны элементы последовательности Xi (1<=i<=n, -1000<=Xi<=1000).

Ваша программа должна решить задачу и записать в файл
TASK1C.SOL два числа: номер первого элемента и длину
подпоследовательности.

Примеры входных и выходных данных:

TASK1C.DAT:
6
1
2
1
2
1
2

TASK1C.SOL:
1
5

Максимальное количество баллов: 30

Задача 1D

"Игра Баше"
Когда очень скучно на уроке и спичек нет, то часто рисуют на парте палочки и играют с соседом в эту игру. Но лучше написать программу и играть с ней, сохраняя школьное имущество. На столе лежит N спичек. Два игрока по очереди забирают со стола несколько спичек (от 1 до M). Выигрывает тот, кто берет последнюю спичку. Напишите программу, которая играет в эту игру. Вы должны использовать дополнительные функции для получения хода соперника. Описание и примеры этих функций находятся в файлах PLAY1D.PAS (для языка Pascal) и PLAY1D.H, PLAY1D.C, PLAY1D.CPP (для языков C/C++). Данные функции строго проверяют выполнение правил игры, но играют за соперника не лучшим образом. Ваша программа должна считать исходные данные из файла TASK1D.DAT. В первой строке этого файла находится число P -номер игрока, за которого играет ваша программа. Во второйстроке файла находится число N - количество спичек на столе (2<=N<=10000). В третьей строке находится число M -максимальное число спичек, которое можно взять за раз (1<M<100).Для начала игры Ваша программа должна вызвать функцию BeginGame. Для того, чтобы сделать свой ход, вызовите функцию TakeMatch, передав ей количество спичек, взятых со стола. Для того, чтобы соперник сделал ход, Ваша программа должна вызвать функцию OppTakeMatch. Она возвратит количество спичек, взятых соперником. По окончании игры вызовите функцию EndGame. Запишите в файл TASK1D.SOL количество спичек, взятых Вашей программой в течение игры.

Пример игры:
TASK1D.DAT:
1
10
3
Ход игры:
Начало игры.
1-й игрок взял 2 спички.
2-й игрок взял 2 спички.
1-й игрок взял 2 спички.
2-й игрок взял 3 спички.
1-й игрок взял 1 спичку.
Конец игры.
TASK1D.SOL:
5
Дополнительные файлы к условию задачи:
PLAY1D.PAS
PLAY1D.H
PLAY1D.C
PLAY1D.CPP
Максимальное количество баллов: 20

Задача 1D: PLAY1D.PAS

Unit Play1D;

Interface

Procedure BeginGame;
Procedure EndGame;
Procedure TakeMatch (J : Integer);
Function OppTakeMatch : Integer;

Implementation

Const
S : Integer = 0;
Var
P, N, M : Integer;
J, K : Integer;

Procedure Error;
Begin
WriteLn ('Нарушены правила игры!');
Halt (1);
End;

Procedure BeginGame;
Var
F : Text;
Begin
If S <> 0 Then Error;
Assign (F, 'TASK1D.DAT'); ReSet (F);
Read (F, P); S := P;
Read (F, N); K := N;
Read (F, M); J := 1;
Close (F);
WriteLn ('Начало игры.');
End;

Procedure TakeMatch (J : Integer);
Begin
If S <& gt; 1 Then Error;
If (J <= 0) Or (J > K) Or (J > M) Then Error;
K := K - J;
If K > 0 Then S := 2 Else S := 3;
WriteLn (P, '-й игрок взял ', J, ' спич(ку,ки,ек).');
End;

Function OppTakeMatch : Integer;
Begin
If S <> 2 Then Error;
J := J + 1;
If (J > K) Then J := K;
If (J > M) Then J := 1;
OppTakeMatch := J;
K := K - J;
If K > 0 Then S := 1 Else S := 3;
WriteLn (3-P, '-й игрок взял ', J, ' спич(ку,ки,ек).');
End;

Procedure EndGame;
Begin
If S <> 3 Then Error;
S := 4;
WriteLn ('Конец игры.');
End;

End.




Задача 1D: PLAY1D.H

void BeginGame (void);
void EndGame (void);
void TakeMatch (int j);
int OppTakeMatch (void);
<

Задача 1D: PLAY1D.C/PLAY1D.CPP

#include <stdlib.h>
#include <stdio.h>
#include "play1d.h"

static int s = 0;
static int p, n, m;
static int j, k;

static void Error (void)
{
printf ("Нарушены правила игры! ");
exit (EXIT_FAILURE);
}

void BeginGame (void)
{
FILE * f;
if (s != 0) Error ();
f = fopen ("task1d.dat", "r");
fscanf (f, "%d%d%d", & p, & n, & m);
s = p; k = n; j = 1;
fclose (f);
printf ("Начало игры. ");
}

void TakeMatch (int j)
{
if (s != 1) Error ();
if (j <= 0 || j > k || j > m) Error ();
k -= j;
s = k > 0 ? 2 : 3;
printf ("%d-й игрок взял %d спич(ку,ки,ек). ", p, j);
}

int OppTakeMatch (void)
{
if (s != 2) Error ();
j ++;
if (j > k) j = k;
if (j > m) j = 1;
k -= j;
s = k > 0 ? 1 : 3;
printf ("%d-й игрок взял %d спич(ку,ки,ек). ", 3-p, j);
return j;
}

void EndGame (void)
{
if (s != 3) Error ();
s = 4;
printf ("Конец игры. ");
}

Задача 1E

"Совершенные строки"

Понятия гармонии, идеала и совершенства впервые появились в Древней Греции и развивались философами эпохи Возрождения, а в дальнейшем И.Кантом и немецкими романтиками. Внося свой скромный вклад в развитие этих понятий, предложим такую задачу. Дана строка символов S, состоящая из маленьких букв латинского алфавита. Строка T называется идеальной в S, если T+T является подстрокой S. Максимальная длина идеальной в S строки называется индексом совершенства S. Если идеальных в S строк не существует, то индекс совершенс тва S полагают равным нулю. Напишите программу, которая определяет индекс совершенства данной строки.
Замечание: A+B обозначает конкатенацию строк A и B.
Подстрокой строки S называется последовательность подряд стоящих символов строки S. Ваша программа должна считать строку S из файла TASK1E.DAT. Длина строки не превышает 100 символов. Ваша программа должна определить индекс совершенства строки S и записать его в файл TASK1E.SOL.
Примеры входных и выходных данных:

TASK1E.DAT:
hehadhadit

TASK1E.SOL:
3
Максимальное количество баллов: 20

 

Последий день отравки решений 29 ноября 1998 года. Решения отправлять по адресу olymp@.pmg17.vstu.vinnica.ua

15 ноября 199года


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"