Задача g6_1086: Степень 2 (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Для того чтобы проверить, как её ученики умеют считать, Мария Ивановна каждый год задаёт им на дом одну и ту же задачу - для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Формат входных данных
Во входном файле содержится единственное число A (1 9 - на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы "завалить" кого-нибудь... ).
Формат выходных данных
В выходной файл вывести единственное число N.
Примеры
f.in
8
f.out
4
f.in
13
f.out
13
Решение g6_1086:
Для решения этой задачи нам потребуются некоторые математические знания. Любое число можно представить в виде двух наборов чисел: один из них - его простые делители, другой в каждом элементе содержит степень этого делителя. Т.е. числу 12 будет соответствовать набор ((2, 3), (2, 1)) - 12 = 22 * 31.
Чтобы число (X) делилось на другое число (Y) необходимо, чтобы для каждого простого делителя степень этого делителя у числа X была больше либо равна степени того же простого делителя у числа Y.
Для начала разобьем число A на простые делители. Заведем два массива, в первом будем хранить значения простых делителей, а во втором - их степени (назовем этот массив k). Будем считать, что число 1 встречается 1 раз - занесем это до начала цикла, это поможет избежать отдельной обработки числа 1. Устроим цикл (i) от 2 до A и будем считать, какие и сколько делителей встречается.
При правильном выполнении этих операций мы получим два массива, по которым можно однозначно восстановить число.
Теперь посчитаем число K из которого затем будем получать число N. Т.к. в составлении числа N должны присутствовать все простые делители, которые имеет число A, то K будет равно произведению всех простых делителей числа A со степенью 1. Т.е. числу K будет соответствовать тот же массив простых делителей, что и числу A, а все их степени будут равны 1.
Устроим цикл (j) от 1 до A, в котором будем перебирать "дополнительный множитель" для числа K. Т.е. мы получаем рабочее N = K * j. Разобьем j на том же наборе простых делителей на степени (назовем этот массив nk) и проверим следующее условие: если для всех делителей (nk[i] + 1) * K * j >= k[i], то выводим число K * j - это и будет ответ, иначе переходим к следующему шагу цикла по j.
|
Задача g6_1087: Игра с фишками (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W*H клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
1. Путь должен состоять из отрезков вертикальных и горизонтальных прямых.
2. Путь не должен пересекать других фишек.
При этом часть пути может оказаться вне доски. Например:
Фишки с координатами (1,3) и (4,4) могут быть соединены. Фишки с координатами (2,3) и (5,3) тоже могут быть соединены. А вот фишки с координатами (2,3) и (3,4) соединить нельзя - любой соединяющий их путь пересекает другие фишки.
Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или "мнимых клеток", расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).
Формат входных данных
Первая строка входного файла содержит два натуральных числа: W - ширина доски, H - высота доски (1 1, Y1, X2, Y2, причём 1 1, X2 1, Y2 1, Y1) и (X2, Y2) - координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.
Формат выходных данных
Для каждого запроса необходимо вывести одно целое число на отдельной строке - длину кратчайшего пути, или 0, если такого пути не существует.
Примеры
g.in
5 4
XXXXX
X...X
XXX.X
.XXX.
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
g.out
5
6
0
g.in
4 4
XXXX
.X..
..X.
X...
1 1 3 1
0 0 0 0
g.out
4
Решение g6_1087:
Так как в решении задачи используются 32 битные компиляторы, то массив, содержащий описание доски, можно неизменным поместить в память. С его считыванием проблем не возникает (или не должно возникнуть). По краям доски, с каждой стороны, добавим ряд точек - это соответствует тому, что путь может пролегать за пределами доски.
Нашу доску можно представить в виде графа специального вида - где с каждой вершиной может быть связано не более четырех вершин - ее непосредственных соседей. Тогда наша задача сводиться к решению задачи нахождения кратчайшего пути между двумя вершинами невзвешенного графа, а для этого необходимо воспользоваться поиском в ширину.
Рассмотрим решение для одного запроса, естественно, что для других запросов оно будет полностью аналогичным.
Заведем еще один массив [Dist], совпадюащий по размерам с размерами доски и заполним все его элементы "бесконечностью"; каждый его элемент будет содержать количество ходов, необходимое, чтобы добраться от начальной клетки до данной. Естественно, что элемент, координаты которого совпадают с координатами начальной фишки, будет содержать ноль. Теперь временно "модернизируем" доску - значение элемента доски, соответствующее конечной фишке заменим на точку.
Теперь, для обхода графа в ширину, создадим очередь, поставим указатель головы и хвоста на 1, а в первый элемент занесем координаты начальной фишки. Теперь будем двигаться по очереди до тех пор, пока элемент очереди не будет содержать значение координат конечной фишки (т.е. кратчайший путь найден) или до тех пор, пока указатель на голову очереди не станет больше указателя на хвост - это означает, что все теоретически достижимые элементы очереди достигнуты.
На каждом шагу будем рассматривать элемент очереди, с координатами (X, Y). Т.к. элемент в очереди, то он достижим из начального за Dist[X, Y] ходов. Рассмотрим четыре соседних с ним элемента: если элемент лежит в пределах расширенной доски, свободен (т.е. элемент доски содержит точку) и расстояние до него равно бесконечности (он еще не рассмотрен), то его следует занести в очередь, а расстояние до него на единицу больше, чем у элемента из которого мы в него пришли.
Условия выхода уже описаны. Теперь осталось только вывести количество шагов (Dist[X2, Y2]) или 0, если Dist[X2, Y2] равно бесконечности. Восстановим доску, заменив точку в (X2, Y2) на X.
Задача g6_1088: Раскопки (Московская городская школьная олимпиада по программированию, заочный тур 2002-2003)
Во время недавних раскопок на Марсе были обнаружены листы бумаги с таинственными символами на них. После долгих исследований учёные пришли к выводу, что надписи на них на самом деле могли быть обычными числовыми равенствами. Если бы этот вывод оказался верным, это доказало бы не только то, что на Марсе много лет назад были разумные существа, но и то, что они уже умели считать:
Ученые смогли понять, что в этом случае означают найденные символы, и перевели эти равенства на обычный язык - язык цифр, скобок, знаков арифметических действий и равенства. Кроме того, из других источников было получено веское доказательство того, что марсиане знали только три операции - сложение, умножение и вычитание (марсиане никогда не использовали "унарный минус": вместо "-5" они писали "0-5"). Также ученые доказали, что марсиане не наделяли операции разным приоритетом, а просто вычисляли выражения (если в них не было скобок) слева направо: например, 3+3*5 у них равнялось 30, а не 18.
К сожалению, символы арифметических действий марсиане почему-то наносили специальными чернилами, которые, как оказалось, были не очень стойкими, и поэтому в найденных листках между числами вместо знаков действий были пробелы. Если вся вышеизложенная теория верна, то вместо этих пробелов можно поставить знаки сложения, вычитания и умножения так, чтобы равенства стали верными. Например, если был найден лист бумаги с надписью "18=7 (5 3) 2", то возможна такая расстановка знаков: "18=7+(5-3)*2" (помните про то, в каком порядке марсиане вычисляют выражения!). В то же время, если попался лист с надписью "5=3 3", то марсиане явно не имели в виду числового равенства, когда писали это:
Вы должны написать программу, находящую требуемую расстановку знаков или сообщающую, что таковой не существует.
Формат входных данных
Первая строка входного файла состоит из натурального (целого положительного) числа, не превосходящего 230, знака равенства, и последовательности натуральных чисел (не более десяти), произведение которых также не превосходит 230. Некоторые группы чисел (одно или более) могут быть окружены скобками. Длина входной строки не будет превосходить 80 символов, и других ограничений на количество и вложенность скобок нет. Между двумя соседними числами, не разделенными скобками, всегда будет хотя бы один пробел, во всех остальных местах может быть любое (в том числе и 0) число пробелов (естественно, внутри числа пробелов нет).
Формат выходных данных
В выходной файл необходимо вывести одну строку, содержащую полученное равенство (т.е., исходное равенство со вставленными знаками арифметических действий). В случае если требуемая расстановка знаков невозможна, вывести строку, состоящую из единственного числа "-1". Выходная строка не должна содержать пробелов.
Примеры
h.in
18=7 (5 3) 2
h.out
18=7+(5-3)*2
h.in
5=3 3
h.out
-1
Решение g6_1088:
Эту задачу можно решать множеством самых разнообразных способов, но мы остановимся на одном из самых простых, хотя, может быть, и не самом эффективном. Решение нашей задачи сводиться к рекурсивному перебору знаков - это не более 39 (менее 20000) вариантов и вычислению значения выражения для каждого варианта.
Именно задача вычисления выражения и является наиболее важной и трудоемкой. Мы воспользуемся модификацией так называемого "палочного метода" вычисления выражений. Для этого введем несколько правил замены. Т.е. если мы находим строку определенного вида, то заменяем ее на строку определенную правилом, поиск каждый раз начинаем с начала выражения.
'x+y' => 'z', где z=x+y
'x-y' => 'z', где x=x-y
'x*y' => 'z', где x=x*y
'(x)' => 'x'
Т.е. если мы встречаем два числовых операнда, между которыми стоит некоторый знак, то выделяем это выражение (назовем его "элементарным выражением", например, '12+35') и передаем его в процедуру, подчитывающую выражения такого простого вида (для примера она должна вернуть строку '47'), а затем заменяем в строке, содержащей выражение выделенную подстроку на результат вычислений. Если же встретился один числовой операнд, заключенный в скобки, то скобки следует удалить из строки - такое преобразование не изменяет значения выражения. Несложно проверить, что, используя эти правила, мы всегда получаем правильный результат.
Немного более подробно остановимся на алгоритме выделения элементарных выражений. Здесь можно воспользоваться методом конечных автоматов, введя автомат, имеющий следующие состояния:
1: жду начала выражения.
'0'..'9' - очищаем строку элементарного выражения, заносим текущий символ в строку элементарного выражения, переход в состояние 2.
другие символы - не выполняем никаких действий
2: ввод первого операнда.
'0'..'9' - добавляем текущий символ в строку элементарного выражения.
'+', '-', '*' - добавляем текущий символ в строку элементарного выражения, переход в состояние 3.
другие символы - переход в состояние 1.
3: проверка второго операнда.
'0'..'9' - добавляем текущий символ в строку элементарного выражения, переход в состояние 4.
другие символы - переход в состояние 1.
4: ввод второго операнда.
'0'..'9' - добавляем текущий символ в строку элементарного выражения.
другие символы - конец работы автомата, элементарное выражение найдено.
Автомат для удаления скобок, в которые заключен единственный операнд, написать еще проще.
Условие того, что выражение посчитано - не одно преобразование элементарного выражения не найдено. Т.е. осталось выражение вида 'x=y', где x и y - числа. Проверить его не представляет труда. В случае если равенство оказалось верным, следует вывести выражение с расставленными знаками (копию выражения, которое мы подсчитывали с помощью элементарных выражений).
Теперь об организации рекурсии. Вводимое выражение необходимо преобразовать, удалив все лишние пробелы, оставив только по одному пробелу между числами, перед скобкой и после скобки. Пробелы, перед первым и после последнего символа следует удалить.
Рекурсивная процедура должна искать в строке первый пробел, последовательно вставлять туда все возможные знаки и запускать следующую процедуру. В случае если пробелов найти не удалось, следует запускать проверку выражения. После работы процедуры на том месте, где она осуществляла вставку, следует восстанавливать пробел.
Теперь осталось только корректно обработать отсутствие решения.
Задача g6_1089: Эксперимент (V Московская командная студенческая олимпиада по программированию 2002)
Результат эксперимента представляет из себя матрицу из 0 3. Отвечающим условиям эксперимента считаются такие подматрицы размера K строк и L столбцов (0
Требуется определить, сколько подматриц в исходной матрице отвечают условиям эксперимента.
Например, в матрице 3*3, состоящий из единиц, подматрицы размера 2*2 с суммой 4 встречаются 4 раза.
Входные данные:
В первой строке стандартного потока ввода находятся 5 чисел N, M, K, L и S, разделенные пробелами. В каждой из следующих N строк находится по M чисел, разделенных пробелами, являющихся элементами матрицы (целые числа, по модулю не превосходящие 30000 [здесь, возможно, опечатка, т.к. в описании сказано, что каждый элемент не превосходит 1000. М.Г.]).
Результат:
В выходной поток записывается одно число - количество подматриц размера K*L, сумма элементов в которых равна S.
Пример:
Входные данные:
3 3 2 2 4
1 1 1
1 1 1
1 1 1
Результат:
4
Решение g6_1089:
Несложно понять, что для решения этой задачи используется динамическое программирование. Действительно, будем использовать дополнительную матрицу такого же размера, в каждом элементе которой будем хранить сумму всех элементов, лежащих не ниже и не правее данного. Пусть A - исходная матрица, B - преобразованная (она может совпадать с A, как мы увидим в дальнейшем элементы матрицы A не понадобятся нигде, кроме как при составлении матрицы B). Тогда B[x,y] = sum[i=1,x](sum[j=1,y](A[i,j])).
Чтобы ускорить процесс воспользуемся тем, что B[x,y] = A[x,y] + B[x-1,y] + B[x,y-1] - B[x-1,y-1]. Для облегчения подсчетов, создадим "барьер" вокруг матрицы B, шириной 1 и заполненный нулями (т.е. создадим нулевые строку и столбец в матрице B и заполним их нулями). Теперь у нас есть матрица B, в которой хранятся суммы. Допустим, мы хотим проверить, является ли точка (x,y) - верхним левым краем искомой подматрицы. Если это так, то должно выполняться условие: B[x,y] + B[x+K,y+L] - B[x,y+L], - B[x+K,y] = S. Теперь достаточно пройти циклом по всем возможным правым углам подматриц и определить, сколько из них удовлетворяют условию.
Задача g6_1090: Кубооктаэдр (XVII Кировская областная олимпиада по информатике).
Возьмем кубик и приклеим к его граням еще по такому же кубику. В результате получим фигуру, представленную на втором рисунке. К свободным граням полученной фигуры, приклеим еще кубики. На рисунке представлены "кубооктаэдры" степеней 0, 1, 2.
Кубооктаэдром степени N назовем фигуру, полученную в результате N-го доклеивания кубиков. Составить программу, подсчитывающую, количество кубиков для кубооктаэдра N-й степени(1
Решение g6_1090: (предоставлено Ефремовым Алексеем)
Чистая арифметика! Обозначим за h высоту некоторого кубооктаэдра. Несложно заметить, что при увеличении степени фигуры, h возрастает в арифметической прогрессии с разностью 2.
Также очевидно, что любой кубооктаэдр степени n можно условно разбить на 2*n+1 уровня, где n-его степень. Кол-во уровней есть всегда нечётное число, поэтому мы можем выделить серединный уровень. Также назовём единичным, уровень, содержащий только один кубик. Рассмотрим кубооктаэдр степени 1. Его мы можем условно разделить на три уровня(т. к любой уровень кубооктаэдра имеет лишь один слой кубиков, далее для простоты мы будем работать только с его проекцией на плоскость):
Итак, для того чтобы получить кубооктаэдр следующей степени нужно доклеить к каждой грани каждого уровня по кубику, а также прибавить еще два единичных уровня.
Кубооктаэдр 2-й степени:
Осталось подсчитать кол-во добавленных кубиков в очередной степени кубооктаэдра(t) и прибавить их кол-во к общей сумме. Для этого нам потребуется знать кол-во кубиков в серединном уровне(q) и высоту(h) предыдущей степени кубооктаэдра. Если внимательно взглянуть на оба разбиения(см. выше) всплывает красивая формула для нахождения t: t=2*q+h*2+2.
Процедура подсчёта кол-ва кубиков приведена ниже:
procedure solve(const k:longint{степень кубооктаэдра}; var r:extended{кол-во кубиков});
var h{высота},q{кол-во кубиков на серед. уровне}:extended;
i:longint;
begin
h:=1; r:=1; q:=1;
for i:=2 to k do begin
r:=r+2*q+h*2+2; {t=2*q+2*h+2}
inc(q,h*2+2);
inc(h,2);
end;
end;
Следует отметить, что ограничение 0 Turbo Pascal 7.0):
writeln(output,r:0:0);
Задача g6_1091: Бусинки (XII Кировская областная олимпиада по информатике).
Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер - целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых фигур не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой.
Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре (на рисунке эти бусинки выделены темным цветом).
Входной файл: input.txt
В первой строке - количество бусинок . В последующих строках по два целых числа - номера, соединенных бусинок.
Выходной файл: output.txt
Вывести одно число - искомое количество бусинок.
Пример:
Входной файл
7
4 5
6 7
7 4
7 2
1 3
4 1
Выходной файл
5
Решение g6_1091: (предоставлено Ефремовым Алексеем)
Предположим, что мы уже имеем массив [1..N,1..2], где [i,1], [I,2]-длины максимальных веток, исходящих из i-той вершины, причём условимся, что [i,1]>=[I,2] (это потребуется в дальнейшем). Например, на рисунке для 4-ой вершины это 2 и 2. для 1-ой 1 и 3. Понятно, что в этом случае мы без труда сможем определить искомую величину - максимальное количество последовательно соединённых бусинок:
max:=0;
for i:=1 to s[0,2] do
if s[i,1]+s[i,2]>max then max:=s[i,1]+s[i,2];
inc(max);
Осталось вычислить этот массив. Всё, что нужно для этого - грамотно пустить рекурсию. Также нужно заметить, что если мы программируем в Turbo Pascal 7.0(именно так и было на олимпиаде), мы не можем создать матрицу смежности требуемого размера. Придётся обойтись списком связей, который прекрасно поместится в отведённую память(т.к. граф не имеет циклов). Для этого придётся использовать динамические структуры(опять же из-за памяти). Также создадим ещё один массив этого типа(log), где i-тый элемент - указатель на просматриваемую на i-том шаге рекурсии в данный момент вершину(т.е. фактически значение log[i] будет продвигаться от 1-го до последнего элемента в исходном списке связей(x[i])). Ещё введём булевский массив p, i-тый элемент которого показывает, просмотрена ли i-тая вершина или нет.
Запускаем рекурсию начиная с первой вершины и на каждом шаге двигаясь по списку связей (а точнее изменяя значения log) вызываем эту же процедуру ,естественно с параметром равным log[i] (i-текущий параметр процедуры) в данный момент. Далее при возвращении обратно, проверяем, есть ли ветка у log[i]-го элемента, которая длиннее, чем какая-нибудь ветка у i-го элемента, если это так, то соответствующим образом модифицируем массив веток(sol).
Процедура будет выглядеть примерно так:
{первоначально log=исходный список связей; p-все элементы false}
procedure solve( i:integer);
begin
p[k]:=false;
while log[i]nil do begin
if p[log[i]^.data] then begin
solve(log[i]^.data);
if s[log[i]^.data,1]>=s[i,1] then begin
q:=s[I,1];
s[i,1]:=s[log[i]^.data,1]+1;
s[i,2]:=q
end
else
if s[log[i]^.data,1]>=s[i,2] then
s[i,2]:=s[log[i]^.data,1]+1
end;
log[i]:=log[i]^.next;
end;
end;
Осталось заметить, что массив s не всегда будет содержать все присутствующие ветки для всех вершин, но для элемента с максимальной суммой вершин в ветках, значение будет определено обязательно.
Задача g6_1092: Пары слов (Самарская областная олимпиада по информатике 2001).
Входной файл содержит набор слов (словом считается последовательность символов, не содержащая символа перевода строки). 1-я буква может быть как заглавной, так и строчной, остальные - строчные. Пусть некоторая последовательность букв встречается в обоих словах (регистр букв учитывается).
Процентом совпадения назовем максимальную длину такой последовательности, деленную на длину более короткого из этих слов, умноженную на 100% и округленное до ближайшего целого. Требуется распределить слова по парам, так чтобы суммарный процент совпадения для всех пар был наибольшим.
|