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

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

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

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

Олимпиадная задача про орехи
Белка Бонифатий собирается спрятать орехи в тайнике на зиму. Для сохранности...

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

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

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

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

47
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 13:11 41
Somebody, это уже перебор пошел! все тесты не угадаешь


odip, в твоей постановке это уже задача линейного программирования. решать ее надо симпликс-методом в общем случае
0
Somebody
2801 / 1612 / 251
Регистрация: 03.12.2007
Сообщений: 4,215
Завершенные тесты: 3
28.08.2009, 13:25 42
Вроде так: если вирусы где-то встретятся, то позже всего это произойдёт на границе поля. Так что надо перебрать 1998 клеток X 10 вирусов.
Код

Код
type
  TPoint = record
    x, y: Integer;
  end;

var
  f: Text;
  n, m, i, r, max: Integer;
  coords: array [1..499] of TPoint;

function MinTo(x, y: Integer): Integer;
var
  i, r, min: Integer;
begin
  min := MaxInt;
  for i := 1 to m do
    begin
      r := abs(coords[i].x - x) + abs(coords[i].y - y);
      if r < min then min := r;
    end;
  Result := min;
end;

begin
  Assign(f, 'input.txt');
  Reset(f);
  ReadLn(f, n, m);
  for i := 1 to m do
    with coords[i] do
      ReadLn(f, x, y);
  Close(f);
  max := 0;
  for i := 1 to n - 1 do
  begin
    r := MinTo(i, 1); if r > max then max := r;
  end;
  for i := 1 to n - 1 do
  begin
    r := MinTo(n, i); if r > max then max := r;
  end;
  for i := 1 to n - 1 do
  begin
    r := MinTo(i, n); if r > max then max := r;
  end;
  for i := 1 to n - 1 do
  begin
    r := MinTo(1, i); if r > max then max := r;
  end;
  Assign(f, 'output.txt');
  Rewrite(f);
  Write(f, max);
  Close(f);
end.
1
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 13:32 43
Цитата Сообщение от Somebody Посмотреть сообщение
если вирусы где-то встретятся, то позже всего это произойдёт на границе поля
как это? и почему это?
0
Somebody
2801 / 1612 / 251
Регистрация: 03.12.2007
Сообщений: 4,215
Завершенные тесты: 3
28.08.2009, 13:45 44
Цитата Сообщение от Lolcht0 Посмотреть сообщение
как это? и почему это?
Вообще-то действительно не так, не знаю, как при 10 вирусах, а в общем можно все границы ими заставить, и они встретятся в центре.
В общем в коде ещё
Код
  for i := 1 to m do
    for j := i + 1 to m do
    begin
      r := (abs(coords[i].x - coords[j].x) + abs(coords[i].y - coords[j].y)) div 2;
      if r > max then max := r;
    end;
если это не работает, то эту идею в топку.
0
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 14:01 45
я ж приводил пример при 8, когда встречаются в центре
0
mamedovvms
2919 / 840 / 324
Регистрация: 30.04.2009
Сообщений: 2,633
28.08.2009, 14:12 46
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
uses crt;
var a:array[1..2,1..12] of integer;
    i,j,k:integer;
    virusov:byte;
    razmernost:integer;
    maxm,min:integer;
function max(i,j:integer):integer;
begin
 if i>j then max:=i else max:=j;
end;
begin
 clrscr;
 writeln('Razmernost ');
 readln(razmernost);
 writeln('Kol-vo virusov ');
 readln(virusov);
 
 for k:=1 to virusov do
  begin
   writeln('i virusa ',k);
   readln(a[1,k]);
   writeln('j virusa ',k);
   readln(a[2,k]);
  end;
maxm:=0;
 for i:=1 to razmernost do
  for j:=1 to razmernost do
   begin
    min:=max(abs(i-a[1,1]),abs(j-a[2,1]));
    for k:=2 to virusov do
 
     begin
      if max(abs(i-a[1,k]),abs(j-a[2,k]))<min then min:=max(abs(i-a[1,k]),abs(j-a[2,k]));
     end;
 
   if min>maxm then maxm:=min;
 
 
   end;
 
writeln(maxm);
readln;
 
end.
Добавлено через 1 минуту
вроде проверил все работает, оценивать вам так что смотрите, решайте
1
odip
Эксперт С++
7162 / 3221 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
28.08.2009, 15:46 47
odip, в твоей постановке это уже задача линейного программирования. решать ее надо симпликс-методом в общем случае
Зато это похоже правильную постановку задачи.
Другие варианты - искать минимальное/максимальное расстояние до чего-либо не эквиваленты исходной задаче.
И потом окружности ведь не точечные, а с шагом по клеткам.

Максимальное расстояние T == 996 достигается если поставить один вирус в точку (1,1).
Крайний дальний угол - (499,499) будет достигнут на 996 шаге.

С окружностями решать непонятно как - надо думать.
Проще решить исходным вариантом
0
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 18:12 48
ну, я не говорю, что твой вариант постановки задачи - плохой! Он, наверное, даст самый быстрый алгоритм.
Я вот и говорю как решать - это задача minimax из класса задач линейного программирования. решается симпликс-методом.

а вот деталей я уже не помню, надо гуглить или полнимать мои лекции, хе хе
0
28.08.2009, 18:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2009, 18:12

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

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

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


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

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

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