Вася продолжает изобретать последовательности. Сегодня в школе его познакомили с операцией возведения в степень, и Вася придумал новую последовательность.
Сначала он пишет на доске натуральное число \(A\). Каждое следующее число, выписанное им на доске, будет равно степени с основанием \(A\) и показателем, равным предыдущему числу. Другими словами, последовательность будет выглядеть так:
\(x[1] = A\),
\(x[k + 1] = A^{x[k]}\), \(k\) > 0
После этого он решил узнать элемент этой последовательности с минимальным номером, который бы делился на данное число \(N\). Поскольку числа на доске могут быть довольно большими, без вашей помощи ему не обойтись.
Вводятся два натуральных числа \(A\), \(N\) (\(1\) ≤ \(A\) ≤ \(10^9\), \(1\) ≤ \(N\) ≤ \(10^9\)).
Если ни один элемент последовательности не делится на \(N\), выведите 0. Иначе выведите минимальный номер элемента рассмотренной последовательности, делящегося на \(N\).
2 2
1
2 4
2
Самолёт вылетает из города А в \(h_1\) часов \(m_1\) минут по местному времени города А и прилетает в город Б в \(h_2\) часа \(m_2\) минуты (по местному времени города Б). Из города Б он вылетает в \(h_3\) часа \(m_3\) минуты (по местному времени города Б, возможно в другие сутки) и прилетает в город А в \(h_4\) часа \(m_4\) минуты (по местному времени города А). При этом полёт в обе стороны продолжается одно и то же время. Сколько длится полет в одну сторону? Ответ нужно вывести в часах и минутах, округлив его при необходимости до целого числа минут в большую сторону.
В каждой из четырех строк в формате hh:mm записаны времена вылета и прилета в том порядке, в котором они перечислены в условии; 0 ≤ \(h_j\) < 24, 0 ≤ \(m_j\) < 60.
Выведите время полёта в том же формате hh:mm. Если ответов несколько, выведите минимальный.
08:00 10:00 12:00 18:00
04:00
00:00 00:00 23:59 01:30
00:46
Один из столичных девелоперов решил построить жилой дом по проекту известного авангардного архитектора. Жилой дом будет состоять из квартир-кубиков и иметь причудливую форму. Есть два ограничения, одно из которых наложено архитектором, а второе — законами физики.
Архитектор хочет, чтобы каждый этаж представлял собой связанную последовательность кубиков (разделенные этажи — это мода 1990х). В то же время необходимо, чтобы хотя бы под одним из кубиков этажа находился кубик предыдущего этажа. Первый этаж должен опираться о землю.
Кроме законов физики архитектора ограничивает также необходимость все это творчество продать. Поскольку покупатели неохотно покупают недвижимость, необходимо привлечь их хоть чем-нибудь, в частности, видом из окна. Специалисты компании-девелопера составили таблицу, в которой для каждого возможного расположения квартиры указана привлекательность вида из окна для этого расположения. Необходимо максимизировать суммарную привлекательность видов из окна.
В приведенном примере показаны привлекательности видов из окна и наилучшее здание из 10 кубиков в данном случае.
По известному количеству кубиков и таблице привлекательности видов из окна вам необходимо выбрать лучший проект (с максимальной суммарной привлекательностью), удовлетворяющий условиям архитектора и законам физики.
В первой строке входного файла указаны натуральные числа \(N\), \(H\) и \(W\) (1 ≤ \(H\) ≤ 30, 1 ≤ \(W\) ≤ 30, 1 ≤ \(N\) ≤ \(HW\)) — количество имеющихся кубиков, максимальная высота и максимальная ширина здания. Следующие H строк содержат по \(W\) натуральных чисел, задающих привлекательность соответствующего расположения квартиры. Привлекательность измеряется в пределах от 1 до 100 000 включительно.
Выведите одно число — наибольшую суммарную привлекательность.
10 6 7 9 3 6 4 8 1 3 2 9 2 5 3 2 6 1 1 8 4 6 5 4 1 9 6 5 3 4 5 6 2 5 6 7 1 2 2 6 7 5 6 4 3
65
Новый кодовый замок для владельцев нетбуков представляет головоломку не только для грабителей, но и для владельцев. На табло замка все время высвечивается некоторая комбинация нулей и единиц. Замок откроется, если на табло высветится некоторая определенная комбинация. Получить требуемую комбинацию из текущей можно нажимая в нужной последовательности кнопки, на которых написано 0 и 1 соответственно.
Если нажать кнопку с нулем, то текущая комбинация на табло сдвигается на одну позицию вправо (правая цифра при этом исчезает), а в самом левом разряде записывается 0. При нажатии на кнопку с единицей происходит то же самое, только в левый разряд записывается 1.
Известно, какая комбинация цифр сейчас находится на табло, и какую комбинацию требуется получить, чтобы открыть замок. Помогите владельцу нетбука — определите, за какое минимальное количество нажатий на кнопки можно получить требуемую комбинацию.
Первая строка содержит текущую последовательность цифр, вторая строка — последовательность, которую требуется получить. Гарантируется, что обе последовательности не пустые, имеют одинаковую длину, не превосходящую 100 000, и состоят только из нулей и единиц. Цифры в строках записаны подряд (без пробелов).
Выведите минимальное количество нажатий на кнопки, с помощью которого можно решить поставленную задачу.
1101 1011
2
0000 1111
4
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
|
|
|
Вася — начинающий программист. Последней его идеей было написать графический редактор черно-белых изображений. К сожалению, вдохновения хватило только на один инструмент — заливку.
В окне редактора картинка отображается как прямоугольная таблица M × N клеток; каждая покрашена либо в чёрный, либо в белый цвет. Две клетки назовём соседними, если у них имеется общая сторона. Областью же будем называть максимальное подмножество клеток одного цвета, такое, что из каждой можно попасть в каждую, перемещаясь только по соседним клеткам этой области.
Заливка работает следующим образом: пользователь указывает на произвольную клетку таблицы, после чего вся область, содержащая данную клетку, перекрашивается в противоположный цвет.
Теперь Вася хочет научиться стирать изображения с помощью своего редактора. Картинка считается чистой, если она либо полностью чёрная, либо полностью белая. Определите минимальное число заливок, которое потребуется для того, чтобы сделать из данного изображения чистое.
Формат входных данных
Вводятся два натуральных числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — количество строк и столбцов у таблицы, соответствующей данному изображению. В следующих N строках содержатся по M символов. В i‑й строке и j-м столбце стоит 0, если соответствующая клетка белая, и 1, если чёрная.
Формат выходных данных
Выведите одно число — минимальное количество заливок, требуемых для стирания данной картинки.
Пример
| Входные данные | Выходные данные |
| 3 5 10101 01010 10101 | 3 |