#405

Цифровое табло

Темы: [Задачи на моделирование] [Двумерные массивы]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача C ]

Изображение задается отрезками, параллельными осям координат или под углом 45 градусов к ним. Необходимо вывести таблицу, где все отрезки имеют ширину k клеток.

В комнате у Аркадия Семеновича Тапкина стоят электронные часы. Цифры на этих часах показываются в специальной псевдографике. А именно, каждое поле, на котором изображается цифра, состоит из w ячеек в ширину и h ячеек в высоту (при этом ячейки на поле имеют форму квадратов).

Но недавно у Аркадия Семеновича появилась проблема. Последнее время он стал плохо видеть. В связи с этим он хочет увеличить изображение этих цифр. Он уже приладил старый 19'' монитор к часам, и теперь дело осталось за малым. Осталось написать программу, которая будет рисовать цифры на дисплее. Аркадий Семенович хочет увеличить изображение в k раз и сделать толщину линий равной d. Помогите ему в этом.

Опишем более формально понятие «увеличить в k раз». Занумеруем ячейки поля w×h сверху вниз и слева направо. Таким образом, верхняя левая ячейка имеет координаты (0, 0), правая нижняя – (w - 1, h - 1), правая верхняя – (w - 1, 0), левая нижняя – (0, h - 1). Кроме этого, введем декартову прямоугольную систему координат так, что начало координат находится в центре верхней левой ячейки, ось Ox направлена вправо, ось Oy – вниз, длину единичного отрезка примем равной длине стороны ячейки. Таким образом, координаты центра ячейки совпадают с ее координатами во введенной нумерации.

Каждая десятичная цифра задается набором составляющих ее изображение отрезков. Для простоты каждый из отрезков либо параллелен одной из координатных осей, либо идет под углом в 45 градусов к ней.

Увеличенная в k раз цифра рисуется на поле размером (w - 1)^.(k - 1) + w ячеек по горизонтали на (h - 1)^.(k - 1) + h ячеек по вертикали.

При увеличении некоторой цифры в k раз производятся следующие операции. Координаты точек, являющихся концами отрезков, составляющих цифру, умножаются на k. После этого закрашиваются те ячейки, через центры которых проходят эти отрезки. Эти ячейки будем называть основными.

После этого, для того, чтобы получить толщину линий равную d, дополнительно закрашиваются те ячейки, центры которых располагаются на расстоянии, не превышающем (d - 1) от центров основных ячеек. Расстоянием между точками A(x_A, y_A) и B(x_B, y_B) будем называть число $rho$ (A, B) = | x_A - x_B| + | y_A - y_B|.

По описанию цифры и параметрам k и d выведите изображение цифры, увеличенное в k раз, с толщиной линий d.

Входные данные

В первой строке вводятся числа k и d ( 1 $le$ k $le$ 100, 1 $le$ d $le$ 500). Вторая строка содержит целые числа w и h ( 1 $le$ w, h $le$ 10).

В третьей строке задается целое число n ( 1 $le$ n $le$ 100) – количество отрезков в описании цифры. Далее следуют n строк, каждая из которых описывает один отрезок. Описание отрезка состоит из четырех целых чисел: x₁, y₁, x₂, y₂ ( 0 $le$ x₁, x₂ < w, 0 $le$ y₁, y₂ < h) – координат концов отрезка.

Каждый из отрезков либо параллелен одной из координатных осей, либо идет под углом в 45 градусов к ней. Все отрезки имеют ненулевую длину.

Выходные данные

Программа должна вывести ровно (h - 1)^.(k - 1) + h строк по (w - 1)^.(k - 1) + w символов в каждой, j-ый символ i-ой строки должен быть равен символу «*» (звездочка), если ячейка с центром в точке (j, i) закрашена, и символу «.» (точка) – иначе.

Примеры

Входные данные

Выходные данные

****
...*
...*
...*
...*
...*

Входные данные

Выходные данные

*******
......*
......*
......*
......*
.....*.
....*..
...*...
..*....
.*.....
*******

#406

Выборы

Темы: [Бинарный поиск в массиве] [Быстрая сортировка] [Бинарный поиск по ответу]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача D ]

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

