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

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

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

     Решение основано, как вы догадались, на волне. В описанный ранее алгоритм необходимо добавить вычисление для каждой клетки количества кратчайших путей до нее и количества безопасных кратчайших путей. Под безопасным путей понимается путь без мин. Ответом к задаче является отношение числа безопасных путей до конечной клетки к общему числу путей. Как вычислить число путей до клетки? Это сумма количества путей до соседних с ней клеток, расстояние до которых на единицу меньше расстояния до данной клетки. Если в данной клетке расположена мина, то число безопасных путей до нее 0, иначе это сумма числа безопасных путей до соседних с ней клеток, расстояние до которых на единицу меньше.

     Есть другой вариант решения. Найти волной расстояние до каждой клетки. Затем перебором искать общее количество путей и количество безопасных путей из начальной клетки в конечную. Такой алгоритм не укладывается в ограничения по времени на 19 тесте. В нем на поле 15 на 15 начальная и конечная клетки расположены в двух противоположных угловых клетках.

     Текст программы: 


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  
  int n, m, si, sj, fi, fj, i, j;
  char lab[15][16];
  long total[15][15];      // для хранения числа путей в клетку
  long good[15][15];       // для хранения числа безопасных путей в клетку
  
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) scanf("%s", lab[i]);
  
  for (i = 0; i < n; i++)
     for (j = 0; j < m; j++)
        if (lab[i][j] == 's') si = i, sj = j;
        else if (lab[i][j] == 'f') fi = i, fj = j;
        
// ------------ ПОИСК В ШИРИНУ -------------------------------------
// 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 d[15][15];            // массив расстояний 
  int head,tail;          // указатели очереди
  point queue[15*15];       // очередь

// обнуляем массив расстояний
  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++];          // берем следующую позицию из очереди
     
// --- Дополнительный код добавлен сюда ----
// вычисление количества путей до текущей клетки p
     if (p.i == si && p.j == sj)
     {
        total[si][sj] = 1;
        good[si][sj]  = 1;
     }
     else
     {
      total[p.i][p.j] = 0;
      good[p.i][p.j] = 0;
        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 (d[newp.i][newp.j] == d[p.i][p.j] - 1)
           {
              total[p.i][p.j] += total[p.i + di[k]][p.j + dj[k]];
              good[p.i][p.j] += good[p.i + di[k]][p.j + dj[k]];
           }
        }
        if (lab[p.i][p.j] == 'm') 
           good[p.i][p.j] = 0;
     }
// -----------------------------------------     
     
     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;                    // заносим позицию в очередь
           }
     }
  }

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

  printf("%.4lf\n", (double)good[fi][fj] / total[fi][fj]);

  fclose(stdout);
  return 0;
}

Результаты по задаче №5 "Лабиринт с минами" (7 баллов).

НикРезультат
ak13_bodatime limit exceeded on test #19
aleksandrrtime limit exceeded on test #19
artitime limit exceeded on test #19
Berdanaccepted
DEathkNIghtSrun-time error on test #2
kandrwrong answer on test #7
kwamawrong answer on test #7
romchwrong answer on test #3
SadKo_Sobakatime limit exceeded on test #19
VOLANDwrong answer on test #7

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

     Большинство присланных программ решают задачу "в лоб". Они хранят массив из N элементов и проводят над ним T преобразований. Такое решение проходит лишь при малых значениях T. При T порядка миллиарда оно работает слишком медленно и не укладывается в ограничение по времени.

     На самом деле эта задача решается с помощью линейной алгебры. Представим состояние колоний в виде вектора-столбца из N элементов. Тогда каждое из преобразований можно представить как домножение данного вектора на некоторую матрицу размера N на N слева. Рассмотрим пример для N = 4. 


                                                        
die 2 0       reproduce 0 3   swap 1 3    merry-go-round 0 0                       
 
 |1 0 0 0|     |3 0 0 0|     |1 0 0 0|     |0 0 0 1|                                     
 |0 1 0 0|     |0 1 0 0|     |0 0 0 1|     |1 0 0 0|                                     
 |0 0 0 0|     |0 0 1 0|     |0 0 1 0|     |0 1 0 0|                                     
 |0 0 0 1|     |0 0 0 1|     |0 1 0 0|     |0 0 1 0|

     Пусть в четырех колониях следующее число бактерий: 3, 1, 2, 0. Применение правила merry-go-round соответствует следующему произведению: 



    |0 0 0 1|   |3|   |0|
    |1 0 0 0| * |1| = |3|
    |0 1 0 0|   |2|   |1|
    |0 0 1 0|   |0|   |2|

    Как использование матриц может ускорить вычисление? Обозначим матрицы, соответствующие M заданным преобразованиям, через P(0), P(1), ..., P(M-1). Начальный (единичный) вектор-столбец обозначим I. Тогда вектор-столбец после всех выполненных преобразований будет следующим: 

(P(0)*P(1)*...*P(M-1))*...*(P(0)*P(1)*...*P(M-1))*P(0)*P(1)*...*P(T%M-1)*I

     Если мы обозначим P(0)*P(1)*...*P(M-1) через Q, то получим: 

