Страница: 1 2 3 4 5 >> Отображать по:

#26

Результаты олимпиады

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

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2005, Задача A ]

По новым правилам Московской командной олимпиады итоги олимпиады подводятся следующим образом.

Команды решают задачи и могут во время тура посылать их на проверку. Задача проверяется на системе тестов.

Каждая задача оценивается из 2-х баллов. 2 балла получает программа, которая проходит все тесты. Кроме того, 1 баллом оцениваются решения, которые проходят некоторое количество первых тестов в задаче (это количество определяется жюри, оно может быть различным в различных задачах, это количество, как и общее количество тестов по задаче, участникам не сообщается). Жюри может (однако не обязано) указать в условии дополнительные ограничения, которым удовлетворяют тесты, за прохождение которых ставится 1 балл.

Помимо баллов за решение задач, команды получают штрафное время. За каждую задачу штрафное время определяется следующим образом.

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

При этом если произошла ошибка компиляции программы, то такая попытка не учитывается при подсчете неверных попыток (то есть она вообще игнорируется).

Например, если на 1-й минуте команда послала программу, которая набрала 0 баллов, то штрафное время равно 0. Пусть на 2-й минуте команда послала решение, которое набрало 1 балл, тогда команда имеет за эту задачу 1 балл и штрафное время, равное 22 минутам (2 минуты от начала тура + 20 штрафных минут). Если на 3-й минуте команда сдала решение задачи на 2 балла, то результат по этой задаче у команды 2 балла, а штрафное время равно 43 минуты (3 минуты от начала тура + 2*20 минут за 2 предыдущие попытки).

И баллы, и штрафное время, полученное командой по разным задачам, суммируются (получаются суммарные баллы и суммарное штрафное время). Команды ранжируются сначала по баллам, а при равном количестве баллов — по штрафному времени (чем меньше штрафное время, тем выше место команды).

Напишите программу, которая по протоколу попыток, сделанных командой, вычисляет количество набранных командой баллов и штрафное время.

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

В первой строке задается число N — суммарное количество задач (1≤N≤26). Во второй строке содержатся N чисел A_i — количество тестов в каждой задаче (2≤A_i≤100). В третьей строке задаются N чисел B_i — количество тестов, которое должно пройти в соответствующей задаче, чтобы команда получила за нее 1 балл (0<B_i<A_i).

Далее идет M — количество сделанных командой попыток. Затем следуют M строк, каждая из которых содержит 3 числа: первое задает время в минутах от начала тура до момента совершения данной попытки, второе — номер задачи, третье — количество пройденных тестов (или –1, если произошла ошибка компиляции). Все попытки упорядочены по времени, ни в какую минуту команда не делала более одной попытки.

По правилам олимпиады общее количество попыток не превышает 200, продолжительность тура — 3-х месяцев (на самом деле, командная олимпиада длится обычно не более 5 часов, однако жюри олимпиады не исключает, что эти же правила когда-нибудь будут использоваться в заочном туре, который длится как раз 3 месяца).

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

Выведите два целых числа — количество набранных командой баллов и суммарное штрафное время.

Примеры

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

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

2 43

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

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

0 0

#31

Роботы

Темы: [Задачи на моделирование] [Обход в ширину]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2005, Задача F ]

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

В подземелье есть N залов, соединенных туннелями. В некоторых залах находятся роботы, которые одновременно получили команду собраться в одном месте.

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

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

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

Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

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

Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Оценка задачи

1 балл получат программы, правильно решающие задачу в случае, когда встреча роботов произойдет в зале, при ограничениях N≤100, K≤2000, M≤100.

Примеры

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

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

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

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

#37

\"Сортировка\" с конфеткой

Темы: [Задачи на моделирование] [Сортировка "пузырьком"]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2006, Задача B ]

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

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

Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

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

Требуется вывести массив после сортировки.

Примеры

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

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

1 2 4 3

#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) закрашена, и символу «.» (точка) – иначе.

Примеры

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

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

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

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

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

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

#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)

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

Страница: 1 2 3 4 5 >> Отображать по:

Выбрано

Отменить

Добавить в контест