В одной демократической стране приближаются парламентские выборы. Выборы проходят по следующей схеме: каждый житель страны, достигший восемнадцатилетнего возраста, отдает свой голос за одну из политических партий. После этого партия, которая набрала максимальное количество голосов, считается победившей на выборах и формирует правительство. Если несколько партий набрали одинаковое максимальное количество голосов, то они должны сформировать коалиционное правительство, что обычно приводит к длительным переговорам.

Один бизнесмен решил выгодно вложить свои средства и собрался поддержать на выборах некоторые партии. В результате поддержки он планирует добиться победы одной из этих партий, которая затем сформирует правительство, которое будет действовать в его интересах. При этом возможность формирования коалиционного правительства его не устраивает, поэтому он планирует добиться строгой победы одной из партий.

Чтобы повлиять на исход выборов, бизнесмен собирается выделить деньги на агитационную работу среди жителей страны. Исследование рынка показало, что для того, чтобы один житель сменил свои политические воззрения, требуется потратить одну условную единицу. Кроме того, чтобы i-я партия в случае победы сформировала правительство, которое будет действовать в интересах бизнесмена, необходимо дать лидеру этой партии взятку в размере p_i условных единиц. При этом некоторые партии оказались идеологически устойчивыми и не согласны на сотрудничество с бизнесменом ни за какие деньги.

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

Входные данные

В первой строке вводится целое число n – количество партий ( 1<= n <=10⁵). Следующие n строк описывают партии. Каждая из этих строк содержит по два целых числа: v_i – количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и p_i – взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена ( 1<=v_i<=10⁶, 1<=p_i<=10⁶ или p_i = - 1). Если партия является идеологически устойчивой, то p_i равно -1. Гарантируется, что хотя бы одно p_i не равно -1.

Выходные данные

В первой строке выведите минимальную сумму, которую придется потратить бизнесмену. Во второй строке выведите номер партии, лидеру которой следует дать взятку. В третьей строке выведите n целых чисел – количество голосов, которые будут отданы за каждую из партий после осуществления операции. Если оптимальных решений несколько, выведите любое.

Примеры

Входные данные

Выходные данные

6
3
3 2 5

#407

Треугольная рамка

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача E ]

Требуется вычислить площадь треугольной рамки (треугольника с заданными сторонами, из которого вырезан подобный треугольник, отступая от сторон на заданное расстояние).

Картины художников-абстракционистов весьма необычны. На них часто изображены абсолютно непонятные предметы. Один известный художник-абстракционист решил добавить своим картинам оригинальности следующим способом. Вместо прямоугольных рамок, в которые обычно вставляются картины, он решил на ближайшей выставке использовать треугольные.

Однако все оказалось совсем не так просто. Художник изготовил рамку, поместил в нее картину и понял, что что-то не так. Рамка получилась слишком широкой, и картина выглядела совсем не так ярко, как он ожидал.

Немного поразмыслив, художник понял, что то, насколько рамка «подходит» для картины, определяется площадью рамки. Кроме этого он понял, что рамки надо не изготавливать самостоятельно, а покупать в специальном магазине. Заглянув в прайс-лист магазина, он увидел, что для каждой рамки в нем указаны длины внешних сторон и ширина.

Поясним подробнее то, как выглядит треугольная рамка. Ее изготовление происходит следующим образом: берется доска из красного дерева, имеющая форму треугольника со сторонами a, b и c. После этого стороны этого треугольника мысленно сдвигаются внутрь него на расстояние d (измеряемое по перпендикуляру к соответствующей стороне). На точках пересечения «сдвинутых» сторон строится маленький треугольник, который затем вырезается из исходного. Пример рамки со сторонами a = 6, b = 8, c = 10 и шириной d = 1 показан на рисунке.

Рис. 1

Помогите художнику по имеющимся в прайс-листе данным вычислить площадь рамки.

Входные данные

На вход программы поступают четыре целых числа a, b, c, d ( 1 $le$ a, b, c, d $le$ 1000) – длины внешних сторон рамки и ее ширина, соответственно. Гарантируется, что треугольник со сторонами a, b и c существует, и что в треугольнике есть точка, расстояние от которой до ближайшей стороны строго больше d.

Выходные данные

