|
Начало раздела - Чемпионат по программированию Протокол I-го тура Турнирная таблица I-го тура |
Главная страница |
Файл программы:treasure.(c|cpp|pas|bas)
Входной файл: treasure.in
Поиск сокровищ – занятие не сложное. Все, в чем Вы нуждаетесь - карта!
Пираты Карибского моря известны своими огромными сокровищами и сложными
картами. Чтение карты обычно выглядит так: “Подойди к одинокой пальме.
Сделай три шага к лесу, затем семнадцать шагов к маленькому роднику, ...
и т.д. и т.п. ..., в заключение сделай шесть шагов к гигантскому камню.
Рой прямо здесь, и найдешь мое Сокровище!” Большинство этих инструкций
сводится к совершению упомянутого числа шагов в одном из восьми основных
направлений по компасу (см. левый рисунок).
Путь искателя сокровищ, проделанный им согласно такому описанию, может
быть весьма замысловатым. Но если Вам некогда любоваться красотами дикой
природы, то нужно идти от точки старта до места, где закопаны сокровища,
по прямой. Часто этот путь бывает гораздо короче. Вместо того, чтобы делать
три шага на север, один шаг на восток, один шаг на север, три шага на восток,
два шага на юг и один шаг на запад (см. правый рисунок), можно сделать
приблизительно 3.6 шага по прямой и добраться до сокровища.
Вы должны написать программу, которая вычисляет расположение и расстояние
до скрытого сокровища, описанного “традиционной” картой.
Входной файл содержит несколько строк. В каждой строке не более 200 символов.
Последняя строка содержит единственное слово END, конец ввода. Все другие
строки описывают одну карту расположения сокровища.
Каждое описание состоит из списка пар <расстояние><направление>,
разделенных запятой, где <расстояние> - положительное целое число, меньшее
1000, а <направление> - N (север), NE (северо-восток), E (восток), SE
(юго-восток), S (юг), SW (юго-запад), W (запад) или NW (северо-запад).
Например, 3W означает 3 шага на запад, и 17NE означает 17 шагов на северо-восток.
Точка (.) завершает описание карты. Описание не содержит пробелов.
Для каждого описания карты, сначала вывести его номер, как показано в примере
вывода. Затем вывести координаты сокровища, в формате “Координаты сокровища
(x,y).” Система координат такова: ось X направлена на восток, ось Y направлена
на север, начало координат соответствует началу пути. Следующей строкой
вывести расстояние от начала пути до места расположения сокровищ в формате
“Расстояние до сокровища d.”. Дробные значения x, y, d должны быть напечатаны
с точностью до третьего знака после запятой.
Вывести пустую строку после обработки каждого описания.
3N,1E,1N,3E,2S,1W.
10NW.
END
Карта #1
Координаты
сокровища (3.000,2.000).
Расстояние
до сокровища 3.606.
Карта
#2
Координаты
сокровища (-7.071,7.071).
Расстояние
до сокровища 10.000.
Файл программы:video.(c|cpp|pas|bas)
Входной файл:video.in
Ваш друг поступил на работу в отдел охраны торговой компании. Одной
из его задач является установить видео систему, для наблюдения за товарами
на бесчисленных этажах огромного склада. Так как компания имеет ограниченный
бюджет, будет установлено по одной камере на каждом этаже. Эти камеры могут
вращаться вокруг, что обеспечивает круговой обзор. Главная задача состоит
в том, чтобы выбрать, место для установки камеры на каждом этаже. Единственным
требованием является обеспечение полного обзора всего помещения.
На левом рисунке камера обеспечивает полный обзор помещения, на правом
нет.
Перед установкой камер, ваш друг сначала хочет узнать, имеется ли для
этого подходящее место. Он просит, чтобы Вы написали программу, которая
на основании анализа плана этажа определяет, имеется ли на этаже точка,
из которой возможен полный обзор помещения.
Все планы этажей представляют собой замкнутые непересекающиеся прямоугольные
многоугольники.
Входной файл содержит описания нескольких этажей. Первая строка каждого
описания содержит целое число n (4 <= n <= 100), которое определяет
количество вершин многоугольника (плана этажа).
Следующие n строки содержат по два целых числа каждая, x и y координаты
n-й вершины. Вершины даются по часовой стрелке. Все вершины отличны друг
от друга.
Ввод завершается описанием этажа с n = 0. Это описание обрабатывать
не нужно.
Для каждого описания этажа, сначала вывести строку с его номером, как показано
в примере вывода. Затем вывести строку, “Полный обзор возможен”, если существует
позиция, из которой весь этаж может быть виден, или “Полный обзор невозможен”,
если такой позиции нет.
Вывести пустую строку после обработки каждого описания.
4
0 0
0 1
1 1
1 0
8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0
0
Этаж #1
Полный
обзор возможен.
Этаж #2
Полный обзор невозможен.
Файл программы: bricks.(c|cpp|pas|bas)
Входной файл:bricks.in
Маленький Ваня любит играть в кубики. Он ставит их один на другой, и получаются столбики разной высоты. “Погляди, какую я стену построил! ”, говорит Ваня своей старшей сестре Леночке. “Ха, у настоящей стены все столбики одинаковые”, отвечает она. После небольшого раздумья, Ваня понимает, что сестра права. Он устраивается по удобнее и собирается переложить кубики так, чтобы выровнять высоту столбиков. “Как бы это сделать так, что бы поменьше кубиков передвигать?” – думает трудолюбивый Ваня. Вы можете помочь?
Входной файл содержит несколько наборов данных. Каждый набор начинается со строки, содержащей одно целое число n, количество столбиков, которые построил Ваня. Следующая строка содержит n целых чисел hi, обозначающих высоту каждого столбика. Числа удовлетворяют следующим условиям: 1 <= n <= 50, 1 <= hi <= 100, общее количество кубиков кратно количеству столбиков. Таким образом, задача всегда имеет решение.
Ввод завершается набором с n = 0. Этот набор обрабатывать не нужно.
Для каждого набора, сначала вывести строку с его номером, как показано
в примере вывода.
Затем вывести строку “Минимальное количество перемещений – k.”, где
k - минимальное количество кубиков, которые нужно переместить для того,
чтобы выровнять высоту всех столбиков.
Вывести пустую строку после обработки каждого набора.
5 2 4
1 7 5
0
Набор #1
Минимальное
количество перемещений – 5.
Файл программы:dice.(c|cpp|pas|bas)
Входной файл:
dice.in
InterGames - компания, специализирующаяся в области разработки игр для
сети Internet. Анализ рынка показал, что такие игры являются популярным
среди их потенциальных заказчиков. В настольных аналогах большинства известных
в мире игр, на определенном этапе игроки бросают игральные кости.
В Internet-игре неблагоразумно позволять игрокам бросать кости и затем
вводить результат в компьютер. Слишком много простора для обмана. Вместо
этого, специалисты InterGames решили оснастить свой игровой комплект телекамерой,
которая будет анализировать изображение кости и автоматически определять
результат броска.
Для этого они отчаянно нуждаются в программе, которая по изображению
игральной кости смогла бы определить количество выпавших очков.
Мы делаем следующие предположения относительно входных изображений.
Изображения состоят из пикселей трех различный цветов: цвет фона, цвет
игральной кости, цвет точки на поверхности кости. Два пиксела принадлежат
одному объекту изображения, если они связаны – имеют общую сторону (касания
углами недостаточно). На рисунке, пиксели A и B связанные, B и C - нет.
|
|
|||
|
|
|
||
Набор S пикселей связан если
для каждой пары (a, b) пикселей в S, имеется последовательность пикселей
a1, a2, …, ak
принадлежащая S такая, что a=a1, b=ak, ai
и ai+1связанные пикселы
для всех 1 <= i <= k.
Будем считать изображением
игральной кости максимальный связанный набор пикселей не фонового
цвета. Максимальный – это такой набор, к которому больше нечего
добавить без того, чтобы он не перестал быть связанным. Аналогично определим
изображение точки на поверхности игральной кости.
Ввод состоит из нескольких описаний снимков телекамеры. Каждое описание
начинается со строки, содержащей два числа w и h (ширину и высоту снимка).
Их значения удовлетворяют следующему условию: 5 < w, h < 50. Далее
следуют h строк по w символов в каждой. Символы могут быть: ‘.’ – цвет
фона, ‘*’ – цвет игральной, ‘X’ –
цвет точки на поверхности кости. На снимке
изображена хотя бы одна игральная кость. Изображение грани игральной кости
из-за оптических искажений не обязательно имеет прямоугольную форму.
Ввод завершается описанием, в котором w = h = 0. Это описание обрабатывать
не нужно.
Для каждого описания снимка кристалла, сначала вывести его номер. Затем
вывести числа точек на изображениях игральных костей данного снимка, в
порядке возрастания.
Печатайте, пустую строку после каждого случая теста.
Выведите, пустую строку после обработки каждого описания.
30 15
..............................
..............................
...............*..............
...*****......****............
...*X***.....**X***...........
...*****....***X**............
...***X*.....****.............
...*****.......*..............
..............................
........***........******.....
.......**X****.....*X**X*.....
......*******......******.....
.....****X**.......*X**X*.....
........***........******.....
..............................
0 0
Снимок #1
1 2 2
4
Файл программы:fastfood.(c|cpp|pas|bas)
Входной файл:fastfood.in
Компания McBurger обладает цепью придорожных ресторанов. Недавно, она
решила пристроить к нескольким ресторанам складские помещения. Каждый такой
склад будет обслуживать несколько близлежащих ресторанов. Конечно, эти
склады должны располагаться так, чтобы расстояние между ними и обслуживаемыми
ресторанами было минимальным. Вы должны написать программу, которая вычисляет
оптимальное положение для каждого склада.
Более точно McBurger ставит задачу так:
Вам будут даны положения n ресторанов
вдоль шоссе как n целых чисел d1 < d2 < … < dn,
где di - это расстояния
до i-го ресторана от штаб-квартиры компании по шоссе. Кроме того, дается
номер k (k <= n), число складов, которые планируется построить. Каждый
ресторан будет обслуживаться ближайшим к нему складом. Общая сумма расстояния
перевозок, определяемая как
должна быть минимальной.
Напишите программу, рассчитывающую положение k складов так, чтобы общая
сумма расстояния перевозок была минимальной.
Ввод состоит из несколько описаний
цепочек ресторанов. Каждое описание начинается со строки, содержащей два
целых числа n и k, таких что: 1 <= n <= 200; 1 <= k <= 30;
k <= n. Далее следуют n строк, каждая из которых содержит одно число
di - расстояния до i-го
ресторана от штаб-квартиры компании по шоссе. Строки упорядочены по возрастанию
расстояний.
Ввод завершается описанием,
в котором n = k = 0. Это описание обрабатывать не нужно.
Для каждого описания цепочек ресторанов, сначала вывести его номер. Затем
вывести схему оптимального размещения складов следующим образом: номер
ресторана, в котором будет располагаться склад и диапазон номеров ресторанов,
которые будут им обслуживаться (смотри пример ниже). Если имеется более
одного варианта оптимального расположения складов - вывести любой из них.
Последней строкой вывести общую сумму расстояния перевозок для данной схемы.
Выведите, пустую строку после обработки каждого описания.
6 3
5
6
12
19
20
27
0 0
Цепочка #1
Склад
1 в ресторане 2 обслуживает рестораны с 1 по 3
Склад
2 в ресторане 4 обслуживает рестораны с 4 по 5
Склад
3 в ресторане 6 обслуживает ресторан 6
Общая
сумма расстояния перевозок = 8
Файл программы:ai.(c|cpp|pas|bas)
Входной файл:ai.in
Преподаватели физики в средней школе часто думают, что задачи, правильнее
давать в виде текстового описания, а не в виде математических формул. В
конце концов, ученики должны сначала прочитать и понять задачу!
Такие учителя стараются поставить задачу не так:
"U = 10V, I = 5A, P =?"
а скорее так:
"Вы имеете замкнутую электрическую цепь, состоящую из источника постоянного тока с напряжением U = 10V и лампочки. В цепи течет электрический ток I= 5A. Какая мощность выделяется на лампочке? ".
Однако многие ученики не обращают внимания на текст задачи. Они извлекают
из него уравнения: U = 10V, I = 5A., а затем думают: "Какую же формулу
я знаю? Ах да, P = U*I.. Следовательно P = 10V*5A = 500W. Все, готово."
Такой подход к решению задач не всегда работает и такие ученики не
относятся к разряду лучших. Но этот простой алгоритм обычно достаточно
хорош для перехода в следующий класс.
Сегодня мы проверим, может ли компьютер решить задачу по физике и перейти
в следующий класс средней школы. Мы остановимся на решении задач типа P-U-I,
то есть задач, в которых две величины из мощности, напряжения и силы тока
даны, а третью требуется вычислить.
Вашей целью будет написать программу, которая читает текст такой задачи
и решает ее согласно простому алгоритму данному выше.
Вход состоит из описаний нескольких задач. Первая строка входного файл
будет содержать единственное положительное целое число n – количество задач.
Следующие n строк содержат описания задач. Описание каждой задачи будет
состоять из одной строки, содержащей точно два поля данных и некоторое
количество произвольных слов (возможно не на русском языке).
Поле данных будет иметь форму I = xA, U = xV или P = xW, где x - вещественное
число. Непосредственно перед значком единицы измерения (A, V или W) может
стоять один из префиксов m. (мили), k (кило) или М. (мега). Более строго
поле данных описывается следующей грамматикой:
DataField ::= Concept '=' RealNumber [Prefix] Unit
Concept ::= 'P' | 'U' | 'I'
Prefix ::= 'm' | 'k' | 'M'
Unit ::= 'W' | 'V' | 'A'
Дополнительные утверждения:
Для каждой задачи вывести три строки:
строка "Задача #k" где k – порядковый номер задачи строка с решением. Величина напряжения, мощности или тока, в зависимости от условия, в основных единицах измерения с точностью до второго знака после запятой (смотри пример ниже). Пустая строка.
3
If the
voltage is U=200V and the current is I=4.5A, which power is generated?
A light-bulb
yields P=100W and the voltage is U=220V. Compute the current, please.
bla bla
bla lightning strike I=2A bla bla bla P=2.5MW bla bla voltage?
Задача #1
P=900.00W
Задача
#2
I=0.45A
Задача
#3
U=1250000.00V
Файл программы:friends.(c|cpp|pas|bas)
Входной файл:friends.in
Вы планируете грандиозную вечеринку по
поводу своего дня рождения. “Чипсы и все такое…”. Всех Вы пригласить не
сможете – просто не хватит места. Множество Ваших друзей состоит из отдельных
групп (подмножеств). Одноклассники (g1), ребята с Вашего двора (g2), приятели
по спортивной секции (g3), знакомые по летнему лагерю (g4) и т.д. При выборе
кандидатов на приглашение Вам придется оперировать со множествами.
Например, если Вы решили пригласить одноклассников
и ребят со своего двора, то это будет выглядеть как g1+g2 - объединение
двух групп.
Если Вы хотите пригласить всех одноклассников,
за исключением тех, которые были с Вами в летнем лагере, то это будет выглядеть
как g1-g4 - разность двух групп.
Если Вы хотите пригласить всех одноклассников,
занимающихся вместе с Вами в спортивной секции, то это будет выглядеть
как g1*g3 - пересечение двух групп.
Пересечение (*) имеет приоритет над объединением
(+) и разностью(-) множеств. Все операции лево - ассоциативны. Это означает,
что для вычисления выражения A op1 B op2
C, где A, B и C – множества, а op1
и op2
любые операции из
+, -, * Вы должны сначала вычислить значение выражения A op1
B (при условии, что обе операции имеют одинаковый приоритет).
Ввод состоит из одной или более строк. Каждая строка содержит одно выражение, которое Вы должны вычислить. Выражения синтаксически правильны и состоят из:
Длина строки не превышает 255 символов.
Печатайте получающиеся множества в фигурных скобках '{' и '}', на отдельной строке. Элементы внутри множества печатайте в алфавитном порядке.
{ABC}
{ABC}+{DEFG}+{Z}+{}
{ABE}*{ABCD}
{ABCD}-{CZ}
{ABC}+{CDE}*{CEZ}
{{ABC}+{CDE})*{CEZ}
{ABC}
{ABCDEFGZ}
{AB}
{ABD}
{ABCE}
{CE}
Файл программы:quadtree.(c|cpp|pas|bas)
Входной файл:quadtree.in
При поиске сокровищ Ацтеков, Флориде Джонс (брату известного Индианы
Джонса) попался в руки древний папирус с длинной строкой таинственных символов.
Строка состояла из комбинации трех различных символов (назовем их B, W
и Q). Будучи опытным криптографом, Флорида Джонс сразу распознал этот шифр
известный вот уже 3000 лет под названием “Дерево квадрантов”.
По системе “Дерева квадрантов”, секретные изображения (подобно картам
сокровищ) кодируются следующим способом: если изображение целиком черное,
оно будет закодировано символом B. Если изображение целиком белое, оно
будет закодировано символом W. Если в изображении используются оба цвета
(что обычно имеет место), оно будет закодировано строкой Qxxxx, где каждый
x это строка, в которой закодирована одна четверть исходного изображения
(верхняя левая, верхняя правая, нижняя левая, нижняя правая). Так как все
изображения Ацтеков были квадратными со стороной n, где n – степень двойки,
данный способ кодирования всегда великолепно работал.
Изображение кусочка шахматной доски размером 2х2, например, было бы
закодировано как QWBBW, изображение кусочка шахматной доски размером 4*4,
было бы закодировано как QQWBBWQWBBWQWBBWQWBBW.
Ваша программа должна декодировать строку шифра “Дерева квадрантов”
и выдать изображение в формате XBM (см. спецификацию вывода).
Входной файл состоит из двух строк. Первая строка содержит целое число n (8 < = n < = 512), где n размер изображения в пикселах n x n. n всегда будет степенью двойки. Вторая строка состоит из цепочки символов B, W и Q. Строка представляет закодированное по системе “Дерева квадрантов” изображение размером n x n точек.
16
QQWBBWQWBBWQWBBWQWBBW
Обратите внимание на то, что комментарии (все, что заключено между /* и */) не часть вывода. Они просто поясняют формат XBM.
#define
quadtree_width 16
#define
quadtree_height 16
static
char quadtree_bits [] = {
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0xf0,0xf0,
/* WWWWBBBB WWWWBBBB */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
0x0f,0x0f,
/* BBBBWWWW BBBBWWWW */
};
| Наверх
webmaster |
