Задача 1. "Артефакты" (45 баллов)
Исходный текст программы: Ann.PAS | Ann.C | Ann.CPP | Ann.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест.
Известен план плоского прямоугольного лабиринта, в котором лежат артефакты. Лабиринт состоит из N*M одинаковых квадратов, часть из которых заняты стенами. Лабиринт имеет несколько входов (не обязательно на границах лабиринта). Перемещаться в лабиринте можно только по горизонтали или по вертикали, переходя из одного свободного (не занятого стеной) квадрата в другой. В лабиринт можно попасть через любой вход, но выходить за пределы лабиринта не разрешается. Напишите программу, которая определяет, какое максимальное количество артефактов можно собрать за одно посещение лабиринта, и каким входом следует для этого воспользоваться.
Вход. Входной файл содержит несколько строк. В первой строке записаны целые числа N и M - размеры лабиринта по вертикали и по горизонтали (1 <= N, M <= 100). В следующих N строках записан план лабиринта. Каждая из этих строк содержит ровно M символов '.' (точка), 'x' (икс), 'A' (заглавная латинская A) или 'E' (заглавная латинская E). Точка обозначает свободный квадрат, 'x' - стену, 'A' - артефакт (он всегда лежит в свободном квадрате) и 'E' - вход в лабиринт. Лабиринт имеет не более 10 входов.
Выход. В выходной файл следует записать максимальное количество артефактов, которые можно собрать за одно посещение лабиринта, и координаты ( x, y ) входа, которым следует для этого воспользоваться. Координаты отсчитываются от левого верхнего угла лабиринта начиная с единицы. Если нельзя собрать ни одного артефакта, запишите в файл одно число 0 (ноль).
Примеры входа и выхода
|
input.txt |
output.txt |
|
3 5 |
3 1 2 |
|
.Ax.. |
|
|
ExxxA |
|
|
...A. |
|
|
input.txt |
output.txt |
|
4 7 |
1 4 1 |
|
AAxExAA |
|
|
xxxAxAA |
|
|
.E.x.x. |
|
|
.....Ex |
|
Задача 2."Треугольник" (15 баллов)
Исходный текст программы: Cnn.PAS | Cnn.C | Cnn.CPP | Cnn.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест
Дан треугольник из чисел. Напишите программу, которая находит наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника. Каждый шаг может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
Вход. Входной файл содержит несколько строк. В первой строке записано целое число N (1<=N<=100) - количество строк треугольника. В следующих N строках файла содержатся строки треугольника, состоящие из 1, 2, ..., N чисел. Все числа целые и не превосходят по модулю 1000000.
Выход. В выходной файл следует вывести найденную максимальную сумму.
Примеры входа и выхода
|
input.txt |
output.txt |
|
3 |
11 |
|
1 |
|
|
2 3 |
|
|
5 7 6 |
|
|
input.txt |
output.txt |
|
5 |
37 |
|
1 |
|
|
2 3 |
|
|
5 7 6 |
|
|
-11 -3 0 9 |
|
|
40 1 2 3 4 |
|
Задача 3. "Охота на слонопотамов" (25 баллов)
Исходный текст программы: Bnn.PAS | Bnn.C | Bnn.CPP | Bnn.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест
Пух и Пятачок решили поохотиться на слонопотамов. Как известно, каждый слонопотам ходит каждую ночь на водопой по одной и той же тропе. Эти тропы пересекаются на лесных полянах. Способ охоты на слонопотамов вам, конечно, известен: надо вырыть глубокую яму, в которую провалится слонопотам. Пух и Пятачок не очень сильные животные, поэтому они решили выкопать всего одну яму, но выбрать для этого такую поляну, чтобы в яму упало максимально возможное количество слонопотамов. Напишите программу, которая поможет Пуху и Пятачку определить наилучшее место для копания.
Вход. Входной файл содержит несколько строк. В первой строке записаны целые числа N - количество слонопотамов, проживающих в лесу, и M - количество полян, пригодных для копания ям (0<=N<=1000, 1<=M<=1000). В следующих N строках записаны маршруты движения слонопотамов (по одной строке на каждого). Каждая такая строка содержит целое число K - количество полян на пути слонопотама (1<=K<=100), а затем K номеров полян Pi, i=1,...,K, через которые проходит данный слонопотам (1<=Pi<=M). Не забудьте, что слонопотам осторожен и может проходить много раз через одну и ту же поляну, прежде чем приблизиться к воде.
Выход. В выходной файл следует записать максимальное количество слонопотамов, которых можно поймать, и номер поляны, на которой следует копать яму. Если решений несколько, выведите любое из них.
Примеры входа и выхода
|
input.txt |
output.txt |
|
3 5 |
2 2 |
|
4 1 2 1 3 |
|
|
2 2 4 |
|
|
1 5 |
|
|
input.txt |
output.txt |
|
4 7 |
4 2 |
|
12 1 2 3 1 2 3 1 2 3 1 2 3 |
|
|
4 6 6 2 6 |
|
|
5 7 7 7 7 2 |
|
|
7 2 4 6 2 4 6 2 |
|
Задача 4. "Круги" (10 баллов)
Исходный текст программы: Dnn.PAS | Dnn.C | Dnn.CPP | Dnn.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест
На плоскости нарисованы N кругов и M точек. Напишите программу, которая находит круг, внутри которого находится наибольшее количество точек (если точка находится на окружности, она тоже считается находящейся внутри круга).
Вход. Входной файл содержит несколько строк. В первой строке записаны числа N и M (1<=N<=1000, 0<=M<=1000). В следующих N строках записано по три целых числа Xi, Yi, Ri - координаты центра и радиус i-го круга (-10000<=Xi, Yi<=10000, 0<=Ri<=10000). И в последних M строках записано по два целых числа Xj, Yj - координаты j-ой точки (-10000<=Xj, Yj<=10000).
Выход. В выходной файл следует записать номер круга, в котором содержится наибольшее количество точек. Если решений несколько, выведите наименьший номер.
Примеры входа и выхода
|
input.txt |
output.txt |
|
2 5 |
2 |
|
0 0 3 |
|
|
1 5 4 |
|
|
1 -2 |
|
|
-1 3 |
|
|
0 5 |
|
|
2 2 |
|
|
4 1 |
|
|
input.txt |
output.txt |
|
2 0 |
1 |
|
1 1 1 |
|
|
2 2 2 |
|
Задача 5. "Копилка" (45 баллов)
Исходный текст программы: Enn.PAS | Enn.C | Enn.CPP | Enn.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест
Для того, чтобы начать свой бизнес и разбогатеть, Юра В. решил накопить денег. Он нашел свинью - копилку и начал собирать деньги. Известно, что определить накопленную сумму в копилке можно, только разбив копилку. Однако Юра не хочет делать этого, пока там не накопилась требуемая сумма. Помогите Юре оценить минимальное количество денег внутри копилки, зная ее вес без монет, вес с монетами и вес монет каждого типа.
Вход. Входной файл содержит несколько строк, в первой строке записано три целых числа: V - вес пустой копилки, W - вес копилки с монетами и N - количество разных типов монет (1<=V<=W<=10000, 1<=N<=100). В следующих N строках записаны по два целых числа - достоинство монеты Cj и вес монеты Pj (1<=Cj<=50000, 1<=Pj<=10000).
Выход. В выходной файл следует вывести минимальную сумму денег, которая может находиться в копилке. Если заданный вес копилки не может быть достигнут с монетами заданного типа, то запишите в выходной файл число -1 (минус единица).
Примеры входа и выхода
|
input.txt |
output.txt |
|
10 110 2 |
60 |
|
1 1 |
|
|
30 50 |
|
|
input.txt |
output.txt |
|
10 110 2 |
100 |
|
1 1 |
|
|
50 30 |
|
|
input.txt |
output.txt |
|
1 6 2 |
-1 |
|
10 3 |
|
|
20 4 |
|
Задача 6. "N в степени N" (10 баллов)
Исходный текст программы: Fnn.PAS | Fnn.C | Fnn.CPP | Fnn.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест
Дано натуральное число N. Требуется вычислить число NN (N в степени N). Если честно, то само это число никому не нужно, достаточно лишь знать остаток от деления NN на заданное натуральное число K. Напишите программу, которая по заданным N и K вычисляет остаток от деления NN на K.
Вход. Входной файл содержит числа N и K (1<=N<=100000, 2<=K<=10000).
Выход. В выходной файл следует записать полученный остаток от деления.
Примеры входа и выхода
|
input.txt |
output.txt |
|
4 7 |
4 |
|
input.txt |
output.txt |
|
7 10 |
3 |
Задача 7. "Строки" (10 баллов)
Исходный текст программы: Gnn.PAS | Gnn.C | Gnn.CPP | Gnn.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест
Даны две последовательности символов A и B одинаковой длины. Напишите программу, которая определяет, можно ли, меняя местами символы в последовательности A, получить из нее последовательность B.
Вход. Входной файл содержит три строки. В первой строке записана длина последовательностей N (1<=N<=100000). Во второй строке записана последовательность A и в третьей строке - последовательность B. Последовательности состоят только из маленьких латинских букв 'a'..'z'.
Выход. В выходной файл следует записать слово "yes", если из A можно получить B, и слово "no" в противном случае.
Примеры входа и выхода
|
input.txt |
output.txt |
|
1 |
no |
|
f |
|
|
e |
|
|
input.txt |
output.txt |
|
5 |
yes |
|
cabar |
|
|
barac |
|
Задача 8. "Малый и средний бизнес" (40 баллов)
Исходный текст программы: Hnn.PAS | Hnn.C | Hnn.CPP | Hnn.BAS
Входной файл: INPUT.TXT. Выходной файл: OUTPUT.TXT.
Ограничение по времени: 1 секунда на тест
Фирма "Пупкин и сыновья" занимается ремонтом жилья. Она заключила N контрактов. В каждом контракте указана его стоимость Si и предельный срок окончания работ Di. За каждый просроченный день фирма обязана уплатить заказчику неустойку P. Кроме того известно количество дней Ti, необходимое для выполнения каждого контракта. Отказаться от выполнения работ фирма не может, и теперь Пупкины тревожатся - удастся ли им избежать банкротства.
Напишите программу, которая вычисляет максимальную сумму, которую может получить фирма, выполнив все контракты.
Вход. Входной файл содержит несколько строк. В первой строке записаны целые числа N (0<=N<=10000) и P (0<=P<=100). В следующих N строках записано по три целых числа Si, Di и Ti (0<=Si<=10000, 0<=Di<=1000, 1<=Ti<=1000).
Выход. В выходной файл следует записать максимальную сумму, которую может получить фирма (учтите, что эта сумма может быть и отрицательной из-за уплаты неустоек).
Примеры входа и выхода
|
input.txt |
output.txt |
|
3 10 |
817 |
|
550 10 3 |
|
|
170 10 3 |
|
|
97 10 3 |
|
|
input.txt |
output.txt |
|
3 100 |
-120 |
|
35 1 1 |
|
|
45 1 1 |
|
|
100 1 1 |
|