3-й квалификационный раунд завершен

Задания

Показывать по одной задаче на странице / все задачи на одной странице

"A" Электронные таблицы
Ограничение по времени 1 секунда
Ограничение по памяти 256 мегабайт

Петя разрабатывает собственный редактор электронных таблиц. В его редакторе столбцы будут называться следующим образом: первые 26 столбцов — соответствующими буквами латинского алфавита: A, B, C, ..., Z. Следующие столбцы, начиная с 27, называются парами букв: AA, AB, ..., AZ, BA, BB, ..., BZ, ..., ZZ. Далее используются тройки букв: AAA, AAB, AAC, ..., затем четверки, и так далее.

Теперь Пете необходимо по номеру столбца определить его название. Помогите ему написать соответствующий фрагмент кода.

Формат входных данных

Входные данные содержат несколько тестовых примеров. Первая строка содержит целое число t — количество тестов (1 ≤ t ≤ 1000).

Следующие t строк содержат по одному целому число k (1 ≤ k ≤ 109).

Формат выходных данных

Для каждого теста выведите в отдельной строке название k-го столбца.

Примеры
Входные данные
4
1
10
100
1000
Выходные данные
A
J
CV
ALL
"B" Смертный бой
Ограничение по времени 1 секунда
Ограничение по памяти 256 мегабайт

Недавно Вася начал играть в новую компьютерную игру. В конце первого уровня его ждал босс, которого нужно победить, чтобы продолжить проходить игру. У Васи есть отряд из n персонажей, i-й из которых имеет hi единиц здоровья и ai единиц атаки. Босс же имеет H единиц здоровья и A единиц атаки.

Сражение происходит следующим образом:

  • Если у Васи больше нет персонажей, он проиграл;
  • Иначе, он выбирает одного из них и выставляет на бой против босса;
  • Пусть Вася выбрал персонажа номер i. Тогда:
    • Персонаж нападает на босса и снимает ему ai единиц здоровья;
    • Если босс еще жив, то есть его количество единиц здоровья положительно, он нападает в ответ и снимает персонажу A единиц здоровья;
    • Пока и персонаж и босс оба живы, действия повторяются.
  • Если босс умер, сражение заканчивается, Вася побеждает. В противном случае все действия повторяются.

Так как Васе еще предстоит проходить следующие уровни, он хочет потерять как можно меньше персонажей. Помогите ему — найдите минимальное возможное количество персонажей, которое он может потерять в сражении с боссом. Если же Васе не победить даже используя всех персонажей, выведите  - 1.

Рассмотрим тестовые примеры.

В первом примере Вася может сначала отправить сражаться персонажа 2, который три раза нанесет удар, уменьшит количество единиц здоровья у босса на 12, и лишь затем погибнет, а затем отправить персонажа 3, который сразу же снимет у босса уже 6 единиц здоровья и убьет его. Таким образом, Вася потеряет только одного персонажа.

Во втором примере даже если Вася отправит в бой по очереди всех персонажей, босс не будет убит.

Формат входных данных

Входные данные содержат несколько тестовых наборов. В первой строке задано количество тестов t (1 ≤ t ≤ 1000).

Каждый из следующих t тестов описывается следующим образом: в первой строке описания теста содержится три целых числа n, H, A — количество персонажей у Васи, количество единиц здоровья и атаки у босса соответственно (1 ≤ n ≤ 105, 1 ≤ H, A ≤ 109).

В каждой из следующих n строк содержится два целых числа hi, ai — количество единиц здоровья и атаки у i-го персонажа соответственно (1 ≤ hi, ai ≤ 109).

Гарантируется, что сумма n во всех тестах одних входных данных не превосходит 105.

Формат выходных данных

Для каждого теста выведите ответ на него — минимальное количество персонажей, которое может потерять Вася, чтобы одержать победу над боссом, или  - 1, если он в любом случае проиграет сражение.

Примеры
Входные данные
2
4 18 4
4 5
9 4
1 6
3 3
4 27 4
4 5
9 4
1 6
3 3
Выходные данные
1
-1
"C" Слегка палиндромные числа
Ограничение по времени 1 секунда
Ограничение по памяти 256 мегабайт

Будем называть целое число слегка палиндромным, если первая цифра его десятичной записи без ведущих нулей совпадает с последней. Ваша задача — посчитать количество слегка палиндромных чисел на отрезке с l по r, включительно.

В первом тестовом примере слегка палиндромные числа — 8, 9, 11 и 22.

Во втором — 1251 и 1261.

Формат входных данных

Входные данные содержат несколько тестов. В первой строке задано число t — количество тестов (1 ≤ t ≤ 5·104).

