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

@DanUnited · Регистрация: 06.01.2009

Студворк — интернет-сервис помощи студентам

Привет всем))

----------------------------------------------
Есть задача, которую не смог решить, представлена на зональной олимпиаде.
Бррр.... про вирусы:
---------------------
Итак, имеется матрица, типа клеток N[499] А точнее N<500;
А также есть вирусы, массив вирусов M; M<11.
За 1 единицу времени заражаются соседние клетки с заражёнными, т.е. те, которые имеют общую сторону уже с заражёнными клетками))
Сначала вводится кол-во элементов матрицы N, после кол-во вирусов.
Далее вводятся построчно координаты каждого вируса.
X1Y1
X2Y2
X3Y#
и так далее....
-------------------------
Программа должна выводить кол-во единиц времени, за которое все клетки полностью заразятся.
Заранее спасибо, DanUnited)))

@DannerDOS · 28.08.2009, 00:25

Lolcht0 Да верно алгоритм во много быстрее чем прямолинейный перебор, но сам алгоритм всем известен, сам нераз это применял на практике...

@Lolcht0 · 28.08.2009, 00:27

я и не говорил, что изобрел что-то новое)) вот взял бы и применил, что тебя останавливало?

@odip · 28.08.2009, 00:28

Ты забыл еще про массив клеток.
И потом N можно не записывать в очередь.
Можно просто запоминать где последний элемент в очереди.
Как перешли через последний - значит нужно увеличивать N.

Еще можно считать число незанятых вирусом клеток - FREE.
Тогда проверка что все клетки заняты вирусом будет выполняться за 1 действие.
Занятие клеток произойдет немного раньше чем будет пуста очередь.

Добавлено через 50 секунд
Вообщем алгоритм понятен - осталось написать

@Lolcht0 · 28.08.2009, 00:32

не спорю, просто я постарался сделать попроще, все эти улучшения уже минорны по сравнением с переходом к такому алгоритму от чистого перебора.

@lexus_ilia · 28.08.2009, 01:15

Сообщение от Puporev

поэтому нужна динамика

Хотелось бы уточнить, а то может показаться, что использование динамических массивов Вам поможет - это не так, Вам следует использовать Динамические структуры, а вот какую именно - решать Вам, но скорее всего это будет список (односвязный, двусвязный).

Добавлено через 25 минут
Хотелось бы исправить себя, использование списков не особо Вам поможет, т.к. такого "длинного" списка Вам не создать, так что думаю следует использовать такую структуру как массив списков, представляющих собой матрицу.

@Lolcht0 · 28.08.2009, 01:18

и чем ЭТО ВСЕ лучше обычного двумерного массива? если так хочется уложиться в 64к - понимать каждый бит как отдельную клетку. тогда нужен массив размером 512/8 = 64 на 500. итого укладываемся в 32к.

@lexus_ilia · 28.08.2009, 01:40

Lolcht0, Вы бы прежде чем писать о том, что всё получается попробовали бы в tp7 объявить массив максимально допустимой ,по задаче, размерности (499*499).
Пробуйте компилировать:

Pascal
1
2
3
4
5
6
7
Type
  mas:array [1..499,1..499] of byte;
var
  Matr:mas;
 
begin
end.

Добавлено через 2 минуты
И да, о том что я писал раньше - это не подойдёт (ну про массив списков), они же всё равно хранятся в пределах 64К...

Evg · 28.08.2009, 09:40

lexus_ilia, в свою очередь могу предложить тебе внимательно прочитать то, что написал Lolcht0. Не массив 512x512, а 512x64, что уже занимает 32к

@lexus_ilia · 28.08.2009, 10:45

Сообщение от Evg

внимательно прочитать то, что написал Lolcht0

Соглашусь, поздновато было, не заметил.

@Somebody · 28.08.2009, 11:55

Ещё идея. Учитывая малое количество вирусов, можно посчитать максимум из расстояний от каждого вируса до углов и половины расстояний от каждого вируса до каждого (r = dx + dy).

Evg · 28.08.2009, 11:56

Сообщение от Somebody

Ещё идея. Учитывая малое количество вирусов, можно посчитать максимум из расстояний от каждого вируса до углов и половины расстояний от каждого вируса до каждого (r = dx + dy).

