Форум программистов, компьютерный форум, киберфорум
Наши страницы
Free Pascal
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.95
DanUnited
Программист TH
290 / 145 / 12
Регистрация: 06.01.2009
Сообщений: 537
#1

Олимпиадная задача про вирусы. - Free Pascal

27.08.2009, 19:23. Просмотров 5710. Ответов 47
Метки нет (Все метки)

Привет всем))
----------------------------------------------
Есть задача, которую не смог решить, представлена на зональной олимпиаде.
Бррр.... про вирусы:
---------------------
Итак, имеется матрица, типа клеток N[499] А точнее N<500;
А также есть вирусы, массив вирусов M; M<11.
За 1 единицу времени заражаются соседние клетки с заражёнными, т.е. те, которые имеют общую сторону уже с заражёнными клетками))
Сначала вводится кол-во элементов матрицы N, после кол-во вирусов.
Далее вводятся построчно координаты каждого вируса.
X1Y1
X2Y2
X3Y#
и так далее....
-------------------------
Программа должна выводить кол-во единиц времени, за которое все клетки полностью заразятся.
Заранее спасибо, DanUnited)))
http://www.cyberforum.ru/free-pascal/thread1276697.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.08.2009, 19:23
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Олимпиадная задача про вирусы. (Free Pascal):

Олимпиадная задача
Обчислити суму N рядків трикутника Паскаля (1≤n≤100). Формат входных данных ...

Часы (олимпиадная задача)
Изобразить часы с двумя стрелками и цифрами для время, каждая из стрелок имеет...

Олимпиадная задача Приключение
Условие Теплым весенним днем группа из N школьников-программистов гуляла в...

Олимпиадная задача. 11 класс
Задача 1: Минимальное расстояние (10). Заранее спасибо! тексты заданий...

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

47
Evg
Эксперт CАвтор FAQ
18938 / 6899 / 513
Регистрация: 30.03.2009
Сообщений: 19,436
Записей в блоге: 30
27.08.2009, 19:34 #2
И в чём конкретно возникла сложность?
Кстати, что такое "зональная олимпиада"? Потому как задача выглядит чуть ли не школьной
0
TAVulator
3950 / 1109 / 160
Регистрация: 27.07.2009
Сообщений: 3,457
27.08.2009, 19:57 #3
Цитата Сообщение от DanUnited Посмотреть сообщение
имеется матрица, типа клеток N[499] А точнее N<500;
матрица одинарная (вектор) что ли?
или матрица квадратная? т.е. N(a) = N(sqrt(a),sqrt(a))?
0
DanUnited
Программист TH
290 / 145 / 12
Регистрация: 06.01.2009
Сообщений: 537
27.08.2009, 20:05  [ТС] #4
матрица квадратная
0
Puporev
Модератор
54135 / 41768 / 28876
Регистрация: 18.05.2008
Сообщений: 98,305
27.08.2009, 20:12 #5
Матрица конечно квадратная 500х500, поэтому нужна динамика, даже byte не влазит.
0
Lolcht0
123 / 121 / 1
Регистрация: 30.03.2009
Сообщений: 766
27.08.2009, 20:52 #6
куда byte не влазит? 224 кб - это вообще смешные цифры, если вы про размер памяти
0
Puporev
Модератор
54135 / 41768 / 28876
Регистрация: 18.05.2008
Сообщений: 98,305
27.08.2009, 20:55 #7
куда byte не влазит?
В 64 кб Турбо Паскаля.
0
Lolcht0
123 / 121 / 1
Регистрация: 30.03.2009
Сообщений: 766
27.08.2009, 21:13 #8
хм, об этом я как-то не подумал)) вроде бы, сейчас уже не tp там компилируют все это...
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,211
Завершенные тесты: 3
27.08.2009, 22:33 #9
Так можно по биту на клетку сделать.
0
Фенрир
42 / 38 / 12
Регистрация: 05.01.2009
Сообщений: 394
27.08.2009, 22:50 #10
на си когда писал если понадобится: (не оптимизированно - наспех)

