Подразделы

Другие разделы

Дата и время

13/10/2024 15:29:11

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

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

printA. Крутые числа

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Стэну нравятся числа, которые одновременно являются кубами и квадратами. Он считает их крутыми. Например, крутым является число 64, так как `64=4^3=8^2`.
Ввод содержит одно целое число `X` (`1\ ≤\ X\ <\ 10^18`).
Выведите минимальное крутое число, строго большее заданного числа `X`.

Пример ввода

10

Пример вывода

64

printB. Хеллоуин

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

printC. Сумма

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Если учительница дает сложную математическую задачу "Найдите сумму чисел в диапазоне от 1 до 10 включительно, которые делятся на целую часть квадратного корня из самого себя без остатка", Тимми уже через секунду готов отвечать. Учительница знает правильный ответ и говорит "Правильно, Тимми", когда он скажет свое имя нужное количество раз, поэтому Тимми никогда не ошибается.
Кайлу нужно вычислить ответ в тысячи раз быстрее Тимми, чтобы получить отличную оценку. Напишите программу, которая поможет Кайлу быстро решать подобные задачи.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10000`) – количество тестовых случаев. Далее следует `N` строк, в каждой строке содержатся два целых числа `A` и `B` (`1\ ≤\ A\ ≤\ B\ ≤\ 10^{12}`) – диапазон чисел.
Выведите для каждого диапазона искомую сумму в отдельной строке.

Пример ввода

2
1 10
10 10

Пример вывода

33
0
Пояснение к примеру: в первом тестовом случае в сумму входят числа 1, 2, 3, 4, 6, 8 и 9.

printD. Пасьянс

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Чтобы успокоиться после сеанса психотерапии, мистер Маки раскладывает пасьянс. Для его любимого пасьянса используется `N` карт, пронумерованных от 1 до `N`. Сначала карты раскладываются в `N` стопок по одной карте. Новые стопки в процессе игры не появляются, но стопка остается существующей, даже если в ней не осталось ни одной карты. Разрешается перемещать верхнюю карту из стопки на соседнюю стопку, только если номер верхней карты в ней больше или соседняя стопка пуста. Игра заканчивается, когда во всех стопках снова по одной карте, и при этом они образуют числовой ряд от 1 до `N` слева направо.
Напишите программу, определяющую, сходится ли пасьянс и какое минимальное количество ходов потребуется для его решения.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 7`). Вторая строка содержит перестановку чисел от 1 до `N` – начальное расположение карт.
Вывести одно целое число – минимальное количество ходов для решения пасьянса. Если решение пасьянса невозможно, то вывести сообщение "IMPOSSIBLE".

Пример ввода #1

3
3 2 1

Пример вывода #1

20

Пример ввода #2

2
2 1

Пример вывода #2

IMPOSSIBLE
Пояснение к примеру 1
Ход123
-321
1312
2132
3132
4312
5312
6312
7132
8132
9123
10123
11231
12231
13213
14123
15123
16213
17213
18213
19123
20123

printE. Задача

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Мистер Гаррисон задал ученикам следующую задачу: "Найти максимальное подмножество чисел из чисел от 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}.

printF. Оборона города

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Для обороны города от монголов Туонг Лу Ким должен построить стену таким образом, чтобы все важные здания города (мэрия, школа и т.д.) находились внутри стены. Стена должна быть связной (клетки, занятые стеной, должны иметь общую сторону) и иметь минимальную длину. Если существует несколько вариантов размещения стены с минимальной длиной, то нужно выбрать вариант, при котором все здания находятся внутри одной связной области, охватываемой стеной, и площадь этой области минимальна. Если есть несколько вариантов с минимальной длиной стены и минимальной площадью, то мистера Кима устроит любой вариант.
Напишите программу, которая по плану городу найдет оптимальный способ строительства стены.
Первая строка ввода содержит два целых числа `N` и `M` (`3\ ≤\ N,\ M\ ≤\ 1000`). Следующие `N` строк содержат `M` символов '*' (важные здания) и '.' (место, где можно строить стену). Гарантируется, что на плане есть хотя бы один символ '*' и нет '*'на его границах.
Вывести `N` строк, содержащих `M` символов – план строительства стены. Клетки, где нужно построить стену, должны быть помечены символом '#'.

Пример ввода

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

Пример вывода

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

printG. Школьный поход

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Пример ввода

5 2
1 7 5 4 6

Пример вывода

14
1 2 2

printH. Jerseys

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.

Sample Input #1

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

Sample Output #1

1

Sample Input #2

1
2
M
M 1
S 1

Sample Output #2

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).
loading