Тур 2

30.11.98-13.12.98 г.

Уважаемые участники олимпиады!
К сожалению, большое число решений задач
первого тура олимпиады оформлены не по
правилам !!!
Пожалуйста, строго соблюдайте требования к вводу и
выводу данных и оформлению писем с решениями задач!!!

Задача 2A


"Книжная полка"

Известно, что предметом большинства самых ожесточенных споров в молодых семьях является расстановка книг на полках.На эту актуальную тему Вам предлагается следующая задача. На свадьбу молодожены получили в подарок одну книжную полку длиной M см и высотой N см, а также собрание японской классической поэзии,состоящее из M томов толщиной 1 см ивысотой N см. Сколькими различными способами они могут расставить это собрание на полке, если каждую книгу можно поставить вертикально или положить горизoнтально на полку или на другие книги.
Ваша программа должна считать исходные данные из файла TASK2A.DAT. В первой строке этого файла находится число M, во второй - число N. Числа M и N - целые, (1<M<=100, 1<N<=10). Ваша программа должна определить количество способов расстановки книг на полке и записать его в файл TASK2A.SOL.
Примеры входных и выходных данных:

TASK2A.DAT:
3
2

TASK2A.SOL:
18

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

Задача 2B

"Подземный ход"

Задачей, приведенной ниже, серьезно занимались в эпоху феодализма. Требовалось эффективное и экономное решение. Так и зародилась научная организация труда.
Средневековые крепости часто имели вид выпуклых многоугольников. Даны планы двух крепостей. Определите, где нужно рыть подземный ход из одной крепости в другую так, чтобы его длина была бы наименьшей.
Ваша программа должна считать исходные данные из файла TASK2B.DAT. В первой строке этого файла находится целое число M - число углов у первой крепости (1<M<20). В следующих M строках перечислены координаты углов крепости Xi, Yi (не обязательно в порядке обхода)
(-1000.000<Xi,Yi<1000.000). Затем, следует количество и координаты углов второй крепости.
Ваша программа должна решить задачу и записать в первой строке файла TASK2B.SOL координаты начала подземного хода, а во второй - конца. Результат должен быть найден с точностью до 0.001.
Примеры входных и выходных данных:

TASK2B.DAT:
5
2.000 1.000
4.000 2.000
2.000 4.000
4.000 4.000
3.000 6.000
3
6.000 1.000
5.000 3.000
7.000 5.000

TASK2B.SOL:
4.000 3.000
5.000 3.000

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

Задача 2C


"Тренировка"

В грузинских волшебных сказках приводится один из уникальных примеров эффективной тренировки. Юная дева, которая начала поднимать на высокую башню маленького теленочка и, тренируясь так каждый день, через год легко подняла на эту башню огромного быка. Хотелось бы, чтобы решение этих задач было бы столь же эффективным.
Две лягушки-легкоатлетки готовятся к ответственным соревнованиям на спортивной дорожке длиной 10 м. Они тренируются следующим образом. Одна лягушка прыгает так, чтобы ее новое положение было бы симметрично прежнему, относительно другой лягушки. Затем вторая лягушка прыгает на 10 см по дорожке. Либо наоборот, одна лягушка прыгает на 10 см, а затем другая прыгает симметрично относительно первой. При этом они прыгают так, чтобы остаться на спортивной дорожке. Известно, какое положение они занимали на дорожке в начале и конце тренировки. Найдите какую-нибудь из возможных последовательностей перемещений лягушек из начального положения в конечное.
Ваша программа должна считать исходные данные из файла TASK2C.DAT. В двух строках этого файла находятся по два числа - положения лягушек в начале и конце тренировки. Оно определяется расстоянием (в дм) от начала дорожки и находится в диапазоне от 0 до 100 включительно.
Ваша программа должна решить задачу и записать в первую строку файла TASK2C.SOL количество положений лягушек в найденной последовательности перемещений, а в следующие строки - эти положения.
Примеры входных и выходных данных:

TASK2C.DAT:
15 29
40 50

TASK2C.SOL:
7
15 29
41 28
40 52
39 26
38 50
39 28
40 50

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

Задача 2D


"Число с различными цифрами"
Продолжим изучать свойства натуральных чисел. Найдите N-е по порядку число с различными цифрами. Первым таким числом считайте 1. Ваша программа должна считать число N из файла TASK2D.DAT (1<=N<=8877690).
Ваша программа должна решить задачу и записать N-е число с различными цифрами в файл TASK2D.SOL.
Примеры входных и выходных данных:
TASK2D.DAT:
100
TASK2D.SOL:
123

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

Задача 2Е

"Игра +-"

