Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи и алгоритмы на C++

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Май 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Виктор Журавлев

Статистика

1.725 подписчиков
-1 за неделю
←   Все выпуски   →

Олимпиадные задачи и алгоритмы на C++


Информационный Канал Subscribe.Ru

Олимпиадные задачи и алгоритмы на C++

    Здравствуйте, уважаемые подписчики.

     В этом выпуске вновь нет теории, зато есть одна нестандартная и интересная задача.

Задача.

     Задача - написать программу, которая играет в игру "Морской бой". Правила этой игры были описаны в условии задачи №8. Напомню их.

     В игру "Морской бой" играют два человека. В начале игры каждый чертит на клеточном листе бумаги свое поле - квадрат с длиной стороны 10 клеток. Строки квадрата обозначаются латинскими буквами от a до j сверху вниз, столбцы - цифрами от 0 до 9 слева направо. Затем игрок расставляет на своем поле корабли: один 4-палубный, два 3-палубных, три 2-палубных и четыре 1-палубных. Корабль - это группа соседних клеток, образующих горизонтальную или вертикальную полоску. Количество палуб корабля - это количество клеток, из которых он состоит. Корабли могут соприкасаться со сторонами поля, но не могут касаться друг друга. Игроки не показывают друг другу свои поля. Примеры полей с расставленными кораблями ('.' - пусто, '#' - палуба): 


     №1               №2               №3               №4

  0123456789       0123456789       0123456789       0123456789
a .......###     a ....##....     a .#.....###     a ..........
b ..####....     b ..........     b #.........     b ..........
c #.........     c .##...#...     c ..#.###...     c .####.....
d #.#..##...     d ......#...     d ..........     d ..........
e #.#.......     e .#.#......     e ####......     e ##....##..
f ..........     f ...#...#..     f ..........     f ....#.....
g ......#...     g ...#......     g .#....#...     g .#..#.....
h ##.......#     h #..#...#.#     h .#....#...     h .#..#..#..
i ....#.....     i #.........     i ..........     i ..........
j .......#..     j #......###     j .#....##..     j ..#.#.#...

     В примерах №1 и №2 корабли расставлены правильно. В примере №3 корабли расставлены неверно, потому что два однопалубных корабля (a1 и b0) касаются друг друга. В примере №4 не хватает одного 3-палубного корабля.

     Первый игрок делает первый ход. Ход заключается в том, что игрок называет позицию на поле противника. Это клетка, в которую стреляет игрок. Причем по правилам он не может выстрелить в одну и ту же клетку дважды. Если эта клетка пуста, то противник говорит "мимо" и ход переходит к нему. В противном случае палуба корабля, расположенная в данной клетке, считается уничтоженной, и возможны два варианта. 1) Если все остальные палубы данного корабля были уничтожены раньше (или это 1-палубный корабль), то противник говорит "убит". 2) Если у корабля сохранилась хотя бы одна палуба, то противник говорит "ранен". В обоих случаях ход снова делает тот же игрок (т.е. он стреляет, пока не промахнется). Задача каждого игрока - уничтожить все корабли противника. Выигрывает тот, кто сделает это раньше.

     Единственное отличие наших правил будет в том, что строки, как и столбцы, обозначаются числами от 0 до 9, а не буквами 'a' - 'z'. Вам необходимо написать модуль на языке C++, используя следующий шаблон. 


//--------------------------------------------------
 ... подключение необходимых вам заголовочных файлов, например stdlib.h, string.h, vector ...

typedef char tfield[10][10];
typedef struct tmove
{ 
  int r, c;
  char result;
} tmove;

 ... описания ваших типов, переменных, функций и т.п. ...

void init(tfield &field)
{
 ... текст функции init ...
}

void makemove(char result, int m, tmove moves[], int &r, int &c)
{
 ... текст функции makemove ...
}
//--------------------------------------------------

    В вашем модуле не должно быть функции main. Функция init вызывается один раз в начале игры. Игрок должен заполнить массив field. Символ '.' соотвествует пустой клетке, '#' - палубе. На поле должны находиться один 4-палубный, два 3-палубных, три 2-палубных и четыре 1-однопалубных корабля.

    Функция makemove вызывается, когда игроку необходимо сделать ход. В переменной result содержится результат предыдущего хода: 'p' - мимо, 'w' - ранил, 'k' - убил. Если это первый ход данного игрока, то в result содержится ' ' (пробел). Переменная m содержит количество ходов противника, сделанных после предыдущего хода вашего игрока. Сами ходы содержатся в массиве moves, состоящем из m элементов типа tmove. Каждая структура tmove описывает один ход противника. r и c - строка и столбец, куда выстрелил противник. result - результат ('p', 'w' или 'k'). В переменные r и c вы должны занести номера строки и столбца клетки, в которую вы стреляете.

    Ниже приведен пример простейшей стратегии, где выстрелы производятся в случайные позиции. 


