Годинник | |
|
2005 год
|
| |
|
XVIII Всеукраинская олимпиада по информатике
|
XVIII Всеукраинская олимпиада по информатике
Первый тур
Спички (100 баллов)
Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости N квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами - сами спички.
Задание
Напишите программу MATCHES, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.
Входные данные
Единственная строка входного файла MATCHES.DAT содержит одно целое число N (1<=N<=109).
Выходные данные
Единственная строка выходного файла MATCHES.SOL должна содержать одно целое число - минимальное количество спичек требуемых для составления заданного количества квадратов.
Пример входных и выходных данных
| MATCHES.DAT | MATCHES.SOL |
| 4 | 12 |
Альтернативные пути (100 баллов)
Задано прямоугольную таблицу размером M строк на N столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.
Будем снисходительными к Путнику, считая "хорошими" не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на K.
Количество "хороших" путей гарантированно не превышает 109.
Задание
Напишите программу GOODWAYS, находящую значение максимально возможной суммы и количества "хороших" путей.
Входные данные
Первая строка входного файла GOODWAYS.DAT содержит три целых числа M (2<=M<=200), N (2<=N<=200) и K (0<=K<=200). Каждая из последующих M строк содержит N чисел, записанных в соответствующих клеточках.
Выходные данные
Первая строка выходного файла GOODWAYS.SOL должна содержать максимальную возможную сумму; вторая строка - количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.
Пример входных и выходных данных
| GOODWAYS.DAT | GOODWAYS.SOL |
2 3 3
1 9 7
2 5 3 | 20
2 |
Театр (100 баллов)
В Театре собираются поставить грандиозную пьесу из двух актов, в которой освещение имеет большое значение. Сцена театра имеет форму выпуклого многоугольника, заданного вершинами в декартовой прямоугольной системе координат. Над сценой находится прожектор, который может перемещаться над ней произвольным образом. Находясь в некоторой точке, прожектор освещает круглую область с центром в этой точке и радиусом R.
В первом акте на сцене лежат квадратные ковры размером HxH, стороны которых параллельны осям координат. Ковры могут частично выходить за пределы сцены. Рассмотрим фигуру, которая состоит из всех точек, находясь в которых, прожектор не освещает ни один из ковров и не освещает территорию вне сцены. Обозначим ее площадь как S1.
Перед вторым актом ковры убирают со сцены. Рассмотрим фигуру, которая состоит из всех точек, находясь в которых прожектор не освещает территорию вне сцены. Ее площадь обозначим как S2.
Задание
По предоставленным входным файлам, каждый из которых описывает сцену и размещение на ней ковров в первом акте, создайте соответствующие им выходные файлы, которые содержат площади S1 и S2 описанных выше фигур.
Входные данные
На вашем диске в каталоге DATA содержатся 10 файлов, которые имеют названия THEATER.D01, THEATER.D02, ... , THEATER.D10, следующего формата.
В первой строке заданы числа R, H, N, M. Где R - радиус области, которую освещает прожектор. H - длина стороны квадрата, который представляет ковер. N - количество вершин выпуклого многоугольника, который задает сцену. M - количество ковров. Во второй строке находятся N пар чисел - координаты вершин многоугольника в порядке обхода (по или против часовой стрелки). В третьей строке находятся M пар чисел - координаты центров ковров.
Выходные данные
Создайте 10 выходных файлов THEATER.S01, THEATER.S02, : , THEATER.S10 в вашем каталоге на дискете. Эти файлы должны содержать ответы для соответствующих входных файлов.
Каждый файл должен содержать два числа - целые части площадей S1 и S2. Вам не нужно сдавать программу! Баллы будут начисляться за файлы с правильными ответами.
Пример входных и выходных данных
| THEATER.D00 | THEATER.S00 |
0.5 2 4 1
1 1 5 1 5 4 1
4
3 4 | 3 6 |
Второй тур
Счет игры (100 баллов)
Задана квадратная доска размером NxN. Известно, что на ней играли в интеллектуальную игру, вследствие чего клеточки оказались окрашенными в белый, чёрный и зеленый цвета. Раскраска клеточек может быть разной (ведь это интеллектуальная игра!), но все клеточки самого верхнего ряда белые, а самого нижнего - чёрные.
Чтобы выявить победителя, необходимо подсчитать количество клеточек в белой и количество клеточек в черной области. Белая область - это как можно большая (по количеству клеточек) часть квадрата, которая ограничена сверху верхней стороной квадрата, а с других сторон - непрерывной границей, которая проходит только через белые клеточки и никакая клеточка не встречается больше одного раза. Белая граница представляет собой последовательность белых соседних клеточек (соседние клеточки имеют общую сторону). Концами этой границы должны быть левая верхняя и правая верхняя клеточки квадрата.
Определение чёрной области выглядит аналогично: она ограничена снизу нижней стороной квадрата, с других сторон - чёрной границей, которая проходит только через чёрные клеточки, а концы этой границы - левая нижняя и правая нижняя клеточки квадрата.
Задание
Напишите программу SCORE, которая по раскраске квадрата находит количество клеточек в белой и чёрной областях.
Входные данные
Первая строка входного файла SCORE.DAT содержит единственное целое число N - размер квадрата (5?N?250). Каждая из следующих N строк содержит по N символов "G", "W" или "B" (записанных без пробелов), которые обозначают зелёный, белый и чёрный цвет, соответственно.
Выходные данные
Первая строка выходного файла SCORE.SOL должна содержать количество клеточек в белой области, а вторая строка - количество клеточек в чёрной области.
 |
