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

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

27.08.2009, 19:23. Просмотров 5787. Ответов 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
DannerDOS
Programmer
39 / 39 / 6
Регистрация: 07.04.2009
Сообщений: 187
28.08.2009, 00:25 #21
Lolcht0 Да верно алгоритм во много быстрее чем прямолинейный перебор, но сам алгоритм всем известен, сам нераз это применял на практике...
0
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 00:27 #22
я и не говорил, что изобрел что-то новое)) вот взял бы и применил, что тебя останавливало?
0
odip
Эксперт С++
7161 / 3220 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
28.08.2009, 00:28 #23
Ты забыл еще про массив клеток.
И потом N можно не записывать в очередь.
Можно просто запоминать где последний элемент в очереди.
Как перешли через последний - значит нужно увеличивать N.

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

Добавлено через 50 секунд
Вообщем алгоритм понятен - осталось написать
0
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 00:32 #24
не спорю, просто я постарался сделать попроще, все эти улучшения уже минорны по сравнением с переходом к такому алгоритму от чистого перебора.
0
lexus_ilia
3050 / 710 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
28.08.2009, 01:15 #25
Цитата Сообщение от Puporev Посмотреть сообщение
поэтому нужна динамика
Хотелось бы уточнить, а то может показаться, что использование динамических массивов Вам поможет - это не так, Вам следует использовать Динамические структуры, а вот какую именно - решать Вам, но скорее всего это будет список (односвязный, двусвязный).

Добавлено через 25 минут
Хотелось бы исправить себя, использование списков не особо Вам поможет, т.к. такого "длинного" списка Вам не создать, так что думаю следует использовать такую структуру как массив списков, представляющих собой матрицу.
0
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 01:18 #26
и чем ЭТО ВСЕ лучше обычного двумерного массива? если так хочется уложиться в 64к - понимать каждый бит как отдельную клетку. тогда нужен массив размером 512/8 = 64 на 500. итого укладываемся в 32к.
0
lexus_ilia
3050 / 710 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
28.08.2009, 01:40 #27
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К...
0
Evg
Эксперт CАвтор FAQ
19282 / 7139 / 528
Регистрация: 30.03.2009
Сообщений: 19,986
Записей в блоге: 30
28.08.2009, 09:40 #28
lexus_ilia, в свою очередь могу предложить тебе внимательно прочитать то, что написал Lolcht0. Не массив 512x512, а 512x64, что уже занимает 32к
0
lexus_ilia
3050 / 710 / 69
Регистрация: 24.09.2008
Сообщений: 1,531
28.08.2009, 10:45 #29
Цитата Сообщение от Evg Посмотреть сообщение
внимательно прочитать то, что написал Lolcht0
Соглашусь, поздновато было, не заметил.
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
28.08.2009, 11:55 #30
Ещё идея. Учитывая малое количество вирусов, можно посчитать максимум из расстояний от каждого вируса до углов и половины расстояний от каждого вируса до каждого (r = dx + dy).
0
Evg
Эксперт CАвтор FAQ
19282 / 7139 / 528
Регистрация: 30.03.2009
Сообщений: 19,986
Записей в блоге: 30
28.08.2009, 11:56 #31
Цитата Сообщение от Somebody Посмотреть сообщение
Ещё идея. Учитывая малое количество вирусов, можно посчитать максимум из расстояний от каждого вируса до углов и половины расстояний от каждого вируса до каждого (r = dx + dy).
Так вирусы ж не обязательно прямоугольные
0
odip
Эксперт С++
7161 / 3220 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
28.08.2009, 12:07 #32
Не так - нужно взять - минимальное кол-во шагов (расстояние нельзя мерить из-за нелинейного распространения):
1) от каждого угла до любого вируса
2) от каждого вируса до каждого другого - но тут поделить на 2, причем с округлением вверх.
Потом из этого набора всех шагов выбрать максимально длинный шаг.
Это и будет число искомое число N.
Только тут очень важно в формулах не ошибиться - +1, -1
0
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 12:16 #33
что значит !"до каждого другого"?
например, есть
Код
 12345
1xxxxx
2x000x
3x000x
4x000x
5xxxxx
х - зараженные
0 - здоровые


что тут понимать под каждым другим?
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
28.08.2009, 12:22 #34
Цитата Сообщение от Evg Посмотреть сообщение
Так вирусы ж не обязательно прямоугольные
В смысле? r = dx + dy даёт количество шагов, они же вроде квадратом распространяются.
Код
00000 00000 00100
00000 00100 01110
00100 01110 11111
00000 00100 01110
00000 00000 00100
0
Evg
Эксперт CАвтор FAQ
19282 / 7139 / 528
Регистрация: 30.03.2009
Сообщений: 19,986
Записей в блоге: 30
28.08.2009, 12:31 #35
Ёперный театр.... я думал, что вирус изначально необязательно точечный. Т.е начально положение может быть

Код
00000
00110
00100
00100
00000
Правда в задаче про это ничегоне сказано
0
odip
Эксперт С++
7161 / 3220 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
28.08.2009, 12:32 #36
В массиве M лежат вирусы. Нужно мерить от M[i] до M[j], где 1<=i<j<=кол_во_вирусов.
От себя до себя бессмысленно мерить.
Если померяли от 3 до 5, то от 5 до 3 тоже нет смысла мерить.
Матрица расстояний между вирусами - симметричная.
0
Lolcht0
123 / 121 / 0
Регистрация: 30.03.2009
Сообщений: 766
28.08.2009, 12:41 #37
ну, хорошо, выше я не учел малости вирусов.

предположим, что у нас 8 вирусов, расставленных по периметру матрицы - в углах, и на середине каждой стороны. максимальное расстояние ~sqrt(500^2+500^2)~700. пополам - 350. а логика мне подсказывает, что ответ должен быть - 250
0
DanUnited
Программист TH
290 / 145 / 12
Регистрация: 06.01.2009
Сообщений: 537
28.08.2009, 12:50  [ТС] #38
Цитата Сообщение от Lolcht0 Посмотреть сообщение
ну, хорошо, выше я не учел малости вирусов.

предположим, что у нас 8 вирусов, расставленных по периметру матрицы - в углах, и на середине каждой стороны. максимальное расстояние ~sqrt(500^2+500^2)~700. пополам - 350. а логика мне подсказывает, что ответ должен быть - 250
Вот только ещё сложнее то, что вирусы расставляешь не ты, а тот кто тестирует программу. Надо в программе указать все варианты размещения вируса: в углу, в серединте, по краям. Вроде бы только 3 варианта.Это только расположение....
0
odip
Эксперт С++
7161 / 3220 / 76
Регистрация: 17.06.2009
Сообщений: 14,161
28.08.2009, 12:58 #39
Да - алгоритм неправильный.
Грубо говоря задача сводится - к такой:
Рисуем M откружностей диаметра T c центрами в вирусах.
Задача - покрыть этими откружностями все поле.
Причем диаметр этих отружностей должен быть минимальным.

Добавлено через 4 минуты
Думаю если учесть все ньюансы то и получится изначальный алгоритм заполнения поля
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
28.08.2009, 12:59 #40
Текущий вариант:
Расстоянием будем считать dx + dy. Надо найти максимум из:
# для каждой пары вирусов: половины расстояний между ними;
# для каждой точки на границе: минимума расстояний от каждого вируса до этой точки;
# то же для каждой середины стороны;
# (возможно, ещё что-то?).
Нехороший тест:
Код
000000
000001
000000
000000
100000
000001
0
28.08.2009, 12:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.08.2009, 12:59

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

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

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


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

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

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