Все имеет своплюсы. Даже минусы иногда превращаются в них. N минусов записаны в ряд. Двое игроков поочередно исправляют один или два рядом стоящих минуса на плюсы. Выигрывает тот, кто исправит последний минус. Составьте программу, которая играет в эту игру. Вы должны использовать дополнительные функции для получения хода соперника. Описание и примеры этих функций находятся в файлах PLAY2E.PAS (для языка Pascal) и PLAY2E.H, PLAY2E.C, PLAY2E.CPP (для языков C/C++). Данные функции строго проверяют выполнение правил игры, но играют за соперника не лучшим образом.
Ваша программа должна считать число N из файла TASK2E.DAT (1<N<100).
Для начала игры Ваша программа должна вызвать функцию BeginGame, передав ей номер игрока, за которого будет играть Ваша программа. Для того, чтобы сделать свой ход, вызовите функцию Move, передав ей номер первого минуса, который Вы хотите исправить на плюс и их количество. Для того, чтобы соперник сделал ход, Ваша программа должна вызвать функцию OppMove, передав ей переменные, в которые она возвратит номер первого минуса, который соперник исправил на плюс, и их количество. По окончании игры вызовите функцию EndGame.
Пример игры:
TASK2E.DAT:
3

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

Задача 2E: PLAY2E.PAS, PLAY2E.H

Unit Play2E;

Interface < br>
Procedure BeginGame (P : Integer);
Procedure EndGame;
Procedure Move (J, C : Integer);
Procedure OppMove (Var J, C : Integer);

Implementation

Const
MaxN = 100;
S : Integer = 0;
Var
P, N, K : Integer;
A : Array [1..MaxN] Of Boolean;

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

Procedure BeginGame (P : Integer);
Var
F : Text;
J : Integer;
Begin
If S <> 0 Then Error;
If (P <> 1) And (P <> 2) Then Error;
Play2E.P := P; S := P;
Assign (F, 'TASK2E.DAT'); ReSet (F);
Read (F, N); K := N;
Close (F);
For J := 1 To N Do A[J] := False;
WriteLn ('Начало игры.');
End;

Procedure Move (J, C : Integer);
Begin
If S <> 1 Tn Error;
If (J < 1) Or ((J+C-1) > N) Or (C < 1) Or (C > 2) Then Error;
If A[J] Or A[J+C-1] Then Error;
A[J] := True; A[J+C-1] := True; K := K-C;
If K > 0 Then S := 2 Else S := 3;
WriteLn (P, '-й игрок исправил ', J, '-й минус на плюс.');
If C = 2 Then
WriteLn (P, '-й игрок исправил ', J+1, '-й минус на плюс.');
End;

Procedure OppMove (Var J, C : Integer);
Begin
If S <> 2 Then Error;
J := 1; While A[J] Do J := J+1;
If (J < N) And Not A[J+1]
Then C := 2
Else C := 1;
A[J] := True; A[J+C-1] := True; K := K-C;
If K > 0 Then S := 1 Else S := 3;
WriteLn (3-P, '-й игрок исправил ', J, '-й минус на плюс.');
If C = 2 Then
WriteLn (3-P, '-й игрок исправил ', J+1, '-й минус на плюс.');
End;

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

End.


void BeginGame (int p);
void EndGame (void);
void Move (int j, int c);
void OppMove (int * j, int * c);

Задача 2E: PLAY2E.C/PLAY2E.CPP

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

static int s = 0;
static int p, n, k;
static int * a;

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

void BeginGame (int r)
{
FILE * f;
int j;

if (s != 0) Error ();
if (r != 1 && r != 2) Error ();
p = r; s = r;
f = fopen ("task2e.dat", "r");
fscanf (f, "%d", & n); k = n;
fclose(f);
a = (int *) malloc (n * sizeof (int));
for(j = 0; j < n; j ++) a[j] = 0;
printf ("Начало игры. ");
}

void Move (int j, int c)
{
if (s != 1) Error ();
if (j < 1 || j+c-1 > n || c < 1 || c > 2) Error ();
j --;
if (a[j] || a[j+c-1]) Error ();
a[j] = 1; a[j+c-1] = 1; k -= c;
s = k > 0 ? 2 : 3;
j ++;
printf ("%d-й игрок исправил %d-й минус на плюс. ", p, j);
if (c == 2)
printf ("%d-й игрок исправил %d-й минус на плюс. ", p, j+1);
}

void OppMove (int * j, int * c)
{
int i;
int d;

if (s != 2) Error ();
for (i = 0; a[i]; i ++);
if (i < n-1 && ! a[i+1]) d = 2;
else d = 1;
a[i] = 1; a[i+d-1] = 1; k -= d;
i ++;
s = k > 0 ? 1 : 3;
printf ("%d-й игрок исправил %d-й минус на плюс. ", 3-p, i);
if (d == 2)
printf ("%d-й игрок исправил %d-й минус на плюс. ", 3-p, i+1);
* j = i;
* c = d;
}

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

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

29 ноября 1998 года Пасихов

© LIKT 1998-2018