C++
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
   #include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <time.h>
 
#define maxn 500
#define maxv 10
 
 void Init (state** kolony, int n); // в начале все клетки здоровы
  void Print (state** kolony, int n, int step, ostream& of); // запись в поток
  int Process (state** kolony, int n);
  void LoadFromFile (state** kol, int n);
  void Dialog (state** kol, int n);
  int Run (int n, int m, int mode);
  
 
 enum state {alive=0, killed}; // состояние клеток
 
   struct Cell {
      int x;
      int y;
     }; // структура клетка
     
   Cell* cInfectedCell; // указатель на массив зараженных клеток
   
    
    
    
     void Init (state** kolony, int n)// в начале все клетки здоровы
   {
  
      for (int i=0; i<n; i++)
      for (int j=0; j<n; j++)
        kolony[i][j]=alive;
    }
  
  
   void Print (state** kolony, int n, int step, ostream& of) // запись в поток
   {
      clrscr();
      of<<"Steps: "<<step<<endl;
      for (int i=0; i<n; i++)   {
      for (int j=0; j<n; j++)
        if(kolony[i][j]==alive) of<<"-";
        else of<<"+";
 
         of<<endl;
        }
   
      of<<endl<<endl;
   }
   
   
    
    int Process (state** kolony, int n) { // процесс
         int m=0; // число новых зараженных клеток
          int result=0; // остались ли живые клетки?
              
              for (int i=0; i<n; i++)
              for (int j=0; j<n; j++) {
                    if (kolony[i][j]==killed) // если данная клетка заражена
                     {
                          if (i-1>=0 && kolony[i-1][j]==alive) // заражаем живую клетку сверху
                              {
                              result=1;
                              cInfectedCell[m].x=i-1;
                              cInfectedCell[m++].y=j; // координаты новой зараженнйо клетки
                              }
                          
                           if (j-1>=0 && kolony[i][j-1]==alive) // заражаем живую клетку слева
                              {
                              result=1;
                              cInfectedCell[m].x=i;
                              cInfectedCell[m++].y=j-1; // координаты новой зараженнйо клетки
                              }    
                           
                           if (j+1<n && kolony[i][j+1]==alive) // заражаем живую клетку справа
                              {
                              result=1;
                              cInfectedCell[m].x=i;
                              cInfectedCell[m++].y=j+1; // координаты новой зараженнйо клетки
                              }   
                           
                            if (i+1<n && kolony[i+1][j]==alive) // заражаем живую клетку снизу
                              {
                              result=1;
                              cInfectedCell[m].x=i+1;
                              cInfectedCell[m++].y=j; // координаты новой зараженнйо клетки
                              }  
                     }
                 }
             
              for ( i=0; i<m; i++)  // вносим новые убитые клетки
                 kolony[cInfectedCell[i].x] [cInfectedCell[i].y]=killed;
              
                 return result;
            }
            
            
            
         
         
          void LoadFromFile (state** kol, int n) {
           ifstream in ("c:\\input.txt"); // открыть файл
                 int x, y; //координаты вируса
               if (!in) return;
                int num;
                char str[64];
                char s1[6];
                
            in>>num; // читаем число вирусов
                  for (int i=0; i<num; i++) {
                   in.getline(str, sizeof(str)); //читаем строку
                   char* p = strchr (str, ','); //разделяем в строке координаты
                   y= atoi (p+1); //из строки в число
                  strncpy(s1, str, strlen(str)-strlen(p));
                 x= atoi (s1);
                 kol[x][y]=killed; //zarajaem
                 } 
        }
          
          
             
           void Dialog (state** kol, int n) { // ввод числа вирусов и генерация координат
               int m, x;
                srand(time(0));
                
                clrscr();
                    do { // ввод числа вирусов
                cout<<"m=";
                cin>>m; 
                 }
                while (m<0 || m>maxv);
                
              for (int i=0; i<m; i++) {
              do {
                  x=rand()%n;
                           }
              while (kol[x][x]==killed); // если вирус уже всеелн в эту клетку то продолжаем генерировать
              kol[x][x]=killed;
                   }
             }
          
          
          int Run (int n, int m, int mode) {
              int steps=0;
           ofstream ofstr("c:\\rezult.txt");
               state**  kol  = new state* [n]; // матрица колонии
                 for (int i=0; i<n; i++)
                  kol[i]= new state[n];
                  
               Init(kol, n); // инициализация колонии
                  
              cInfectedCell= new  Cell [5*n]; // вспомогательный массив координат зараженный клеток
 
          if (mode==1)
           LoadFromFile (kol, n); // из файла
           else Dialog (kol, n); // из диалога
              
              
                do {
                 steps++;
         Print (kol, n ,steps, ofstr);
                 }
            while (Process(kol, n));
          return steps;
          
          }
          
          
          
          
          
      int main () {
        int n, m, mode;
        clrscr();
             
              do { // ввод размера колонии
                cout<<"n=";
                cin>>n;
              }
              while (n<0 || n>maxn);
              
              
              cout<<"1-Coordinates From File\n2-Coordinates From Dialog";
              cin>>mode;
 
         int steps=Run (n, m, mode); // число едениц времени
         
            cout<<"Kolonia zarazitsea za "<<steps<<" edenits vremeni"<<endl;
           cout<<"Sostoianie na kajdom etape smotrite v file rezult.txt"<<endl;
         
           getch();
                 
          
           
           delete  cInfectedCell; //очистка памяти
           return 0;
            }