Каждый тест задаётся одной строкой, которая содержит целые числа l и r (1 ≤ l ≤ r ≤ 1018).

Формат выходных данных

Для каждого теста выведите в отдельной строке количество слегка палиндромных чисел на заданном отрезке.

Примеры
Входные данные
3
8 25
1251 1266
12 21
Выходные данные
4
2
0
"D" Дерево и многочлены
Ограничение по времени 2 секунды
Ограничение по памяти 256 мегабайт

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

Дано подвешенное дерево с n вершинами, пронумерованными от 1 до n. Исходно в каждой вершине дерева записано число 0. Для вершины v обозначим как d[v] глубину вершины v — количество вершин на пути от корня дерева до вершины v, в частности корень имеет глубину 1.

Дано число k. Требуется обрабатывать запросы двух видов.

  1. Дана вершина v и многочлен q(t) = q0 + q1t + q2t2 + ... + qktk. Для каждой вершины u в поддереве вершины v требуется прибавить к значению в этой вершине значение q(d[u]).
  2. Дана вершина v и многочлен q(t) = q0 + q1t + q2t2 + ... + qktk. Для каждой вершины u на пути от корня до вершины v, включительно, требуется прибавить к значению в этой вершине значение q(d[u]).

Все действия выполняются по модулю 109 + 7.

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

Формат входных данных

Входные данные содержат несколько тестов. В первой строке задано число t — количество тестов (1 ≤ t ≤ 105).

Далее следует описание тестов. Описание теста начинается с числа n — количества вершин в дереве, и числа k — максимальной степени многочленов (1 ≤ n ≤ 105, 1 ≤ k ≤ 20).

Далее следует n чисел p1, p2, ..., pn, число pi задает номер родителя вершины i, либо равно 0, если вершина i является корнем. Гарантируется, что числа pi задают корректное подвешенное дерево.

Следующая строка содержит число q — количество запросов (1 ≤ q ≤ 105). Следующие q строк содержат запросы, описание запроса состоит из числа t, равного 1 или 2 — типа запроса, после которого следует число v — номер вершины, и затем k + 1 целое число q0, q1, ..., qk — коэффициенты многочлена (0 ≤ qi < 109 + 7).

Гарантируется, что сумма значений n во всех тестов одних входных данных не превышает 105. Также сумма значений q во всех тестов одних входных данных не превышает 105.

Формат выходных данных

Для каждого теста выведите n чисел, для каждой вершины выведите число, которое в ней окажется после выполнения всех запросов. Еще раз напомним, что все вычисления проводятся по модулю 109 + 7.

Примеры
Входные данные
1
4 2
2 4 2 0
3
1 2 0 1 0
2 3 1 0 0
2 1 0 0 1
Выходные данные
12 7 4 2
"E" Красивый отчёт
Ограничение по времени 5 секунд
Ограничение по памяти 256 мегабайт

Андрей занимается анализом графа подписок в одной социальной сети. Этот граф является ориентированным: если пользователь a подписан на пользователя b, то пользователь b не обязательно подписан на пользователя a.

Менеджер Андрея попросил его посчитать для каждого пользователя x, сколько существует пользователей y, таких, что от пользователя x можно добраться в графе подписок до пользователя y.

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

Формат входных данных

В первой строке заданы целые числа n и m (1 ≤ n, m ≤ 200 000) — число пользователей социальной сети и число ситуаций, когда один пользователь подписан на другого.

Далее, в m строках идёт описание графа, i-я из этих строк содержит два целых числа ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi) и означает, что пользователь ai подписан на пользователя bi. Каждая упорядоченная пара (ai, bi) встречается во входных данных не более одного раза.

Формат выходных данных

Выведите n целых чисел qi — оценку на количество пользователей y, таких, что от пользователя i можно добраться в графе подписок до пользователя y. Если настоящее количество таких пар равно zi, должны выполняться неравенства qi ≤ 2zi и zi ≤ 2qi. Кроме того, допустимо для не более, чем 10 пользователей вывести qi, не удовлетворяющее указанным ограничениям.

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

В примере от пользователя 1 можно добраться до всех пяти пользователей. Однако, показанный ответ 7 тоже допустим, так как отличается от 5 не более, чем в два раза. Аналогично, допустимым является ответ 2 для пользователя 4.

Примеры
Входные данные
5 6
1 2
1 3
2 4
2 5
3 5
4 2
Выходные данные
7
3
2
2
1

Отправить решение

Загрузить Максимальный размер - 256 Кб

Вход

ВКонтакте Facebook It.Mail

Забыли пароль?

Регистрация

На вашу электронную почту была
отправлена инструкция по восстановлению пароля.