//--------------------------------------------------
#include <stdlib.h>
#include <string.h>

typedef char tfield[10][10];
typedef struct tmove
{ 
  int r, c;
  char result;
} tmove;

int a[10][10];

void init(tfield &field)
{
  int i, j;
  memset(a, 1, sizeof(a));
  srand(314159);
  strcpy(field[0], ".......###");
  strcpy(field[1], "..####....");
  strcpy(field[2], "#.........");
  strcpy(field[3], "#.#..##...");
  strcpy(field[4], "#.#.......");
  strcpy(field[5], "..........");
  strcpy(field[6], "......#...");
  strcpy(field[7], "##.......#");
  strcpy(field[8], "....#.....");
  strcpy(field[9], ".......#.");
  field[9][9]='.';
}

void makemove(char result, int m, tmove moves[], int &r, int &c)
{
  int i, j, k, n;
  k = 0;
  for (i = 0; i < 10; i++)
    for (j = 0; j < 10; j++)
      if (a[i][j]) k++;
  n = abs(rand() % k);
  for (i = 0; i < 10; i++)
    for (j = 0; j < 10; j++)
      if (a[i][j])
        if (n-- == 0)
        {
          r = i;
          c = j;
          a[r][c] = 0;
          return;
        }
}
//--------------------------------------------------

Тестирование

    Присланные программы будут сражаться друг с другом по принципу "каждый с каждым". Между каждой парой будет проведено две игры. В одной игре первым ходит один игрок, в другой - другой игрок. В каждой игре победитель получает один балл, проигравший - ноль баллов. В итоговом рейтинге игроки сортируются по уменьшению числа баллов.

     Ограничение по времени для каждого игрока - 10 секунд. Суммируются время работы функции init и всех вызовов makemove. Если в ходе игры один из игроков превысил ограничение по времени, то он считается проигравшим. Если игрок выполнил недопустимый ход, то он также проигрывает.

     Для данной задачи допускаются лишь модули, написанные на Microsoft Visual C++. Программа, которая облегчит вам тестирование своего модуля, будет в ближайшие несколько дней выложена на сайте accepted.narod.ru.

Оформление, отправка и проверка решений.

    На проверку принимаются решения, написанные на языке C++. Отправляйте свои письма по адресу accepted@narod.ru. Решение должно содержаться в одном файле, вложенном в ваше письмо. Для компиляции, по вашему выбору, будет использоваться программа bcc.exe (Borland C++ 3.1) или cl.exe (Microsoft Visual C++ 6.0). Размер исходного кода не должен превышать 40 Kb. Для каждой задачи отправляйте отдельное письмо. В теле письма укажите следующие данные (пример): 

ник (*): vasya
пароль (*): a193z458w2
фамилия: Иванов
имя: Василий
e-mail: vasya@hotmail.com
номер задачи (*): 1
компилятор (*): cl

    (*) обозначены обязательные для заполнения поля. Ник и пароль вы сами придумаете при отправке своего первого письма. В последующих письмах указывайте те же самые ник и пароль. Я пока не придумал, что делать, если два человека используют один и тот же ник. Так что, старайтесь придумать его так, чтобы никто до вас его еще не придумал :-) Если вы укажите свой e-mail, то с этой проблемой будет легче разобраться. В качестве компилятора укажите bcc или cl. И, главное, не забудьте указать номер задачи!

    При проверке решений, используются стандартные правила acm. Их можно найти, например, на сайте http://acm.baylor.edu. Проверка решений осуществляется на наборе тестов, недоступных участникам. Решение считается принятым, если выдало верный ответ на каждом из тестов. Программа должна считывать данные из указанного в условии входного файла и выдавать результат в указанный в условии выходной файл. Она не должна работать с другими файлами или каталогами. Входной файл нельзя открывать для записи. При доступе к входному и выходному файлу вы должны предполагать, что они находятся в текущей директории. Не используйте консольный ввод или вывод.

    Решения принимаются до субботы следующей недели (22 мая 2004) включительно. В воскресенье (23 мая 2004) будут высланы результаты тестирования и авторские решения.

Ведущий рассылкой: Виктор Журавлев
Вопросы, пожелания, предложения пишите на мой e-mail.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное