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

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

Новые блоги и статьи Все статьи Все блоги /
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .

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

	Олимпиадная задача про вирусы. 27.08.2009, 19:23. Показов 12707. Ответов 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 21282 / 8307 / 637 Регистрация: 30.03.2009 Сообщений: 22,668 Записей в блоге: 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