Задачи личных соревнований по спортивному программированию 2016

Стэну нравятся числа, которые одновременно являются кубами и квадратами. Он считает их крутыми. Например, крутым является число 64, так как `64=4^3=8^2`.

Ввод содержит одно целое число `X` (`1\ ≤\ X\ <\ 10^18`).

Выведите минимальное крутое число, строго большее заданного числа `X`.

10

64

Эрик обходит на Хеллоуин дома соседей, что собрать сладости. Он может посещать дома соседей по несколько раз и соседи каждый раз дают угощения, но Эрик не может посещать дом дважды подряд. Перед повторным визитом он должен посетить какой-нибудь другой дом. Кроме того, по мере заполнения мешка, Эрику становится тяжелее идти, поэтому пройденное расстояние при каждом переходе между домами соседей должно строго уменьшаться.

Эрик начинает путешествие от своего дома в точке `(0,0)`. Дома соседей находятся в точках с координатами `(X_i,\ Y_i)`. Координаты всех домов различны.

Вычислите, какое максимальное количество угощений сможет собрать Эрик, прежде чем расстояние до следующего дома ему покажется слишком большим (т.е. большим или равным предыдущего пройденного расстояния).

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 2000`) – количество домов соседей. Следующие `N` строк содержат по два целых числа `X_i` и `Y_i` (`-10000\ ≤\ X_i,\ Y_i\ ≤\ 10000`) – координаты домов.

Вывести одно целое число – максимальное количество угощений, которое сможет собрать Эрик.

5
3 1
3 2
3 3
4 10
5 8

6

Пояснение к примеру: Сначала Эрик идет из точки (0,0) в точку (4,10), преодолевая расстояние `sqrt(116)`, оттуда в точку (3,1) и проходит расстояние `sqrt(82)`, далее в точку (5,8), находящуюся на расстоянии `sqrt(53)`, а из нее в точку (3,3) на расстоянии `sqrt(29)`, затем снова в точку (3,1) на расстоянии 2 и, наконец, в точку (3,2) на расстоянии 1.

Если учительница дает сложную математическую задачу "Найдите сумму чисел в диапазоне от 1 до 10 включительно, которые делятся на целую часть квадратного корня из самого себя без остатка", Тимми уже через секунду готов отвечать. Учительница знает правильный ответ и говорит "Правильно, Тимми", когда он скажет свое имя нужное количество раз, поэтому Тимми никогда не ошибается.

Кайлу нужно вычислить ответ в тысячи раз быстрее Тимми, чтобы получить отличную оценку. Напишите программу, которая поможет Кайлу быстро решать подобные задачи.

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10000`) – количество тестовых случаев. Далее следует `N` строк, в каждой строке содержатся два целых числа `A` и `B` (`1\ ≤\ A\ ≤\ B\ ≤\ 10^{12}`) – диапазон чисел.

Выведите для каждого диапазона искомую сумму в отдельной строке.

2
1 10
10 10

33
0

Чтобы успокоиться после сеанса психотерапии, мистер Маки раскладывает пасьянс. Для его любимого пасьянса используется `N` карт, пронумерованных от 1 до `N`. Сначала карты раскладываются в `N` стопок по одной карте. Новые стопки в процессе игры не появляются, но стопка остается существующей, даже если в ней не осталось ни одной карты. Разрешается перемещать верхнюю карту из стопки на соседнюю стопку, только если номер верхней карты в ней больше или соседняя стопка пуста. Игра заканчивается, когда во всех стопках снова по одной карте, и при этом они образуют числовой ряд от 1 до `N` слева направо.