Добавлено через 6 минут
хотя для олимпиады не пойдет
0
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
27.08.2009, 22:59 #11
В 64 кб Турбо Паскаля.
Надо полагать FPC не имеет таких глупых ограничений ?
0
Lolcht0
123 / 121 / 1
Регистрация: 30.03.2009
Сообщений: 766
27.08.2009, 23:30 #12
odip, не имеет. оно не глупое, оно досовское)) 64 кб - это размер сегмента. любой кусок данных целиком должен помещаться в 1 сегменте, вроде так...
Фенрир, дело даже не в памяти, дело в том, что алгоритм плохой...
0
DannerDOS
Programmer
39 / 39 / 6
Регистрация: 07.04.2009
Сообщений: 187
27.08.2009, 23:57 #13
Люди, поработайте не много над следующим кодом, и засунте туда GetTime(...) и Delay(...) :

Pascal
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
Program ViRus;
Uses crt;
Type
  TMasEll = Array [0..100, 0..100] of Byte; //Здесь в любое время можно изменить размерность, об этом пока бесапокоиться не стоит
Var
  MasEll : TMasEll; //Рассматриваемый массив ячеек
{Если ячейка равна 0 тогда нет вируса, если же равна 1 тогда данная ячейка занята вирусом}
  v : Integer; //Осторожно - вирус!
  n, m : Integer; //Колличество строк и столбцов
  v_i, v_j : Integer; //Координаты вирусов
  i, j : Integer; //Счетчики
 
{Функция проверки последовательности ячеек занимаемых вирусами} 
Function Nork (MasEll : TMasEll; n, m : Integer) : Boolean;
  var
    i, j, k : Integer;
  begin
    k := 0;
    For i := 1 to n do
      For j := 1 to m do begin
        If MasEll[i, j] = 1 then Inc(k);
      end;
    If k = n * m then Nork := True
    else Nork := False;
  end;
  
Begin
  clrscr;
  Write('Введите колличество строк = ');
    Readln(n);
  Write('Введите колличество столбцов = ');
    Readln(m);
  Write('Введите колличество вирусов = ');
    Readln(v);
  For i := 1 to v do begin
    Writeln('Введите координаты ', i, 'го вируса: ');
      Write('Введите X = ');
        Readln(v_i);
      Write('Введите Y = ');
        Readln(v_j);
    MasEll[v_i, v_j] := 1;
  end;
 i := 0; j := 1;
 Repeat
   For i := 1 to n do
     For j := 1 to m do begin
       If MasEll[i, j] = 1 then begin
         MasEll[i - 1, j] := 1;
         MasEll[i, j + 1] := 1;
         MasEll[i + 1, j] := 1;
         MasEll[i - 1, j - 1] := 1;
       end;
     end;
   Nork (MasEll, n, m);
 Until Nork (MasEll, n, m) <> True;
