|
Начало раздела - Чемпионат по программированию Протокол II-го тура Турнирная таблица II-го тура |
Главная страница |
Файл программы: quadtre2.(c|cpp|pas|bas)
Входной файл:quadtre2.in
Поняв, что закодированная методом “Дерева квадрантов” карта была фальшивкой, Флорида Джонс решает сыграть злую шутку со следующим охотником за сокровищами. Но для этого, он нуждается в вашей помощи еще раз: Вы должны написать программу, которая берет изображение в формате XBM и кодирует его методом “Дерева квадрантов”.
Обратите внимание на то, что комментарии (все, что заключено между /* и */) не часть вывода. Они просто поясняют формат 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 */
};
16
QQWBBWQWBBWQWBBWQWBBW
Так как задачи “Дерево квадрантов” и “Дерево квадрантов II” являются обратными друг другу, Вы можете воспользоваться решением одной задачи для проверки решения другой.
Файл программы:poly.{c|cpp|pas|bas}
Входной файл:poly.in
Даны коэффициенты полинома от степени 8 до степени 0. Вы должны вывести
полином в читаемом виде, удалив ненужные символы. Например, для ряда коэффициентов
0, 0, 0, 1, 22, -333, 0, 1, -1 вы должны вывести строку x^5 + 22x^4 - 333x^3
+ x - 1.
Правила форматирования, которые должны быть соблюдены:
- Члены должны бать выведены в порядке уменьшения степени.
- Значение степени должно идти после знака '^'.
- Постоянный член нужно выводить как константу.
- Нужно выводить только члены с коэффициентами отличными от нуля. Если коэффициенты всех членов равны нулю, тогда необходимо вывести постоянный член.
- Единственными пробелами должны быть одиночные пробелы, окружающие с обеих сторон бинарные операторы + и -
- Если первый член полинома положительный, то его знак выводить ненужно, а если отрицательный то нужно, как показано: -7x^2 + 30x + 66
- Отрицательный член оформляется как вычитаемый положительный член, за исключением случая, описанного в пункте 6.
не правильно x^2 + -3x
правильно x^2 - 3x- Коэффициенты 1 и -1 должны появляться только в виде постоянного члена.
не правильно -1x^3 + 1x^2 + 3x^1 - 1
правильно -x^3 + x^2 + 3x - 1
Входной файл будет содержать дну или более количество строк. Каждая строка содержит девять коэффициентов полинома, разделенных одним или более пробелом. Каждый коэффициент, это целое число, абсолютное значение которого не превышает 1000.
Для каждого набора коэффициентов нужно вывести одну строку, содержащую полином, в том виде, как описано выше.
0 0 0 1 22
333 0 1 1
0 0 0
0 0 0 55 5 0
x^5 + 22x^4
333x^3 + x 1
55x^2
+ 5x
Файл программы:doors.{c|cpp|pas|bas}
Входной файл:doors.in
Вы должны найти длину самого короткого пути через помещение, содержащее препятствия в виде стен. Помещение всегда будет иметь координаты углов (0;0) и (10;10). Начальный и конечный пункты пути - всегда (0;5) и (10;5). Внутри помещения могут находиться от 0 до 18 вертикальных стенок, каждый с двумя дверными проемами. Рисунок ниже изображает такое помещение и показывает искомый путь минимальной длины.
Входные данные для помещения, показанного на рисунке, следующие:
2
4 2 7
8 9
7 3 4.5
6 7
Первая строка содержит число внутренних границ (стенок). Затем идут
по одной строке для каждой стенки, содержащие пять вещественных чисел каждая.
Первое число - координата x стенки (0<x<10), остальные четыре - y
координаты концов дверных проемов. Стенки появляются в порядке увеличения
их x-координат. Дверные проемы появляются в порядке увеличения их y-координат.
Входной файл будет содержать по крайней мере один такой набор данных.
Конец данных определяется набором данных, в котором количество стенок
равно –1.
Для каждого набора данных вывести одну строку, содержащую единственное
число – минимальную длину пути, округленную до второго знака после запятой.
В строке не должно быть пробелов.
1
5 4 6
7 8
2
4 2 7
8 9
7 3 4.5
6 7
-1
10.00
10.06
Файл программы:arraymap.{c|cpp|pas|bas}
Входной файл:arraymap.in
Компьютерная фирмаCybersoft
(лидер в разработках языков программирования) наняла Вас для разработки
нового языка программированияA--.
Ваша задача состоит в том, чтобы разработать модуль языка для работы с
массивами, который будет получать ссылку на элемент массива типа x [5,6]
и вычислять его физический адрес. Физический адрес нужно вывести в виде
десятичного числа.
Физический адрес элемента массива A[i1,i2,…,iD]
вычисляется по формуле C0+C1i1+C2i2+…+ СDiD
, где константы C0…CD
вычисляются как определено ниже:
B = Базовый адрес массива
D = Число размерностей в массиве
Ld = Нижняя граница размерности
d
Ud = Верхний связанный из размерности
d
CD = размер элемента массива
в байтах
Cd = Cd+1 ( Ud+1 – Ld+1
+ 1 ) для 1 <= d < D
C0 = B – C1L1 – C2L2
–…– CDLD
Первая строка входного файла содержит два положительных целых числа.Первое
число (N) описывает количество массивов, описанных во входном файле. Второе
число (R) задает количество элементов массивов, адреса которых должны быть
вычислены. Следующие N строк описывают каждая по одному массиву. Далее
идут R строк, в каждой из которых задан один элемент массива, адрес которого
нужно вычислить.
Каждая строка, описывающая массив, состоит из имени массива (максимальная
длина 10 символов), положительного целого числа, определяющего базовый
адрес массива, положительного целого числа, определяющего размер в байтах
элемента массива, и положительного целого числа, определяющего количество
размерностей в массиве (1<=D<=10). Далее в этой же строке идут D-пар
целых чисел, которые представляют нижние и верхние (соответственно) пределы
индексов размерности D массива.
Каждая строка, которая определяет элемент
массива, содержит имя массива за которым идут целые индексыi1,i2,…,iD,
где D - количество размерностей в массиве.
Для каждого, заданного во входном файле, элемента массива вывести одну
строку, содержащую имя элемента массива и его физический адрес. Форматировать
выводимые строки согласно следующим правилам.
Для каждой выводимой строки:
3 4
ONE 1500
2 2 0 3 1 5
TWO 2000
4 3 1 4 0 5 5 10
THREE
3000 1 1 1 9
ONE 2
4
THREE
7
TWO 2
0 6
TWO 3
3 9
ONE[2, 4]
= 1526
THREE[7]
= 3006
TWO[2,
0, 6] = 2148
TWO[3,
3, 9] = 2376
Файл программы:board.{c|cpp|pas|bas}
Входной файл:board.in
Вы - член группы программистов, чья задача состоит в том, чтобы написать
настольную игру. Вы пишите модуль, который определяет состояние игрового
поля и вычисляет все возможные варианты ходов для данного игрока. Игровое
поле представляет собой квадрат, разбитый сеткой 8х8 (как шахматная доска,
только все клетки одного цвета). Строки помечены сверху вниз буквами латинского
алфавита от 'A' до 'H'. Столбцы пронумерованы слева направо числами от
1 до 8.
Во время игры, каждый игрок может занимать от 1 до 12 клеток на игровом
поле. В клетках располагаются фишки одного типа.
Допустимые ходы определяются следующими правилами:
Входной файл состоит из одной или более задач. Каждая задача состоит из
описания игрового поля и строки-задания. Описание каждого поля состоит
из восьми строк. Каждая строка содержит восемь символов из набора '.' (точка),
'O' (большая латинская буква), 'X' (большая латинская буква). Точкой обозначены
пустые клетки игрового поля. Буквами - фишки соответствующих игроков.
Строка-задание содержит единственный символ 'O' или 'X' , говорящий
о том, ходы каких фишек нужно рассчитать.
Каждый возможный ход нужно описать на отдельной строке. Сначала выводятся
координаты исходной клетки, а затем, через черточку, координаты клетки
назначения. Координаты клетки состоят из имени строки и номера столбца.
Строки не должны содержать пробелов. Строки должны быть выведены по алфавиту,
в порядке возрастания. Если у игрока нет возможных ходов, выведите строку
"GAME OVER".
После решения каждой задачи выводите пустую строку.
O.......
O......X
O.....XX
O....XXX
.O...XXX
........
..O..XXX
........
O
..OXO...
..OOO...
........
........
........
........
........
........
X
A1-A2
A1-C3
A1-E1
B1-A2
B1-B3
B1-D3
B1-F1
C1-B2
C1-C4
C1-D2
C1-G1
D1-C2
D1-D5
D1-F3
D1-H1
E2-D2
E2-D3
E2-E6
E2-F1
E2-F2
E2-G4
G3-F2
G3-F3
G3-H3
G3-H4
GAME OVER
Файл программы:algebra.{c|cpp|pas|bas}
Входной файл:algebra.in
Автор школьного учебника по алгебре заказал Вам программу, решающую простые алгебраические уравнения. Она будет использоваться для тестирования примеров учебника. Автор подготовит текстовый файл с примерами. Все примеры будут в форме алгебраического уравнения, состоящего из целочисленных констант, четырех базовых арифметических операторов, знака равенства, и переменной. Например:
Для учебника необходимо, чтобы задача была решена пошагово. Для
примера, приведенного выше, такое решение выглядело бы так:
Множество действий, которые должна уметь производить Ваша программа,
ограничено целочисленными операциями умножения, деления, сложения и вычитания.
Действия производятся слева направо, в стандартном, для арифметических
операций, порядке. Гарантируется, что результатом деления будет целое число.
Входной файл будет содержать один или более примеров для решения. Каждый пример будет содержать от 2 до 21 целочисленных операндов. Операнды могут иметь ведущий знак. Пробелы в строке с примером являются факультативными; то есть они могут быть, а могут нет. Имя переменной состоит из алфавитных символов в количестве от 1 до 8.
Решение примера начинается с вывода самого примера. Затем выводится в отдельной строке результат выполнения каждой операции. Бинарные операторы и знак равенства должны быть окружены одиночными пробелами. Более пробелов быть не должно. Решение примера заканчивается выводом пустой строки.
3 * 4 + 4
1 / 1 = xyzzy
12 + 2
* 12 / 2 1 = y
2 * 3
+ 6 +4 = r
2*3+6+4=r
3 * 4 + 4
- 1 / 1 = xyzzy
12 + 4
- 1 / 1 = xyzzy
12 + 4
- 1 = xyzzy
16 - 1
= xyzzy
15 = xyzzy
12 + 2
* 12 / 2 - 1 = y
12 + 24
/ 2 - 1 = y
12 + 12
- 1 = y
24 - 1
= y
23 = y
2 * -3
+ -6 - 4 = r
-6 + -6
- 4 = r
-12 -
4 = r
-16 =
r
2 * -3
+ -6 - 4 = r
-6 + -6
- 4 = r
-12 -
4 = r
-16 =
r
Файл программы:semigrp.{c|cpp|pas|bas}
Входной файл:semigrp.in
Бинарная операция на множестве S - функция, которая назначает каждой упорядоченной паре элементов множества S один, уникальный элемент того же множества S. Для обозначения бинарной операции используются специальные символы (типа * или +). Например, если мы используем символ '#' для обозначения некоторой бинарной операции на множестве S = {a, b, c}, значение выражения a#b равняется некоторому элементу множества S (тоже справедливо для b#a, a#a, a#c, и любой другой возможной комбинации).
Из этого определения следует, что сложение, вычитание и умножение можно назвать операциями на множестве целых чисел. Деление (математическое, не целочисленное) – нельзя отнести к бинарным операциям на множестве целых чисел, так как например результат деления 1 на 2 не принадлежит к множеству целых чисел.
Использование слова упорядоченной в определении бинарной операции важно, так как результат операции a#b может отличаться от результата операции b#a. В случае с множеством целых чисел это очевидно на примере бинарной операции вычитания, так как например 5-3 не равно 3-5. Если в специфическом случае, x#y = y#x для всех элементов x и y из множества S, мы говорим, что бинарная операция коммутативна. Бинарная операция сложения, на множестве целых чисел - коммутативна.
В заключении, обратим внимание на маленькие множества (от 1 до 26 элементов). Для таких множеств бинарную операцию можно определить просто перечислив все возможные ее значения (таблица умножения). Например, бинарная операция '#' на множестве S = {a, b, c} могла бы быть определена так:
#|abc
-+---
a|bcb
b|acb
c|cba
В левом столбце таблицы находятся первые элементы упорядоченной пары, в верхней строке - вторые. Таким образом, в этом примере, a#b=c, b#a=a, и c#c=a. Тело таблицы состоит исключительно из элементов множества S, как и должно быть для любой бинарной операции. Обратите внимание, что операция # не коммутативна, так как b#a не равно a#b.
Бинарная операция #, на множестве S ассоциативна если (x#y)#z = x#(y#z) для всех элементов x, y, и z множества S. В примере с таблицей выше, операция не ассоциативна, так как (a#b)#c не равно a#(b#c). Если бинарная операция # на множестве S ассоциативна, то говорят что пара <S,#> образует полугруппу. Если бинарная операция еще и коммутативна, то говорят, что полугруппа коммутативна.
Напишите программу, которая будет читать элементы множества вместе с соответствующей “таблицей умножения” , задающей бинарную операцию. Ваша программа должна определить образует ли множество S с данной операцией полугруппу. Если множество и соответствующая операция не образуют полугруппу, ваша программа должна сообщить об этом и указать причину. Если полугруппа образуется, ваша программа должна проверить, является ли она коммутативной.
Таким образом, для каждого множества и соответствующей таблицы возможен один из следующих четырех результатов:
НЕ ПОЛУГРУППА: x#y=z,
ГДЕ z НЕ ЭЛЕМЕНТ МНОЖЕСТВА
НЕ ПОЛУГРУППА: (x#y)#z
НЕ РАВНО x#(y#z)
ПОЛУГРУППА, НО НЕ КОММУТАТИВНАЯ:
(x#y НЕ РАВНО y#x)
КОММУТАТИВНАЯ ПОЛУГРУППА
Для первых трех вариантов нужно подставить первые фактические элементы множества, иллюстрирующие справедливость Вашего вывода.
Входной файл состоит из одного или более описаний задач. Каждое описание
начинается со строки, содержащей единственное целое число n – количество
элементов множества (1<=n<=26).
Следующая строка входного файла будет содержать n уникальных, строчных
букв латинского алфавита. Они представляют собой элементы множества. Хотя
каждый символ уникален (не повторяется), они не обязательно размещены в
алфавитном порядке.
Следующие n строк содержат тело “таблицы умножения” , которая соответствует
элементам предыдущей строки. Каждая из этих строк будет содержать n строчных
букв латинского алфавита.
Входной файл заканчивается описанием задачи, у которой n = 0. Его обрабатывать
не надо.
Для каждой решенной задачи вывести:
3
abc
abc
bca
cab
3
abc
abc
bca
cad
4
acdb
aaaa
aaca
aada
aaab
5
abcde
aaaaa
bbabb
cccbc
ddddd
eeeee
0
S = {a,b,c}
#|abc
-+---
a|abc
b|bca
c|cab
КОММУТАТИВНАЯ ПОЛУГРУППА
------------------------------
S = {a,b,c}
#|abc
-+---
a|abc
b|bca
c|cad
НЕ ПОЛУГРУППА: c#c =
d, ГДЕ d НЕ ЭЛЕМЕНТ МНОЖЕСТВА
------------------------------
S = {a,c,d,b}
#|acdb
-+----
a|aaaa
c|aaca
d|aada
b|aaab
ПОЛУГРУППА, НО НЕ КОММУТАТИВНАЯ:
(c#d НЕ РАВНО d#c)
------------------------------
S = {a,b,c,d,e}
#|abcde
-+-----
a|aaaaa
b|bbabb
c|cccbc
d|ddddd
e|eeeee
НЕ ПОЛУГРУППА: (b#a)#c
НЕ РАВНО b#(a#c)
------------------------------
Файл программы:puzzle.{c|cpp|pas|bas}
Входной файл:puzzle.in
Вы должны написать программу, собирающую Jigsaw-puzzle (собрать исходное изображение из его фрагментов). Входной файл будет содержать размер Jigsaw-puzzle, размер фрагментов, и сами фрагменты. Фрагменты будут состоять из символов ASCII. Ваша программа должна собрать и вывести исходное изображение.
Первая строка входного файл будет содержать три целых числа N,H,W.
N - размер Jigsaw-puzzle , измеряемый в количестве фрагментов, из которых
состоит сторона изображения (это всегда квадрат NxN). Значения N находятся
в диапазоне от 2 до 10.
H и W - соответственно высота и ширина фрагмента изображения. Размеры
всех фрагментов одинаковы. Значения H и W находятся в диапазоне от 1 до
25.
Остальная часть файла описывает фрагменты изображения в произвольном
порядке. Каждое описание заканчивается строкой, содержащей четыре целых
числа в диапазоне от -5 до 5. Эти числа несут информацию о сторонах фрагмента,
соответственно верхней, левой, нижней и правой.
Если число равно 0, то соответствующая сторона фрагмента является частью
внешней стороны изображения. Если нет, то к ней примыкает сторона другого
фрагмента, помеченная тем же числом с противоположным знаком.
Все фрагменты будут прямоугольными блоками символов ASCII из диапазона
от 32 до 127. Помните, что символ
пробела (ASCII код 32) является равноправным символом изображения.
Выходной файл должен просто содержать решенную проблему в соответствующем расположении. Проблема будет иметь одним и только одно решение.
2 2 3
OOC
BCC
-2 2 0 0
AOO
AAB
5 0 0 -2
XXY
XOO
0 0 -5 -5
YZZ
OOZ
0 5 2 0
XXYYZZ
XOOOOZ
AOOOOC
AABBCC
2 8 14
88,
8888.
:8888b
8888
-.:888b
' d8888
,88888
':88888
0 3 -1 0
o8%88
o88%888
8'- -
8'
d8.-=. ,==
>8 `~` :`~
88
88b. `-~
0 0 -5 -3
.:88888
':::8888
::' 8888b
8888b
,%888b.
%%%8--'-.
_%-' --- -
..-' = --.
1 4 0 0
888b ~==~
88888o--:'
`88888| ::
8888^^'
d888
d88%
/88:.__
,
'''::===.
5 0 0 -4
o8%8888,
o88%8888888.
8'- -:8888b
8' 8888
d8.-=. ,==-.:888b
>8 `~` :`~' d8888
88 ,88888
88b. `-~ ':88888
888b ~==~ .:88888
88888o--:':::8888
`88888| :::' 8888b
8888^^' 8888b
d888 ,%888b.
d88%
%%%8--'-.
/88:.__
, _%-' --- -
'''::===..-' = --.
| Наверх
webmaster |
