Задача A. Hot-keys
Условие
Когда вы проектируете дизайн всплывающих диалоговых форм для интерактивных программ,
важно назначить горячие клавиши (так же известные как клавиши быстрого доступа) на каждый элемент
диалогового окна для ускорения работы через клавиатуру.
Для придания смысла, горячие клавиши, как правило, назначаются на основании первых букв в заголовке/названии активных элементов диалога.
Ручное назначение горячих клавиш может быть утомительным занятием и не защищено от ошибок,
т.к. необходимо следить за тем, чтобы случайно не назначить одну и ту же клавишу на разные элементы.
Вашей программе подается на вход список заголовков.
Она должна будет назначить столько уникальных горячих клавиш, сколько вообще возможно.
Каждая назначенная горячая клавиша должна быть символом соответсвующего заголовка элемента.
Для каждой комбинации позицией считается самое крайнее от начала строки (заголовка элемента) появление символа горячей клавиши.
Из всех возможных решений с одинаковым количеством горячих клавиш,
ваша программа должна выбрать единственное с минимальной суммой позиций горячих клавиш.
Если решений с такой минимальной суммой несколько, то выведите любое из них.
Формат входного файла
Входной файл содержит количество заголовков N, за которым следует N строк с названиями заголовков.
Формат выходного файла
Выходной файл должен содержать N строк с одинаковыми заголовками, как и во входном файле.
В каждом заголовке, которому была назначена какая-то комбинации, перед самым левым вхождением символа из горячей клавиши
необходимо добавить символ '&' (ASCII 38).
Ограничения
1 ≤ N ≤ 10, все заголовки имеют длину от 1 до 10 символов и состоят из строчных латинских букв.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
yes
no
cancel
|
&yes
&no
&cancel
|
| 2 |
4
abc
bca
acb
aaaa
|
&abc
&bca
a&cb
aaaa
|
Задача B. Двойные тетради Чебурашки
Условие
Пришла осень, каникулы закончились, и Чебурашке снова нужно идти в школу.
Он заранее готовился к этому: накупил карандашей, ручек, тетрадей.
Среди покупок, кроме обычных тетрадей, были также и двойные,
каждая из которых предназначена сразу для двух предметов.
Каждый день Чебурашке нужно брать с собой тетради для всех предметов,
которые будут преподаваться в его классе в этот день.
Тетради тяжелые, а носить лишний вес в школу не хочется.
Поэтому он пытается распределить предметы по тетрадям таким образом,
чтобы за неделю переносить наименьший возможный вес.
Помогите ему это сделать.
У Чебурашки есть NS одинарных и ND двойных тетрадей.
Все одинарные тетради имеют вес WS, а все двойные — вес WD.
Чебурашка учится N дней в неделю.
Он изучает M предметов, пронумерованных от 1 от M.
Вес, который Чебурашке придётся перенести за один день,
равен сумме весов всех тетрадей, которые он должен будет взять.
Требуется написать программу, вычисляющую наименьший возможный вес,
который Чебурашке придется перенести в сумме за все дни недели.
Формат входного файла
Во входном файле содержатся числа N M NS ND WS WD.
Далее следует расписание, состоящее из N дней.
Каждый день описывается одной строкой.
В начале строки содержится Ki — число уроков в i-ый день,
за которым следует Ki чисел — номера предметов.
Все числа во входном файле целые.
Формат выходного файла
В выходном файле должно содержаться единственное число — минимальный возможный вес.
Ограничения
0 ≤ N ≤ 6
0 ≤ M ≤ 10
0 ≤ WS, WD ≤ 109
0 ≤ K1 + K2 + … + KN ≤ 15
2 × ND + NS = M
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
4 4 0 2 2 2
2 1 2
2 3 4
2 1 2
2 3 4
|
8
|
| 2 |
4 4 2 1 0 2
2 1 2
2 3 4
2 1 2
2 3 4
|
4
|
Problem C. Radio Coverage
Statement
Radio station 'ACM Rock' is broadcasting over the circular area with center in point
(x0, y0) and radius R.
In order to increase the auditorium, it were suggested to build several relay stations.
N locations were selected as candidate sites for relay stations.
Relay station placed in i-th location will cover a circular area with center
in point (xi, yi) and radius ri,
where center lies inside the area covered by the base station,
(x0 - xi)2 +
(y0 - yi)2 ≤ R2.
Your task is to select a subset of sites for relay stations so that:
- the covered areas for relays do not intersect (but may touch) one another,
- the total area covered by base station and all relays is maximum possible.
Input file format
Input file contains integer number
N followed by real numbers
x0 y0 R, followed by
N
triples of real numbers
xi yi ri.
Output file format
Output file should contain a single real number — the maximal coverage area with the
absolute error less than 10
−2.
Constraints
1 ≤
N ≤ 10,
0 ≤
xi,
yi,
x0,
y0 ≤ 1000,
1 ≤
ri ≤
R ≤ 1000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
1 0 0 10
10 0 10
|
505.4816
|
Problem D. Divide by Squares
Statement
Divide by Squares is played on a rectangular grid.
Some of the squares in the grid are numbered.
The objective is to divide the grid into rectangular
and square pieces such that each piece contains exactly one number,
and that number represents the area of the rectangle (from Wikipedia).
On the pictures you can see a sample of the puzzle and its solution.
You are to write program that solves this puzzle.
Input file format
The first line of the input file contains three integers,
separated by spaces — the height
H, the width
W of the grid,
and total amount
K of numbers on the grid.
Each of the next
K lines contains three integers,
separated by spaces — position
(i, j) of the number and the number itself.
The puzzle in the input has at least one solution.
Output file format
The output file must contain
K lines.
For each number in the input you should print four integers on corresponding line —
coordinates of left upper corner of the rectangle that contains
this number and its height and width. You have to print arbitrary solution.
Constraints
1 ≤ H ≤ 10, 1 ≤ W ≤ 10, 1 ≤ K ≤ W*H
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
4 4 4
2 1 4
2 3 6
3 1 4
4 4 2
|
1 1 2 2
1 3 3 2
3 1 2 2
4 3 1 2
|
