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


Годинник
 
Условия 3 тура

Тур 3

28.12.98-16.01.99г.

Оргкомитет и жюри олимпиады поздравляет вас и ваших учителей с наступающим Новым Годом!

Задача 3A


"Игры древней Индии"

Множество интереснейших игр пришли к нам из Древней Индии. Среди них шахматы, нарды, калах... Возможно, эта игра тоже родилась там. В клетках прямоугольной таблицы записаелые числа. Известно, что сумма всех чисел нечетна. Двое игроков поочередно стирают все числа из крайнего столбца или крайней строки таблицы. При этом игрок получает количество очков, равное сумме стертых им чисел. Игра кончается, когда в таблице не останется ни одного числа. Выигрывает тот, кто наберет большее количество очков. Составьте программу, которая играет в эту игру. Вы должны использовать дополнительные функции для получения хода соперника. Описание и примеры этих функций находятся в файлах PLAY3A.PAS (для языка Pascal) и PLAY3A.H, PLAY3A.C, PLAY3A.CPP (для языков C/C++). Данные функции строго проверяют выполнение правил игры, но играют за соперника не лучшим образом.
Ваша программа должна считать исходные данные из файла TASK3A.DAT. В первой строке этого файла находятся числа M и N - количество строк и столбцов таблицы (1<=M,N<=10). Вследующих M строках находится по N чисел, записанных в таблице. Числа находятся в диапазоне от -100 до 100. Для начала игры Ваша программа должна вызвать функцию BeginGame, передав ей номер игрока, за которого она будет играть. Для того, чтобы сделать свой ход, вызовите функцию Move, передав ей символ 'U', 'D', 'L' или 'R', если Вы стираете крайнюю верхнюю или крайнюю нижнюю строку, крайний левый или крайний правый столбец соответственно. Для того, чтобы соперник сделал ход, Ваша программа должна вызвать функцию OppMove. Она возвратит символ 'U', 'D', 'L' или 'R', в зависимости от того, какую строку или столбец стер Ваш соперник. По окончании игры вызовите функцию EndGame.
Пример игры:
TASK3A.DAT:
2 5
1 3 -9 1 -7
-2 4 -5 6 -3
Ход игры:
Начало игры.
1-й игрок стер крайнюю нижнюю строку.
2-й игрок стер крайний левый столбец.
1-й игрок стер крайний левый столбец.
2-й игрок стер крайний правый столбец.
1-й игрок стер крайний правый столбец.
2-й игрок стер крайнюю верхнюю строку.
1-й игрок выйграл!
Конец игры.
Дополнительные файлы к условию задачи:
PLAY3A.PAS
PLAY3A.H
PLAY3A.C
PLAY3A.CPP
Максимальное количество баллов: 40


Задача 3A: PLAY3A.PAS
Unit Play3A;
Interface
Procedure BeginGame (P : Integer);
Procedure EndGame;
Procedure Move (J : Char);
Function OppMove : Char;
Implementation
Const
MaxN = 10;
S : Integer = 0;
Var
P, R, C, M, N : Integer; K : Char;
Tbl : Array [1..MaxN, 1..MaxN] Of Integer;
Cnt1, Cnt2 : Integer;
Procedure Error;
Begin
WriteLn ('Нарушены правила игры!');
Halt (1);
End;
Procedure MakeMove (Ch : Char; P : Integer; Var Cnt : Integer);
Var
K : Integer;
Begin
Case Ch Of
'L': Begin
For K := 0 To M-1 Do Cnt := Cnt + Tbl[R+K,C];
C := C + 1; N := N - 1;
WriteLn (P, '-й игрок стер крайний левый столбец.');
End;
'R': Begin
For K := 0 To M-1 Do Cnt := Cnt + Tbl[R+K,C+N-1];
N := N - 1;
WriteLn (P, '-й игрок стер крайний правый столбец.');
End;
'U': Begin
For K := 0 To N-1 Do Cnt := Cnt + Tbl[R,C+K];
R := R + 1; M := M - 1;
WriteLn (P, '-й игрок стер крайнюю верхнюю строку.');
End;
'D': Begin
For K := 0 To N-1 Do Cnt := Cnt + Tbl[R+M-1,C+K];
M := M - 1;
WriteLn (P, '-й игрок стер крайнюю нижнюю строку.');
End
Else Error;
End;
End;
Procedure BeginGame (P : Integer);
Var
F : Text;
I, J : Integer;
Begin
If S <> 0 Then Error;
If (P <> 1) And (P <> 2) Then Error;
Play3A.P := P; S := P;
Assign (F, 'TASK3A.DAT'); ReSet (F);
Read (F, M, N);
R := 1; C := 1; K := 'L';
Cnt1 := 0; Cnt2 := 0;
For I := 1 To M Do
For J := 1 To N Do
Read (F, Tbl[I,J]);
Close (F);
WriteLn ('Начало игры.');
WriteLn ('Ваша программа играет за ', P, '-го игрока.');
End;
Procedure Move (J : Char);
Begin
If S <> 1 Then Error;
MakeMove (J, P, Cnt1);
If (M > 0) And (N > 0) Then S := 2 Else S := 3;
End;
Function OppMove : Char;
Begin
If S <> 2 Then Error;
MakeMove (K, 3-P, Cnt2);
OppMove := K;
Case K Of
'L': K := 'R';
'R': K := 'U';
'U': K := 'D';
'D': K := 'L';
End;
If (M > 0) And (N > 0) Then S := 1 Else S := 3;
End;
Procedure EndGame;
Begin
If S <> 3 Then Error;
S := 4;
If Cnt1 > Cnt2
Then WriteLn (P, '-ый игрок выйграл!')
Else WriteLn (3-P, '-ый игрок выйграл!');
WriteLn ('Конец игры.');
End;
End.

