Решения задач из различных тренировок по алгоритмам.
Задачи разбиты на блоки.
A. Ближайший ноль
Тимофей ищет место, чтобы построить себе дом. Улица, на которой он хочет жить, имеет длину n, то есть состоит из n одинаковых идущих подряд участков. Каждый участок либо пустой, либо на нём уже построен дом.
Общительный Тимофей не хочет жить далеко от других людей на этой улице. Поэтому ему важно для каждого участка знать расстояние до ближайшего пустого участка. Если участок пустой, эта величина будет равна нулю — расстояние до самого себя.
Помогите Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.
В первой строке дана длина улицы —– n (1 ≤ n ≤ 10^6). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один ноль. Номера домов (положительные числа) уникальны и не превосходят 10^9.
Для каждого из участков выведите расстояние до ближайшего нуля. Числа выводите в одну строку, разделяя их пробелами.
| Ввод | Вывод |
|---|---|
| 5 0 1 4 9 0 |
0 1 2 1 0 |
| 6 0 7 9 4 8 20 |
0 1 2 3 4 5 |
B. Ловкость рук
«Тренажёр для скоростной печати» представляет собой квадратную клавиатуру из шестнадцати клавиш размером 4x4. На каждой клавише может быть изображена либо точка, либо цифра от 1 до 9.
Занятие на тренажёре делится на раунды:
- каждый раунд состоит из нескольких игр;
- в разных раундах число игр может быть разным;
- номер каждой игры в раунде обозначается счётчиком t.
Для каждого раунда на клавишах устанавливаются определённые значения, которые остаются неизменными в течение всех игр раунда.
Значение счётчика игр t не может превысить значение самого большого числа, отображённого на клавиатуре в текущем раунде.
В упражнении на тренажёре принимают участие два игрока, они играют вдвоём на одной клавиатуре. Для каждого раунда устанавливается максимальное число клавиш, которые может нажать один игрок (оно обозначается переменной k и не изменяется в течение раунда).
В каждой отдельной игре участники должны вместе нажать на клавиши, на которых изображена цифра, соответствующая номеру игры t. Например, во второй игре раунда игроки должны нажать все те клавиши, на которых изображена двойка.
В раунде могут быть игры, где не требуется нажимать кнопки: например, в приведённом варианте раунда в играх от t = 4 до t = 8 кнопки нажимать не потребуется: на клавиатуре нет цифр от 4 до 8:
Если в очередной игре у участников есть возможность нажать все необходимые клавиши — они их нажимают и получают 1 балл.
Предположим, что для раунда задан набор кнопок, как на картинке, и k = 3 (каждый из участников может нажать не более трёх кнопок). Тогда во второй игре (t = 2), где должны быть нажаты двойки, игроки вдвоём смогут нажать только 6 клавиш (k * 2 = 6). Но на клавиатуре семь двоек; участники не смогут нажать их все и не получат балл.
Напишите программу, которая будет принимать данные для определённого раунда:
- значение k,
- значения для кнопок,
и вычислит количество баллов, которое будут заработано в этом раунде.
В первой строке дано целое число k (1 ≤ k ≤ 5).
В четырёх следующих строках заданы значения для кнопок –— по 4 символа в каждой строке. Каждый символ —– либо точка, либо цифра от 1 до 9. Символы одной строки идут подряд и не разделены пробелами.
Выведите единственное число –— количество баллов, которое игроки наберут в раунде.
| Ввод | Вывод |
|---|---|
| 3 1231 2..2 2..2 2..2 |
2 |
| 4 1111 9999 1111 9911 |
1 |
| 4 1111 1111 1111 1111 |
0 |
A. Дек
Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию.
Внимание: при реализации используйте кольцевой буфер.
В первой строке записано количество команд n — целое число, не превосходящее 100000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 50000. В следующих n строках записана одна из команд:
- push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error».
- push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error».
- pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error».
- pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error».
Value — целое число, по модулю не превосходящее 1000.
Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.
| Ввод | Вывод |
|---|---|
| 4 4 push_front 861 push_front -819 pop_back pop_back |
861 -819 |
| 7 10 push_front -855 push_front 0 pop_back pop_back push_back 844 pop_back push_back 823 |
-855 0 844 |
| 6 6 push_front -201 push_back 959 push_back 102 push_front 20 pop_front pop_back |
20 102 |
B. Калькулятор
Задание связано с обратной польской нотацией. Она используется для парсинга арифметических выражений. Еще её иногда называют постфиксной нотацией.
В постфиксной нотации операнды расположены перед знаками операций.
Пример 1:
3 4 +
означает 3 + 4 и равно 7
Пример 2:
12 5 /
Так как деление целочисленное, то в результате получим 2.
Пример 3:
10 2 4 * -
означает 10 - 2 * 4 и равно 2
Разберём последний пример подробнее:
Знак * стоит сразу после чисел 2 и 4, значит к ним нужно применить операцию, которую этот знак обозначает, то есть перемножить эти два числа. В результате получим 8.
После этого выражение приобретёт вид:
10 8 -
Операцию «минус» нужно применить к двум идущим перед ней числам, то есть 10 и 8. В итоге получаем 2.
Рассмотрим алгоритм более подробно. Для его реализации будем использовать стек.
Для вычисления значения выражения, записанного в обратной польской нотации, нужно считывать выражение слева направо и придерживаться следующих шагов:
- Обработка входного символа:
- Если на вход подан операнд, он помещается на вершину стека.
- Если на вход подан знак операции, то эта операция выполняется над требуемым количеством значений, взятых из стека в порядке добавления. Результат выполненной операции помещается на вершину стека.
- Если входной набор символов обработан не полностью, перейти к шагу 1.
- После полной обработки входного набора символов результат вычисления выражения находится в вершине стека. Если в стеке осталось несколько чисел, то надо вывести только верхний элемент.
Замечание про отрицательные числа и деление: в этой задаче под делением понимается математическое целочисленное деление. Это значит, что округление всегда происходит вниз. А именно: если a / b = c, то b ⋅ c — это наибольшее число, которое не превосходит a и одновременно делится без остатка на b.
Например, -1 / 3 = -1. Будьте осторожны: в C++, Java и Go, например, деление чисел работает иначе.
В текущей задаче гарантируется, что деления на отрицательное число нет.
В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел.
На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000.
Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.
Выведите единственное число — значение выражения.
| Ввод | Вывод |
|---|---|
| 2 1 + 3 * | 9 |
| 7 2 + 4 * 2 + | 38 |
A. Поиск в сломанном массиве
Алла ошиблась при копировании из одной структуры данных в другую. Она хранила массив чисел в кольцевом буфере. Массив был отсортирован по возрастанию, и в нём можно было найти элемент за логарифмическое время. Алла скопировала данные из кольцевого буфера в обычный массив, но сдвинула данные исходной отсортированной последовательности. Теперь массив не является отсортированным. Тем не менее, нужно обеспечить возможность находить в нем элемент за O(log n).
Можно предполагать, что в массиве только уникальные элементы.
От вас требуется реализовать функцию, осуществляющую поиск в сломанном массиве.
Функция принимает массив натуральных чисел и искомое число k. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.
В примерах:
В первой строке записано число n –— длина массива.
Во второй строке записано положительное число k –— искомый элемент.
Далее в строку через пробел записано n натуральных чисел – элементы массива.
Функция должна вернуть индекс элемента, равного k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, функция должна вернуть −1.
Изменять массив нельзя.
Для отсечения неэффективных решений ваша функция будет запускаться от 100000 до 1000000 раз.
| Ввод | Вывод |
|---|---|
| 9 5 19 21 100 101 1 4 5 7 12 |
6 |
| 2 1 5 1 |
1 |
B. Эффективная быстрая сортировка
Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.
Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач P_i и размер штрафа F_i. Штраф начисляется за неудачные попытки и время, затраченное на задачу.
Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.
Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется "in-place").
Как работает in-place quick sort
Как и в случае обычной быстрой сортировки, которая использует дополнительную память, необходимо выбрать опорный элемент (англ. pivot), а затем переупорядочить массив. Сделаем так, чтобы сначала шли элементы, не превосходящие опорного, а затем —– большие опорного.
Затем сортировка вызывается рекурсивно для двух полученных частей. Именно на этапе разделения элементов на группы в обычном алгоритме используется дополнительная память. Теперь разберёмся, как реализовать этот шаг in-place.
Пусть мы как-то выбрали опорный элемент. Заведём два указателя left и right, которые изначально будут указывать на левый и правый концы отрезка соответственно. Затем будем двигать левый указатель вправо до тех пор, пока он указывает на элемент, меньший опорного. Аналогично двигаем правый указатель влево, пока он стоит на элементе, превосходящем опорный. В итоге окажется, что что левее от left все элементы точно принадлежат первой группе, а правее от right — второй. Элементы, на которых стоят указатели, нарушают порядок. Поменяем их местами (в большинстве языков программирования используется функция swap()) и продвинем указатели на следующие элементы. Будем повторять это действие до тех пор, пока left и right не столкнутся.
На рисунке представлен пример разделения при pivot=5. Указатель left — голубой, right — оранжевый.
В первой строке задано число участников n, 1 ≤ n ≤ 100 000.
В каждой из следующих n строк задана информация про одного из участников.
i-й участник описывается тремя параметрами:
- уникальным логином (строкой из маленьких латинских букв длиной не более 20)
- числом решённых задач P_i
- штрафом F_i
F_i и P_i — целые числа, лежащие в диапазоне от 0 до 10^9.
Для отсортированного списка участников выведите по порядку их логины по одному в строке.
| Ввод | Вывод |
|---|---|
| 5 alla 4 100 gena 6 1000 gosha 2 90 rita 2 90 timofey 4 80 |
gena timofey alla gosha rita |
| 5 alla 0 0 gena 0 0 gosha 0 0 rita 0 0 timofey 0 0 |
alla gena gosha rita timofey |