If Nork (MasEll, n, m) = True then Writeln('Ячейки заполнены вирусами');
End.
Я спать пошол, не могу...
0
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
28.08.2009, 00:02 #14
оно не глупое, оно досовское)) 64 кб - это размер сегмента. любой кусок данных целиком должен помещаться в 1 сегменте, вроде так...
То есть DOS больше 64Kb использовать не может ?

Добавлено через 2 минуты
представлена на зональной олимпиаде
А что это за олимпиада, на которой такие тривиальные задачи дают ?
0
Lolcht0
123 / 121 / 1
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 00:08 #15
odip, ну, читай внимательнее - где написано, что не может?

и да, ты, в смысле, знаешь более быстрый алгоритм? я придумал чуточку пошустрее, чем тупой перебор, но думаю, должны быть еще более шустрые
0
Evg
Эксперт CАвтор FAQ
18938 / 6899 / 513
Регистрация: 30.03.2009
Сообщений: 19,436
Записей в блоге: 30
28.08.2009, 00:09 #16
Цитата Сообщение от odip Посмотреть сообщение
То есть DOS больше 64Kb использовать не может ?
Это скорее ограничение 16-битного приложения. Все указатели как и вся адресация являются near-указателями. А динамическая память - уже far-указатели
0
DannerDOS
Programmer
39 / 39 / 6
Регистрация: 07.04.2009
Сообщений: 187
28.08.2009, 00:12 #17
Автору необходимо решить поставленную ему задачу, а не придумывать фундаментальные алгоритмы... Пусть сначало решит а потом повозиться над совершенствованием алгоритма...
0
odip
Эксперт С++
7161 / 3219 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
28.08.2009, 00:14 #18
я придумал чуточку пошустрее, чем тупой перебор
Ну так давай его сюда быстрее, а то в посте #13 как-то все тускло и багов полно
0
DannerDOS
Programmer
39 / 39 / 6
Регистрация: 07.04.2009
Сообщений: 187
28.08.2009, 00:17 #19
Цитата Сообщение от odip Посмотреть сообщение
Ну так давай его сюда быстрее, а то в посте #13 как-то все тускло и багов полно
Багов немеренно! Просто с ходу примерчик написал... Особо не задумываясь... Поэтому и говарю поработайте!
0
Lolcht0
123 / 121 / 1
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 00:19 #20
не буду писать код.

смысл такой. создаем структуру (X,Y,N)
X,Y - координаты зараженной клетки, N - момент времени

создаем очередь из этих структур. Вначале записываем в очередь координаты вирусов. N=0

теперь - \


пока очередь не пуста

читаем элемент
запоминаем N.
смотрим соседние с элементом клетки. Если не заражены - добавляем в очередь, увеличивая N на 1. upd:и помечаем эти клетки, как зараженные

ответ - последнее запомненное N

таким образом, если вначале у нас 1 вирус, мы анализируем всего 4 клетки вместо 250 000. и так далее
0
28.08.2009, 00:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2009, 00:19
Привет! Вот еще темы с решениями:

Олимпиадная задача
Условие: http://i.imm.io/1m1cH.jpeg Примеры вывода: http://i.imm.io/1m1cL.png...

Олимпиадная задача
На вход в файле INPUT.TXT подаётся две строчки: N - количество томов(максимум...

Олимпиадная задача Pascal
Пришел недавно с олимпиады . Все решил , последняя задача никак не дается . Кто...

Олимпиадная задача с кубиками
Не могли бы вы мне помочь? Юный математике Матвей интересуется теорией...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru