Отправляет 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++

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

Поиск в ширину на примере задачи о лабиринте.

    Постановка задачи. Лабиринт задан таблицей n*m из символов. Символ '#' - означает стену, '.' - пустое пространство, 's' - начальную позицию, 'f' - конечную позицию. Игрок может находиться только в пустых клетках. Из клетки он может перемещаться в соседнюю по горизонтали или по вертикали, но не по диагонали. Требуется найти кратчайший путь из начальной клетки в конечную.

    Пример лабиринта и кратчайшего пути в нем (n=4, m=6): 


 ......       23456.   
s#.#..       1#.#7.
 .#.#..       .#.#8.
 ...#f.       ...#9.

    Решение. Для решения используется алгоритм поиска в ширину. Собственно, поиском в ширину его обычно называют, когда говорят про графовые алгоритмы. В задачах о лабиринтах его чаще называют волновым алгоритмом, или просто волной. 


// -------------------------------------------------------------------------
// lab - двухмерный массив, в котором хранится лабиринт
// n,m - количество строк и столбцов в массиве lab
// si,sj - начальная позиция
// fi,fj - конечная позиция

typedef struct point {int i, j;} point;

int di[4] = { -1, 0, 1,  0};
int dj[4] = {  0, 1, 0, -1};
int i,j;
int d[n][m];            // массив расстояний 
int head,tail;          // указатели очереди
point queue[n*m];       // очередь

// обнуляем массив расстояний
for (i = 0; i < n; i++)
   for (j = 0; j < m; j++)
      d[i][j] = 0;
d[si][sj] = 1;          // расстояние до начальной клетки равно 1 

// инициализируем очередь
head = tail = 0;
queue[tail].i = si;
queue[tail++].j = sj;   // заносим в очередь начальную клетку

while (head < tail)     // цикл пока очередь не пуста
{
   point p = queue[head++];          // берем следующую позицию из очереди
   for (int k = 0; k < 4; k++)       // цикл по соседним клеткам
   {
      point newp;
      newp.i = p.i + di[k];
      newp.j = p.j + dj[k];
      // проверяем, что такая клетка есть
      if (0 <= newp.i && newp.i < n && 0 <= newp.j && newp.j < m)
         // проверяем, что она свободна и ранее ее не посещали
         if (lab[newp.i][newp.j] != '#' && d[newp.i][newp.j] == 0)
         {
            d[newp.i][newp.j] = d[p.i][p.j] + 1;     // находим расстояние 
            queue[tail++] = newp;                    // заносим позицию в очередь
         }
   }
}

if (d[fi][fj]) 
   printf("расстояние = %d\n", d[fi][fj]);
else
   printf("нет ни одного пути");

// -------------------------------------------------------------------------

    Массив d используется для хранения расстояний от начальной клетки до каждой из остальных. Если d[i][j] = 0, то расстояние до клетки (i,j) еще неизвестно. Клетки обрабатываются в порядке увеличения расстояния. Для этого используется очередь. При обработке клетки в очередь заносятся все соседние с ней, расстояние до которых еще не известно. Причем расстояние до них устанавливается равным расстоянию до текущей клетки плюс один.

    Рассмотрим работу алгоритма на приведенном выше примере. Порядок занесения клеток в очередь будет следующий: (1,0), (0,0), (2,0), (0,1), (3,0), (0,2), (3,1), (0,3), (1,2), (3,2), (0,4), (2,2), (0,5), (1,4), (1,5), (2,4), (2,5), (3,4), (3,5).

    Значения элементов массива d: 


 ......     2 3 4 5 6 7 
s#.#..     1 0 5 0 7 8  
 .#.#..     2 0 6 0 8 9
 ...#f.     3 4 5 0 9 10

    Приведенный выше алгоритм находит только длину кратчайшего пути. Сам путь можно восстановить с конца с помощью массива d. Последней клеткой в пути будет (fi,fj). Предпоследняя клетка (i,j) - это одна из соседних с (fi,fj) клеток, для которой d[i][j] = d[fi][fj] - 1. Затем выбираем клетку, соседнюю с предпоследней, расстояние до которой равно d[fi][fj] - 2, и так далее, пока не дойдем до (si,sj).

Задача №5 "Лабиринт с минами" (7 баллов).

Входной файл: input.txt
Выходной файл: output.txt
Ограничение по времени: 1 сек. на тест
Ограничение по памяти: 1 Mb

Условие

     Шпиону требуется пробраться из одной клетки лабиринта в другую. У шпиона есть карта лабиринта, поэтому он всегда идет по кратчайшему пути. Если кратчайших путей несколько, то он с равной вероятностью может выбрать любой из них. В лабиринте размещено несколько мин. Шпион не знает, где они расположены. Известно только, что в начальной и конечной клетках мин нет. Если на пути, выбранном шпионом, есть хотя бы одна мина, то он погибнет. Требуется найти вероятность того, что он все же доберется из начальной клетки в конечную.