Выведите площадь рамки с точностью не меньше 10^-5.

Примеры

Входные данные

6 8 10 1

Выходные данные

18.0

#408

Форматирование документа

Темы: [Задачи на моделирование] [Алгоритмы на строках]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача F ]

Дано описание текста, в котором каждое слово занимает некоторый блок. В тексте расположены рисунки, для которых заданы параметры их расположения (обтекание текстом и т.п.). Требуется для каждого рисунка определить его координаты на странице.

Вася пишет новую версию своего офисного пакета "Closed Office". Недавно он начал работу над редактором "Dword", входящим в состав пакета.

Последняя проблема, с которой столкнулся Вася --- размещение рисунков в документе. Он никак не может добиться стабильного отображения рисунков в тех местах, в которые он их помещает. Окончательно отчаявшись написать соответствующий модуль самостоятельно, Вася решил обратиться за помощью к вам. Напишите программу, которая будет осуществлять размещение документа на странице.

Документ в формате редактора "Dword" представляет собой последовательность абзацев. Каждый абзац представляет собой последовательность элементов – слов и рисунков. Элементы одного абзаца разделены пробелами и/или переводом строки. Абзацы разделены пустой строкой. Строка, состоящая только из пробелов, считается пустой.

Слово --- это последовательность символов, состоящая из букв латинского алфавита, цифр, и знаков препинания: ".", ",", ":", ";", "!", "?", "-", "'".

Рисунок описывается следующим образом: "(image image parameters)". Каждый параметр рисунка имеет вид "имя=значение". Параметры рисунка разделены пробелами и/или переводом строки. У каждого рисунка обязательно есть следующие параметры:

Параметр	Описание
width	Целое положительное число – ширина рисунка в пикселях
height	Целое положительное число – высота рисунка в пикселях
layout	Одно из следующих значений: embedded (в тексте), surrounded (обтекание текстом), floating (свободное) – описывает расположение рисунка относительно текста

Документ размещается на бесконечной вверх и вниз странице шириной $w$ пикселей (разбиение на конечные по высоте страницы планируется в следующей версии редактора). Одна из точек на левой границе страницы условно считается точкой с ординатой равной нулю. Ордината увеличивается вниз.

Размещение документа происходит следующим образом. Абзацы размещаются по очереди. Первый абзац размещается так, что его верхняя граница имеет ординату 0.

Абзац размещается следующим образом. Элементы располагаются по строкам. Каждая строка исходно имеет высоту $h$ пикселей. В процессе размещения рисунков высота строк может увеличиваться, и строки могут разбиваться рисунками на фрагменты.

Слова размещаются следующим образом. Считается, что каждый символ имеет ширину $c$ пикселей. Перед каждым словом, кроме первого во фрагменте, ставится пробел шириной также в $c$ пикселей. Если слово помещается в текущем фрагменте, то оно размещается на нем. Если слово не помещается в текущем фрагменте, то оно размещается в первом фрагменте текущей строки, расположенном правее текущего, в котором оно помещается. Если такого фрагмента нет, то начинается новая строка, и поиск подходящего фрагмента продолжается в ней. Слово всегда "прижимается" к верхней границе строки.

Размещение рисунка зависит от его расположения относительно текста.

Если расположение рисунка относительно текста установлено в "$embedded$", то он располагается так же, как слово, за тем исключением, что его ширина равна ширине, указанной в параметрах рисунка. Кроме того, если высота рисунка больше текущей высоты строки, то она увеличивается до высоты рисунка (при этом верхняя граница строки не перемещается, а смещается вниз нижняя граница). Если рисунок типа "$embedded$" не первый элемент во фрагменте, то перед ним ставится пробел шириной $c$ пикселей. Рисунки типа "$embedded$" также прижимаются к верхней границе строки.

Если расположение рисунка относительно текста установлено в "$surrounded$", то рисунок размещается следующим образом. Сначала аналогично находится первый фрагмент, в котором рисунок помещается по ширине. При этом перед рисунком этого типа не ставится пробел, даже если это не первый элемент во фрагменте.

После этого рисунок размещается следующим образом: верхний край рисунка совпадает с верхней границей строки, в которой находится найденный фрагмент, а сам рисунок продолжается вниз. При этом строки, через которые он проходит, разбиваются им на фрагменты.