(Q^(T/M))*P(0)*P(1)*...*P(T%M-1)*I

    Вычисление матриц Q можно выполнить за M-1 операцию перемножения матриц. Сложность перемножения матриц N на N равна O(N^3), значит сложность вычисления Q есть O(M * N^3). Далее Q возводится в степень T/M. Эту операцию можно выполнить за время O(log(T/M) * N^3). И еще T%M перемножений матриц добавляет O(T%M * N^3). В итоге сложность алгоритма получается O(M * N^3 + log(T/M) * N^3 + T%M * N^3) = O(M * N^3).

     Заметим, что все вычисления производятся по модулю k. Никаких переполнений при вычислении заданных матриц возникнуть не должно. Полученную матрицу итогового преобразования необходимо умножить на единичный вектор-столбец. Полученный вектор-столбец и будет ответом.

     Текст программы: 


#include 
#include 
#include 

const int max_m = 100;
const int max_n = 20;

long n, k;        // все операции выполняются modulo k

class Matrix
{
public:
   int m[max_n][max_n];
   Matrix();
   Matrix(int diag);
   Matrix(char *rule, int r1, int r2);
   Matrix operator* (Matrix &M);
};

Matrix::Matrix()
{
   memset(m, 0, sizeof(m));
}

Matrix::Matrix(int diag)
{
   int i;
   memset(m, 0, sizeof(m));
   for (i = 0; i < n; i++) m[i][i] = diag;      
}

Matrix::Matrix(char *rule, int r1, int r2)
{
   int i;
   memset(m, 0, sizeof(m));
   for (i = 0; i < n; i++) m[i][i] = 1;         
   if (!strcmp(rule, "die")) 
      m[r1][r1] = 0;
   else if (!strcmp(rule, "reproduce"))
      m[r1][r1] = r2 % k;
   else if (!strcmp(rule, "copy"))
      m[r1][r2] = 1;
   else if (!strcmp(rule, "teleport"))
      m[r1][r2] = 1,
      m[r2][r2] = 0;
   else if (!strcmp(rule, "swap"))
      m[r1][r1] = m[r2][r2] = 0,
      m[r1][r2] = m[r2][r1] = 1;
   else if (!strcmp(rule, "merry-go-round"))
      for (i = 0; i < n; i++) 
         m[i][i] = 0,
         m[i][(i + (n-1)) % n] = 1;
}

Matrix Matrix::operator* (Matrix &M)
{
   int i, j, t;
   Matrix R(0);
   for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
      {
         R.m[i][j] = 0;
         for (t = 0; t < n; t++)
            R.m[i][j] += (*this).m[i][t] * M.m[t][j];
         R.m[i][j] %= k;
      }
   return R;
}

/*
Вычисление A в степени n.
При вычислении A^n используются правила:
  A^0      = E (единичная матрица)
  A^(2k)   = (A^k) * (A^k)
  A^(2k+1) = (A^k) * (A^k) * A;
Сложность операции возведения в степень получается 
  O(log(n) * (сложность умножения)) = O (log(n) * n^3)
*/
Matrix power(Matrix A, int n)
{
   Matrix R(1);
   if (n)
   {
      Matrix T;
      T = power(A, n / 2);
      if (n % 2 == 0)
         R = T * T;
      else
        R = T * T * A;
   }
   return R;
}

int main(int argc, char* argv[])
{
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
   
   long m, t, i, j;
   char rule[max_m][20];         // для хранения правил
   int r1[max_m], r2[max_m];     // параметры правил
   
// ввод данных   
   scanf("%d %d %d %d", &n, &m, &t, &k);
   for (i = 0; i < m; i++) 
      scanf("%s %d %d", rule[i], &r1[i], &r2[i]);
      
// находим произведения матриц всех преобразований
   Matrix M(1);
   for (i = 0; i < m; i++)
   {
      Matrix T(rule[i], r1[i], r2[i]);
      M = T * M;
   }
   M = power(M, t / m);
   
// учитываем "остаточные" преобразования
   for (i = 0; i < t % m; i++)
   {
      Matrix T(rule[i], r1[i], r2[i]);
      M = T * M;
   }
   
// выводим ответ - суммы строк матрицы   
   for (i = 0; i < n; i++)
   {
      int s = 0;
      for (j = 0; j < n; j++) s += M.m[i][j];
      s %= k;
      printf("%d\n", s);
   }
   
   fclose(stdout);
   return 0;
}

Результаты по задаче №6 "Бактерии" (8 баллов).

НикРезультат
ak13_bodatime limit on test #5
aleksandrrtime limit on test #5
artiaccepted
DEathkNIghtSaccepted
john_smithtime limit on test #5
kandraccepted
LamerOnLinetime limit on test #5
romchwrong answer on test #3
SadKo_Sobakatime limit on test #5
VOLANDtime limit on test #5

    Условия задач, тесты и решения вы всегда можете найти на сайте accepted.narod.ru.

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

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

В избранное