Так вирусы ж не обязательно прямоугольные

@odip · 28.08.2009, 12:07

Не так - нужно взять - минимальное кол-во шагов (расстояние нельзя мерить из-за нелинейного распространения):
1) от каждого угла до любого вируса
2) от каждого вируса до каждого другого - но тут поделить на 2, причем с округлением вверх.
Потом из этого набора всех шагов выбрать максимально длинный шаг.
Это и будет число искомое число N.
Только тут очень важно в формулах не ошибиться - +1, -1

@Lolcht0 · 28.08.2009, 12:16

что значит !"до каждого другого"?
например, есть

Code
1
2
3
4
5
6
 12345
1xxxxx
2x000x
3x000x
4x000x
5xxxxx

х - зараженные
0 - здоровые

что тут понимать под каждым другим?

@Somebody · 28.08.2009, 12:22

Сообщение от Evg

Так вирусы ж не обязательно прямоугольные

В смысле? r = dx + dy даёт количество шагов, они же вроде квадратом распространяются.

Code
1
2
3
4
5
00000 00000 00100
00000 00100 01110
00100 01110 11111
00000 00100 01110
00000 00000 00100

Evg · 28.08.2009, 12:31

Ёперный театр.... я думал, что вирус изначально необязательно точечный. Т.е начально положение может быть

Правда в задаче про это ничегоне сказано

@odip · 28.08.2009, 12:32

В массиве M лежат вирусы. Нужно мерить от M[i] до M[j], где 1<=i<j<=кол_во_вирусов.
От себя до себя бессмысленно мерить.
Если померяли от 3 до 5, то от 5 до 3 тоже нет смысла мерить.
Матрица расстояний между вирусами - симметричная.

@Lolcht0 · 28.08.2009, 12:41

ну, хорошо, выше я не учел малости вирусов.

предположим, что у нас 8 вирусов, расставленных по периметру матрицы - в углах, и на середине каждой стороны. максимальное расстояние ~sqrt(500^2+500^2)~700. пополам - 350. а логика мне подсказывает, что ответ должен быть - 250

@DanUnited · 28.08.2009, 12:50 **[ТС]**

Сообщение от Lolcht0

ну, хорошо, выше я не учел малости вирусов.

предположим, что у нас 8 вирусов, расставленных по периметру матрицы - в углах, и на середине каждой стороны. максимальное расстояние ~sqrt(500^2+500^2)~700. пополам - 350. а логика мне подсказывает, что ответ должен быть - 250

Вот только ещё сложнее то, что вирусы расставляешь не ты, а тот кто тестирует программу. Надо в программе указать все варианты размещения вируса: в углу, в серединте, по краям. Вроде бы только 3 варианта.Это только расположение....

@odip · 28.08.2009, 12:58

Да - алгоритм неправильный.
Грубо говоря задача сводится - к такой:
Рисуем M откружностей диаметра T c центрами в вирусах.
Задача - покрыть этими откружностями все поле.
Причем диаметр этих отружностей должен быть минимальным.

Добавлено через 4 минуты
Думаю если учесть все ньюансы то и получится изначальный алгоритм заполнения поля

@Somebody · 28.08.2009, 12:59

Текущий вариант:
Расстоянием будем считать dx + dy. Надо найти максимум из:
# для каждой пары вирусов: половины расстояний между ними;
# для каждой точки на границе: минимума расстояний от каждого вируса до этой точки;
# то же для каждой середины стороны;
# (возможно, ещё что-то?).
Нехороший тест:

Новые блоги и статьи Все статьи Все блоги /
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .	Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .

@DanUnited Программист TH 292 / 147 / 12 Регистрация: 06.01.2009 Сообщений: 537

	Олимпиадная задача про вирусы. 27.08.2009, 19:23. Показов 12748. Ответов 47 Метки нет (Все метки) Привет всем)) ---------------------------------------------- Есть задача, которую не смог решить, представлена на зональной олимпиаде. Бррр.... про вирусы: --------------------- Итак, имеется матрица, типа клеток N[499] А точнее N<500; А также есть вирусы, массив вирусов M; M<11. За 1 единицу времени заражаются соседние клетки с заражёнными, т.е. те, которые имеют общую сторону уже с заражёнными клетками)) Сначала вводится кол-во элементов матрицы N, после кол-во вирусов. Далее вводятся построчно координаты каждого вируса. X1Y1 X2Y2 X3Y# и так далее.... ------------------------- Программа должна выводить кол-во единиц времени, за которое все клетки полностью заразятся. Заранее спасибо, DanUnited))) 0