Напишите программу, определяющую, сходится ли пасьянс и какое минимальное количество ходов потребуется для его решения.

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 7`). Вторая строка содержит перестановку чисел от 1 до `N` – начальное расположение карт.

Вывести одно целое число – минимальное количество ходов для решения пасьянса. Если решение пасьянса невозможно, то вывести сообщение "IMPOSSIBLE".

3
3 2 1

20

2
2 1

IMPOSSIBLE

Мистер Гаррисон задал ученикам следующую задачу: "Найти максимальное подмножество чисел из чисел от 1 до `N`, в котором нет чисел ровно в `p` раз больше какого-либо другого числа из этого подмножества" и указал каждому школьнику значения `N` и `p` индивидуально.

Напишите программу, которая поможет мистеру Гаррисону проверить ответы учеников.

Первая строка ввода содержит два целых числа `N` (`1\ ≤\ N\ ≤\ 10^9`) и `p` (`2\ ≤\ p\ <\ 100`, `p` – простое число).

Вывести два целых числа – максимальное количество элементов в искомом подмножестве и количество вариантов таких максимальных подмножеств по модулю `10^9+7`.

8 2

5 6

Пояснение к примеру: существует 6 максимальных подмножеств из 5 значений {1,3,4,5,7}, {1,4,5,6,7}, {1,3,5,7,8}, {1,5,6,7,8}, {2,3,5,7,8} и {2,5,6,7,8}.

Для обороны города от монголов Туонг Лу Ким должен построить стену таким образом, чтобы все важные здания города (мэрия, школа и т.д.) находились внутри стены. Стена должна быть связной (клетки, занятые стеной, должны иметь общую сторону) и иметь минимальную длину. Если существует несколько вариантов размещения стены с минимальной длиной, то нужно выбрать вариант, при котором все здания находятся внутри одной связной области, охватываемой стеной, и площадь этой области минимальна. Если есть несколько вариантов с минимальной длиной стены и минимальной площадью, то мистера Кима устроит любой вариант.

Напишите программу, которая по плану городу найдет оптимальный способ строительства стены.

Первая строка ввода содержит два целых числа `N` и `M` (`3\ ≤\ N,\ M\ ≤\ 1000`). Следующие `N` строк содержат `M` символов '*' (важные здания) и '.' (место, где можно строить стену). Гарантируется, что на плане есть хотя бы один символ '*' и нет '*'на его границах.

Вывести `N` строк, содержащих `M` символов – план строительства стены. Клетки, где нужно построить стену, должны быть помечены символом '#'.

5 6
......
.*....
....*.
......
......

######
#*...#
####*#
...###
......

Джимбо и Нед являются организаторами школьного похода. Выбранный ими маршрут привел бойскаутов к старому канатному мосту, который пугает некоторых школьников. Поэтому Джибмо нужно придумать, как быстро преодолеть это препятствие и продолжить поход. Школьники должны переходить мост в том порядке, в котором подошли к мосту, при этом на мост должны заходить группами от 1 до `M` человек, чтобы мост не рухнул под их тяжестью. Группа движется по мосту вместе и переходит его за время перехода самого медленного из членов группы.

Напишите программу, которая найдет оптимальный план разбиения на группы, минимизирующий суммарное время перехода через мост.

Первая строка ввода содержит два целых числа – количество школьников `N` (`1\ ≤\ N\ ≤\ 100000`) и максимальный размер группы `M` (`1\ ≤\ M\ ≤\ 20`). Следующая строка содержит `N` целых чисел в диапазоне от 1 до 1000 – время на переход моста для каждого школьника.

В первой строке вывести одно число – минимальное суммарное время перехода через мост. Во второй строке вывести размеры групп, на которые нужно разбить школьников.

5 2
1 7 5 4 6

14
1 2 2

A school team "Cows" is trying to assign jerseys numbered `1,2,…,N` to players. The size of each jersey is either small (S), medium (M) or large (L). Each player has requested a specific jersey number and a preferred size. The players will not be satisfied with a jersey that is the wrong number or that is smaller than their preferred size. They will be satisfied with a jersey that is their preferred size or larger as long as it is the right number. Two players cannot be given the same jersey.

Your task is to determine the maximum number of requests that can be satisfied.

The first line of input is the integer `N` (`1\ ≤\ N\ ≤\ 1000000`) which is the number of jerseys. The second line of input is the integer `M` (`1\ ≤\ M\ ≤\ 1000000`) which is the number of players. The next `N` lines are each the character S, M or L. Line `j` gives the size of jersey `j` (`1\ ≤\ j\ ≤\ N`). The last `M` lines are each the character S, M or L followed by a space followed by an integer. Line `i` (`1\ ≤\ i\ ≤\ M`) gives the requested size and jersey number `k` (`1\ ≤\ k\ ≤\ N`) for player `i`.

The output will consist of a single integer which is the maximum number of requests that can be satisfied.

4
3
M
S
S
L
L 3
S 3
L 1

1

1
2
M
M 1
S 1

1

Explanation Sample Output

Jersey 1 cannot be assigned because it is medium and player 3 requested large. No player requested jersey 2 or 4. Jersey 3 (small) can be assigned player 2 (small) but not player 1 (large).