Если расположение рисунка относительно текста установлено в "$floating$", то рисунок размещается поверх текста и других рисунков и никак с ними не взаимодействует. В этом случае у рисунка есть два дополнительных параметра: "$dx$" и "$dy$" --- целые числа, задающие смещение в пикселях верхнего левого угла рисунка вправо и вниз, соответственно, относительно позиции, где находится верхний правый угол предыдущего слова или рисунка (или самой левой верхней точки первой строки абзаца, если рисунок --- первый элемент абзаца).

Если при размещении рисунка таким образом он выходит за левую границу страницы, то он смещается вправо, так, чтобы его левый край совпадал с левой границей страницы. Аналогично, если рисунок выходит за правую границу страницы, то он смещается влево, чтобы его правый край совпадал с правой границей страницы.

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

По заданным $w$, $h$, $c$ и документу найдите координаты верхних левых углов всех рисунков в документе.

Входные данные

В первой строке вводятся три целых числа: $w$, $h$ и $c$ ($1 \le w \le 1000$, $1 \le h \le 50$, $1 \le c \le w$).

Далее следует документ. Размер входных данных не превышает $1000$ байт. Гарантируется, что ширина любого слова и любого рисунка не превышает $w$. Высота всех рисунков не превышает 1000. Относительное смещение всех рисунков типа "$floating$" не превышает $1000$ по абсолютной величине.

Выходные данные

Выведите по два числа для каждого рисунка --- координаты его верхнего левого угла. Выводите координаты рисунков в том порядке, в котором они встречаются во входных данных.

Рисунок к примеру

Примеры

Входные данные

120 10 8
start (image layout=embedded width=12 height=5)
(image layout=surrounded width=25 height=58)
and word is 
(image layout=floating dx=18 dy=-15 width=25 height=20)
here new 
(image layout=embedded width=20 height=22)
another
(image layout=embedded width=40 height=19)
longword

new paragraph
(image layout=surrounded width=5 height=30)
(image layout=floating width=20 height=35 dx=50 dy=-16)

Выходные данные

#409

Максимальная сумма

Темы: [Динамическое программирование на таблицах]

Источники: [ Командные олимпиады, ВКОШП, 2006, Задача G ]

Задана таблица, содержащая числа. Необходимо найти прямоугольную рамку (прямоугольник, с осями, параллельными осям координат и шириной линий 1) с максимальной суммой чисел в ячейках, покрытых рамкой.

Сегодня на страницах газеты «Математический досуг» была опубликована необычная математическая головоломка. Одна из страниц газеты полностью занята прямоугольной таблицей, состоящей из m строк и n столбцов. В каждой ячейке таблицы записано некоторое целое число.

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

Безуспешно потратив несколько часов на решение головоломки, Саша решил написать программу, которая сделала бы это за него. Но и тут его постигла неудача. Теперь ему ничего не остается, как обратиться за помощью к вам.

Напишите программу, которая по заданной таблице найдет искомый прямоугольник.

Входные данные

В первой строке вводятся два целых числа $m$ и $n$ ($2 \le m, n \le 300$). Далее следует описание таблицы – $m$ строк, каждая из которых содержит по $n$ целых чисел $a_{i, j}$ ($-10^4 \le a_{i,j} \le 10^4$).

Выходные данные

В первой строке выведите целое число $s$ – максимальную сумму чисел на границе искомого прямоугольника. Во второй строке выведите четыре натуральных числа: $x_1$, $y_1$, $x_2$, $y_2$ – координаты левой верхней и правой нижней ячейки выбранного прямоугольника, соответственно (здесь $x$ – номер строки, а $y$ – номер столбца, строки нумеруются сверху вниз, начиная с единицы, столбцы нумеруются слева направо, начиная с единицы). Если оптимальных решений несколько, выведите любое.

Примеры

Входные данные

2 3
1 1 1
1 1 1

Выходные данные

6
1 1 2 3

Входные данные

5 4
9 -2 -1 3
-10 -5 1 -4
1 -1 2 -2
3 0 0 -1
2 2 -1 2

Выходные данные

8
3 1 5 3