Пример входных и выходных данных
| SCORE.DAT | SCORE.SOL |
7
WWWWWWW
WGWWBWG
WWWWGWW
BBGWWWB
GWBBWGB
BBBBGBB
BBBBBBB | 2215 |
|
Вид белой и чёрной областей для примера из условия представлен на рисунке.
Домино (100 баллов)
Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до M включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).
Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.
Некоторые костяшки были удалены из полного набора. Требуется определить, какое минимальное количество цепочек нужно выложить из оставшихся в наборе костяшек, чтобы каждая из них принадлежала ровно одной цепочке.
Задание
Напишите программу DOMINO, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.
Входные данные
В первой строке входного файла DOMINO.DAT содержится одно целое число M (0?M?100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число N, равное количеству костяшек, удаленных из полного набора. Каждая ?-я из последующих N строк содержит по два числа Ai и Bi. Это количества точек на половинках i-й удалённой костяшки.
Выходные данные
Единственная строка выходного файла DOMINO.SOL должна содержать одно целое число L - минимальное количество цепочек.
Пример входных и выходных данных
| DOMINO.DAT | DOMINO.SOL |
7
2
7 5
3 4
| 2 |
Скалы (100 баллов)
На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x L метров, на котором введены координаты, как показано на рисунке.
Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой H поставить в точку с X-координатой p, то в каждой точке q отрезка [p-H;p] на оси X рельеф поднимается на q-p+H метров по всей его ширине (то есть для произвольного Z от 0 до 1), а в каждой точке q отрезка [p;p+H] рельеф поднимается на H+p-q метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).
Во время строительства рабочие время от времени интересуются объёмом части дамбы, находящейся над некоторым прямоугольником.
Задание
Напишите программу ROCKS, которая поможет рабочим в их расчётах.
Входные данные
В первой строке входного файла ROCKS.DAT содержатся два целых числа: N - количество операций, которые будут выполнять рабочие (1<=N<=100000), и L - длина прямоугольника (1<=L<=100000).
В следующих N строках содержатся описания операций: первое число строки - номер операции, где "1" означает, что рабочие собираются поставить магический импульсатор, "2" - рабочие хотят узнать некоторый объём. Если операция имеет код "1", то далее идут два целых числа p и H (0?p?L; 1?H?L), то есть импульсатор силой H ставят в позицию p (на оси X). Если операция имеет код "2", то далее идут два целых числа A и B (0<=A
Выходные данные
Создайте выходной файл ROCKS.SOL, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.
Если операция есть "1", то выведите число "-1" без кавычек. Если операция есть "2", то выведите число, равное объёму части дамбы, которая находится над прямоугольником от A до B по оси X, и от 0 до 1 по оси Z, как показано на рисунке.
Пример входных и выходных данных
| ROCKS.DAT | ROCKS.SOL |
2 13
1 7 5
2 5 9
| -116 |
Полный архив олимпиады (~4,5 Mb)
|
|
© Всеукраинский виртуальный центр олимпиад школьников
"ОЛІМП"
|
| |
| |