Задача 3A: PLAY3A.H
void BeginGame (int q);
void EndGame (void);
void Move (char j);
char OppMove (void);


Задача 3A: PLAY3A.C/PLAY3A.CPP
#include <stdlib.h>
#include <stdio.h>
#include "play3a.h"
#define maxn 10
static int s = 0;
static int p, r, c, m, n;
static char k;
static int tbl[maxn][maxn];
static int cnt1, cnt2;
static void Error (void)
{
printf ("Нарушены правила игры! ");
exit (EXIT_FAILURE);
}
static void makemove (char ch, int p, int * cnt)
{
int k;
switch (ch)
{
case 'L': for (k = 0; k < m; k ++) (* cnt) += tbl[r+k][c];
printf ("%d-й игрок стер крайний левый столбец. ", p);
c ++; n --; break;
case 'R': for (k = 0; k < m; k ++) (* cnt) += tbl[r+k][c+n-1];
printf ("%d-й игрок стер крайний правый столбец. ", p);
n --; break;
case 'U': for (k = 0; k < n; k ++) (* cnt) += tbl[r][c+k];
printf ("%d-й игрок стер крайнюю верхнюю строку. ", p);
r ++; m --; break;
case 'D': for (k = 0; k < n; k ++) (* cnt) += tbl[r+m-1][c+k];
printf ("%d-й игрок стер крайнюю нижнюю строку. ", p);
m --; break;
default: Error ();
}
}
void BeginGame (int q)
{
FILE * f;
int i, j;
if (s != 0) Error ();
if (q != 1 && q != 2) Error ();
p = q; s = q;
f = fopen ("task3a.dat", "r");
fscanf (f, "%d%d", & m, & n);
r = 0; c = 0; k = 'L';
cnt1 = 0; cnt2 = 0;
for (i = 0; i < m; i ++)
for (j = 0; j < n; j ++)
fscanf (f, "%d", & (tbl[i][j]));
fclose(f);
printf ("Начало игры. ");
printf ("Ваша программа играет за %d-го игрока. ", p);
}
void Move (char j)
{
if (s != 1) Error ();
makemove (j, p, & cnt1);
s = (m > 0 && n > 0) ? 2 : 3;
}
char OppMove (void)
{
char j = k;
if (s != 2) Error ();
makemove (k, 3-p, & cnt2);
switch (k)
{
case 'L': k = 'R'; break;
case 'R': k = 'U'; break;
case 'U': k = 'D'; break;
case 'D': k = 'L'; break;
}
s = (m > 0 && n > 0) ? 1 : 3;
return j;
}
void EndGame (void)
{
if (s != 3) Error ();
s = 4;
printf ("%d-й игрок выйграл! ", (cnt1 > cnt2) ? p : (3-p));
printf ("Конец игры. ");
}

Задача 3B

"Прямоугольники"

