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

@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. Надо найти максимум из:
# для каждой пары вирусов: половины расстояний между ними;
# для каждой точки на границе: минимума расстояний от каждого вируса до этой точки;
# то же для каждой середины стороны;
# (возможно, ещё что-то?).
Нехороший тест:

Новые блоги и статьи Все статьи Все блоги /
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

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

	Олимпиадная задача про вирусы. 27.08.2009, 19:23. Показов 12785. Ответов 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