Легенда

​Друзья позвали вас сыграть в стратегическую настольную игру, посвящённую возобновляемым источникам энергии — экология стала модным направлением! В игре вы становитесь владельцем земли — в распоряжении есть прямоугольное поле произвольного размера из квадратных секторов-клеток, для которых известны средняя скорость ветра и яркость солнца. В честном споре — на камень-ножницы-бумага — вам выпала возможность генерировать энергию с помощью солнечных и ветряных электростанций (СЭС и ВЭС соответственно). На клетки вы можете поставить либо одну солнечную электростанцию (1х1), либо ветряную (2х2). СЭС производит энергию пропорционально яркости солнца с коэффициентом 1.5. ВЭС производит энергию пропорционально квадрату средней скорости ветра на занимаемом участке. Количество СЭС неограничено, количество ВЭС ограничено 5-ью станциями (можно выставить не все). Ваша цель — победить в игре, а именно — максимизировать вырабатываемую энергию, с умом расставив электростанции. Решение засчитывается, если предложенная им расстановка обеспечивает не меньшую генерацию, чем у авторского решения.

Формат входных данных: в первой строке – два целых числа, ширина N и высота M поля. Далее идут две вещественные матрицы из M строк и N столбцов: в первой приводятся средние скорости ветра в каждой клетке, во второй – средние яркости солнца.

4 4
8.9 7.3 8.3 4.4
8.5 2.6 3.0 8.4
9.4 2.5 8.3 6.2
5.9 9.1 1.4 9.1
9.1 3.3 2.4 5.0
5.8 9.9 3.3 3.4
8.6 6.2 1.8 2.9
6.0 7.6 4.6 8.8

Формат выходных данных: набор строк в виде матрицы из M строк и N столбцов. В каждой клетке указывается: S, если выставлена СЭС, W – если выставлена ВЭС, и . (символ точки), если ничего не выставлено. Символы должны быть разделены пробелом. Заметьте, ВЭС должны выставляться блоками 2 на 2 клетки, и это будет проверяться!

. W W S
S W W .
S . S S
. S S .

Для решения этой задачи у вас есть 20 попыток.

Time Limit: 5 секунд

Memory Limit: 256 MB

Видео-разбор


Последнее изменение: Wednesday, 31 January 2024, 13:15