Прямоугольник во многих психологических тестах характеризует ординарность мышления. Мы считаем, что оттенок пренебрежения по отношению к прямоугольникам совершенно неуместен. Надеемся, что Вы согласитесь с нами, решая эту задачу.
Дано N прямоугольников на плоскости со сторонами, параллельными осям координат. Определите площадь части плоскости, покрытой прямоугольниками.
Ваша программа должна считать исходные данные из файла TASK3B.DAT. В первой строке этого файла находится число N -количество прямоугольников (1<=N<=10). В каждой i-ой из последующих N строк находятся четыре действительных числа XAi, YAi, XBi и YBi - координаты левой нижней и правой верхней вершины i-го прямоугольника (-1000.0<XAi,YAi, XBi,YBi<1000.0). Ваша программа должна решить задачу и записать найденную площадь в файл TASK3B.SOL с точностью до 0.01.
Примеры входных и выходных данных:
TASK3B.DAT:
4
2.0 2.0 5.0 7.0
6.0 4.0 9.0 7.0
-1.0 3.0 5.0 5.0
7.0 5.0 8.0 6.0
TASK3B.SOL:
30.00
Максимальное количество баллов: 30

Задача 3C

"Черное и белое"
В этой задаче Вы будете менять местами белые и черные фишки. На доске размером (2N+1)x(2N+1) расположены фишки белого и черного цвета, как показано на рисунке. Фишки можно перемещать по следующим правилам. Если клетка рядом с фишкой свободна, то фишку можно передвинуть на эту клетку. Если рядом с фишкой стоит фишка другого цвета, а следующая за ней свободна, то ее можно переместить на свободную клетку. При этом фишки белого цвета могут двигаться только слева направо или сверху вниз, а фишки черного цвета - справа налево или снизу вверх. Напишите программу, которая поменяет белые и черные фишки местами.
Рисунок:
wwwwbbb
wwwwwbbb
wwwwbbb
www_bbb w - белая фишка
wwwbbbb b - черная фишка
wwwbbbb _ - свободная клетка
wwwbbbb
Ваша программа должна считать число N из файла TASK3C.DAT (1<=N<=10).
Ваша программа должна решить задачу и записать в первую строку файла TASK3C.SOL количество перемещений фишек. В последующих строках должно быть записано положение (номер строки и столбца) свободной клетки после очередного перемещения.
Примеры входных и выходных данных:
TASK3C.DAT:
1
TASK3C.SOL:
12
1 2
1 1
1 3
1 2
3 2
3 1
3 3
3 2
2 2
2 1
2 3
2 2
Максимальное количество баллов: 40

Задача 3D

"Ступеньки"


Если Вы живете на девятом этаже, а лифт в вашем доме работает не всегда, то эта задача покажется Вам знакомой. Сколькими различными способами поклонник здорового образа жизни может спуститься по лестнице, состоящей из N ступенек, если он может шагать по ней или перепрыгивать через 1, 2, ..., P ступенек.
Ваша программа должна считать исходные данные из файла TASK3D.DAT. В первой строке этого файла находится число N, во второй - число P. Числа N и P - целые, (1<=N<=30,1<=P<=5).
Ваша программа должна решить задачу и записать полученное число в файл TASK3D.SOL.
Примеры входных и выходных данных:
TASK3D.DAT:
4
2
TASK3D.SOL:
7
Максимальное количество баллов: 20


Задача 3Е

"Парламент"
Решение этой задачи поможет уменьшить число случаев рукоприкладства в нашем Верховном Совете. В парламенте у каждого его члена не более трех врагов. Выясните, можно ли разбить парламент на две палаты так, чтобы у каждого парламентария в одной с ним палате было бы не более одного врага.
Ваша программа должна считать исходные данные из файла TASK3E.DAT. В первой строке этого файла находится целое число N - количество членов парламента (1<N<100). Во второй строке - целое число M - количество пар врагов. В следующих M строках перечислены пары врагов Ai, Bi, где Ai, Bi - порядковые номера парламентариев (1<=Ai,Bi<=N). Если разбиение парламента возможно, то Ваша программа должна записать в первой строке файла TASK3E.SOL количествочленов первой палаты, а последующих строках - номера членов первой палаты. Если разбить парламент на две палаты невозможно, запишите в первой строке файла число -1. Примеры входных и выходных данных:
TASK3E.DAT:
6
9
1 2
1 4
1 6
2 3
2 5
3 4
3 5
4 6
5 6
TASK3E.SOL:
3
2
3
6
Максимальное количество баллов: 40

 

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

28 декабря1998 года Пасихов


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