Problem A. Hot-keys
Statement
When designing dialog forms for interactive programs, it is important
to assign hot-keys (known also as accelerator keys) to each
dialog element, so as to facilitate keyboard input.
For better mnemonics, hot-keys are assigned based on the letters
of dialog elements' captions,
usually favoring letters near the beginning of caption.
Manual hot-keys distribution can be tedious and error-prone,
as one must be careful not to assign same letter to different elements.
Your program will be given a list of captions.
It must assign unique hot-keys to as many captions of possible.
Each assigned hot-key must be a letter from the corresponding caption.
For each hot-key, position is the leftmost occurrence of the hot-key letter
in the corresponding caption.
From all solutions with the same numbers of hot-keys,
your program must choose the one with minimal sum of hot-key positions.
If there is still more than one optimal solution, output any of them.
Input file format
Input file contains number of captions N followed by N lines with captions.
Output file format
Output file must contain N lines with the same captions as in input.
In those captions which have hot-key assigned, leftmost occurrence
of hot-key letter must be preceded with '&' (ASCII 38).
Constraints
1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and
consist of small Latin letters.
Sample tests
| No. |
Input file (input.txt) |
Output file (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
|