Формат входного файла

    В первой строке входного файла записаны два числа n и m, разделенные пробелом, - длина и ширина лабиринта (2 <= n, m <= 15). Далее идут n строк по m символов каждая - описание лабиринта. Символы означают следующее: '#' - стена, '.' - пустая клетка, 'm' - клетка с миной, 's' - начальная клетка, 'f' - конечная клетка. Гарантируется, что в лабиринте ровно одна начальная клетка и ровно одна конечная клетка. Гарантируется, что существует хотя бы один путь из начальной клетки в конечную. Из текущей клетки шпион может перемещаться в соседнюю с ней по горизонтали или вертикали, но не по диагонали.

Формат выходного файла

    В выходной файл вывести единственное вещественное число 0.0000 <= p <= 1.0000 (вероятность) с четырьмя знаками после десятичной точки. Округление производите по стандартным правилам. Если ответ хранится в переменной p типа double, то достаточно воспользоваться оператором printf("%.4lf\n", p).

Пример входного файла (input.txt)


5 8
m.#....f
 .m..###.
 ..#....m
#m#.###.
s.......

Пример выходного файла (output.txt)


0.2500

Комментарий

    Из четырех кратчайших путей мин нет только на одном. Вероятность равна 1/4.

Задача №6 "Бактерии" (8 баллов).

Входной файл: input.txt
Выходной файл: output.txt
Ограничение по времени: 2 сек. на тест
Ограничение по памяти: 1 Mb

Условие

    Ученые одного института недавно открыли новый вид бактерий. Им известна следующая информация об этих бактериях:

  • Бактерии живут в N отдельных колониях. Колонии пронумерованы от 0 до N-1.
  • Каждую секунду количество бактерий в каждой колонии может измениться. Некоторые из них могут умереть, родиться или даже переехать в другую колонию. Эти изменения проходят в соответствии с некоторыми известными законами. Существует M таких законов, и они используются последовательно в порядке, записанном учеными. (Если мы пронумеруем законы от 0 до M-1, то через S секунд после начала эксперимента сработает правило (S-1)%M.)
  • Каждый раз, когда K бактерий встречаются в одной колонии, они объединяются в новый организм и улетают. (Если 2K+5 бактерий встретились в одной колонии и K > 5, то K из них образуют организм, следующие K образуют организм и только 5 бактерий останутся в колонии.)

    Ваша задача - вычислить, сколько бактерий будет жить в каждой колонии через T секунд, если в начале эксперимента в каждой колонии было по одной бактерии.

Формат входного файла

     В первой строке входного файла содержатся три целых числа N, M и T, разделенные одиночными пробелами (2 <= N <= 20, 1 <= M <= 100, 1 <= T <= 2000000000). Вторая строка содержит одно целое число K (2 <= K <= 1000). Следующие M строк описывают правила, по которым живут бактерии. Каждой описание состоит из одной строки и ровно двух целых чисел, разделенных одним пробелом. Возможные описания и их значения приведены ниже.

  • die i 0

    • Все бактерии в i-й колонии умирают.
  • reproduce i k

    • Количество бактерий в i-й колонии увеличивается в k раз. (1 <= k <= 100)
  • copy i j

    • Количество бактерий в i-й колонии увеличивается на количество бактерий в j-й колонии.
  • teleport i j

    • Все бактерии из j-й колонии перемещаются в i-ю колонию.
  • swap i j

    • Обменивает бактерии между i-й и j-й колониями.
  • merry-go-round 0 0

    • Все бактерии из i-й колонии перемещаются в (i+1)-ю колонию (0 <= i < N-1) и все бактерии из (N-1)-й колонии перемещаются в 0-ю.

Формат выходного файла

     Для каждой колонии выведите одну строку с количеством бактерий, которые будут жить в этой колонии через T секунд.

Пример входного файла (input.txt)


8 6 11
7
reproduce 2 5
copy 4 2
die 1 0
merry-go-round 0 0
teleport 5 3
swap 0 2

Пример выходного файла (output.txt)


1
0
0
0
0
4
4
1

Комментарий

Секунда Преобразование Колонии
0-я1-я2-я3-я4-я5-я6-я7-я
начало  11111111
1-яreproduce 2 5 11511111
2-яcopy 4 2 11516111
3-яdie 1 0 10516111
4-яmerry-go-round 0 0 11051611
5-яteleport 5 3 11001411
6-яswap 0 2 01101411
7-яreproduce 2 5 01501411
8-яcopy 4 2 01506411
9-яdie 1 0 00506411
10-яmerry-go-round 0 0 10050641
11-яteleport 5 3 10000441

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

    На проверку принимаются решения, написанные на языке 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. Проверка решений осуществляется на наборе тестов, недоступных участникам. Решение считается принятым, если выдало верный ответ на каждом из тестов. Программа должна считывать данные из указанного в условии входного файла и выдавать результат в указанный в условии выходной файл. Она не должна работать с другими файлами или каталогами. Входной файл нельзя открывать для записи. При доступе к входному и выходному файлу вы должны предполагать, что они находятся в текущей директории. Не используйте консольный ввод или вывод.

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

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

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

В избранное