@DannerDOS Programmer 40 / 40 / 6 Регистрация: 07.04.2009 Сообщений: 187
	28.08.2009, 00:25
	Lolcht0 Да верно алгоритм во много быстрее чем прямолинейный перебор, но сам алгоритм всем известен, сам нераз это применял на практике... 0

@Lolcht0 125 / 123 / 0 Регистрация: 30.03.2009 Сообщений: 766
	28.08.2009, 00:27
	я и не говорил, что изобрел что-то новое)) вот взял бы и применил, что тебя останавливало? 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	28.08.2009, 00:28
	Ты забыл еще про массив клеток. И потом N можно не записывать в очередь. Можно просто запоминать где последний элемент в очереди. Как перешли через последний - значит нужно увеличивать N. Еще можно считать число незанятых вирусом клеток - FREE. Тогда проверка что все клетки заняты вирусом будет выполняться за 1 действие. Занятие клеток произойдет немного раньше чем будет пуста очередь. Добавлено через 50 секунд Вообщем алгоритм понятен - осталось написать 0

@Lolcht0 125 / 123 / 0 Регистрация: 30.03.2009 Сообщений: 766
	28.08.2009, 00:32
	не спорю, просто я постарался сделать попроще, все эти улучшения уже минорны по сравнением с переходом к такому алгоритму от чистого перебора. 0

@Lolcht0 125 / 123 / 0 Регистрация: 30.03.2009 Сообщений: 766
	28.08.2009, 01:18
	и чем ЭТО ВСЕ лучше обычного двумерного массива? если так хочется уложиться в 64к - понимать каждый бит как отдельную клетку. тогда нужен массив размером 512/8 = 64 на 500. итого укладываемся в 32к. 0

Evg 21285 / 8310 / 637 Регистрация: 30.03.2009 Сообщений: 22,671 Записей в блоге: 30
	28.08.2009, 09:40
	lexus_ilia, в свою очередь могу предложить тебе внимательно прочитать то, что написал Lolcht0. Не массив 512x512, а 512x64, что уже занимает 32к 0

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	28.08.2009, 11:55
	Ещё идея. Учитывая малое количество вирусов, можно посчитать максимум из расстояний от каждого вируса до углов и половины расстояний от каждого вируса до каждого (r = dx + dy). 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	28.08.2009, 12:07
	Не так - нужно взять - минимальное кол-во шагов (расстояние нельзя мерить из-за нелинейного распространения): 1) от каждого угла до любого вируса 2) от каждого вируса до каждого другого - но тут поделить на 2, причем с округлением вверх. Потом из этого набора всех шагов выбрать максимально длинный шаг. Это и будет число искомое число N. Только тут очень важно в формулах не ошибиться - +1, -1 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	28.08.2009, 12:32
	В массиве M лежат вирусы. Нужно мерить от M[i] до M[j], где 1<=i<j<=кол_во_вирусов. От себя до себя бессмысленно мерить. Если померяли от 3 до 5, то от 5 до 3 тоже нет смысла мерить. Матрица расстояний между вирусами - симметричная. 0

@Lolcht0 125 / 123 / 0 Регистрация: 30.03.2009 Сообщений: 766
	28.08.2009, 12:41
	ну, хорошо, выше я не учел малости вирусов. предположим, что у нас 8 вирусов, расставленных по периметру матрицы - в углах, и на середине каждой стороны. максимальное расстояние ~sqrt(500^2+500^2)~700. пополам - 350. а логика мне подсказывает, что ответ должен быть - 250 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	28.08.2009, 12:58
	Да - алгоритм неправильный. Грубо говоря задача сводится - к такой: Рисуем M откружностей диаметра T c центрами в вирусах. Задача - покрыть этими откружностями все поле. Причем диаметр этих отружностей должен быть минимальным. Добавлено через 4 минуты Думаю если учесть все ньюансы то и получится изначальный алгоритм заполнения поля 0