Мониторинг
Алла получила задание, связанное с мониторингом работы различных серверов.
Требуется понять, сколько времени обрабатываются определённые запросы на
конкретных серверах. Эту информацию нужно хранить в матрице, где номер столбца
соответствуют идентификатору запроса, а номер строки — идентификатору сервера.
Алла перепутала строки и столбцы местами. С каждым бывает. Помогите ей
исправить баг.
Есть матрица размера m × n. Нужно написать функцию, которая её транспонирует.
Транспонированная матрица получается из исходной заменой строк на столбцы.
В первой строке задано число n — количество строк матрицы.
Во второй строке задано m — число столбцов, m и n не превосходят 1000.
В следующих n строках задана матрица. Числа в ней не превосходят
по модулю 1000.
Напечатайте транспонированную матрицу в том же формате, который задан во
входных данных. Каждая строка матрицы выводится на отдельной строке,
элементы разделяются пробелами.
| Ввод | Вывод |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 |
1 0 7 2 2 2 4 7 3 6 1 0 |
Список дел
Васе нужно распечатать свой список дел на сегодня. Помогите ему: напишите
функцию, которая печатает все его дела. Известно, что дел у Васи не больше 5000.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать
только функцию, которая принимает на вход голову списка и печатает его
элементы. Ниже дано описание структуры, которая задаёт узел списка.
В качестве ответа сдайте только код функции, которая печатает элементы списка.
Длина списка не превосходит 5000 элементов. Список не бывает пустым.
Функция должна напечатать элементы списка по одному в строке.
Нелюбимое дел
Вася размышляет, что ему можно не делать из того списка дел, который он
составил. Но, кажется, все пункты очень важные! Вася решает загадать число и
удалить дело, которое идёт под этим номером. Список дел представлен в виде
односвязного списка. Напишите функцию solution, которая принимает на вход
голову списка и номер удаляемого дела и возвращает голову обновлённого списка.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать
только функцию, которая принимает на вход голову списка и номер удаляемого
элемента и возвращает голову обновлённого списка.
Функция принимает голову списка и индекс элемента, который надо удалить
(нумерация с нуля). Список содержит не более 5000 элементов.
Список не бывает пустым.
Верните голову списка, в котором удален нужный элемент.
Заботливая мама
Мама Васи хочет знать, что сын планирует делать и когда. Помогите ей:
напишите функцию solution, определяющую индекс первого вхождения передаваемого
ей на вход значения в связном списке, если значение присутствует.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать
только функцию, которая принимает на вход голову списка и искомый элемент,
а возвращает целое число — индекс найденного элемента или -1.
Функция на вход принимает голову односвязного списка и элемент, который нужно
найти. Длина списка не превосходит 10000 элементов. Список не бывает пустым.
Функция возвращает индекс первого вхождения искомого элемента в список
(индексация начинается с нуля). Если элемент не найден, нужно вернуть -1.
Всё наоборот
Вася решил запутать маму —– делать дела в обратном порядке. Список его дел
теперь хранится в двусвязном списке. Напишите функцию, которая вернёт список
в обратном порядке.
Внимание: в этой задаче не нужно считывать входные данные. Нужно написать
только функцию, которая принимает на вход голову двусвязного списка и
возвращает голову перевёрнутого списка. Ниже дано описание структуры, которая
задаёт вершину списка.
Функция принимает на вход единственный аргумент — голову двусвязного списка.
Длина списка не превосходит 1000 элементов. Список не бывает пустым.
Функция должна вернуть голову развернутого списка.
Стек - Max
Нужно реализовать класс StackMax, который поддерживает операцию определения
максимума среди всех элементов в стеке. Класс должен поддерживать
операции push(x), где x – целое число, pop() и get_max().
В первой строке записано одно число n — количество команд, которое не
превосходит 10000. В следующих n строках идут команды. Команды могут быть
следующих видов:
- push(x) — добавить число x в стек;
- pop() — удалить число с вершины стека;
- get_max() — напечатать максимальное число в стеке;
Если стек пуст, при вызове команды get_max() нужно напечатать «None», для
команды pop() — «error».
Для каждой команды get_max() напечатайте результат её выполнения. Если стек
пустой, для команды get_max() напечатайте «None». Если происходит удаление из
пустого стека — напечатайте «error».
| Ввод | Вывод |
|
8 get_max push 7 pop push -2 push -1 pop get_max get_max |
None -2 -2 |
Стек - MaxEffective
Реализуйте класс StackMaxEffective, поддерживающий операцию
определения максимума среди элементов в стеке.
Сложность операции должна быть O(1).
Для пустого стека операция должна возвращать None.
При этом push(x) и pop() также должны выполняться за константное время.
В первой строке записано одно число — количество команд,
оно не превосходит 100000. Далее идут команды по одной в строке.
Команды могут быть следующих видов:
push(x) — добавить число x в стек. Число x не превышает 105;
pop() — удалить число с вершины стека;
get_max() — напечатать максимальное число в стеке;
top() — напечатать число с вершины стека;
Если стек пуст, при вызове команды get_max нужно напечатать «None»,
для команды pop и top — «error».
Для каждой команды get_max() напечатайте результат её выполнения.
Если стек пустой, для команды get_max() напечатайте «None».
Если происходит удаление из пустого стека — напечатайте «error».
| Ввод | Вывод |
|
13 pop pop top push 4 push -5 top push 7 pop pop get_max top pop get_max |
error error error -5 4 4 None |
Скобочная последовательность
Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов.
Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно
популярная.
Дана скобочная последовательность. Нужно определить, правильная ли она.
Будем придерживаться такого определения:
- пустая строка —– правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки одного
типа, –— правильная скобочная последовательность;
- правильная скобочная последовательность с приписанной слева или справа
правильной скобочной последовательностью —– тоже правильная.
На вход подаётся последовательность из скобок трёх видов: [], (), {}.
Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную
последовательность и возвращает True, если последовательность правильная,
а иначе False.
На вход подаётся одна строка, содержащая скобочную последовательность.
Скобки записаны подряд, без пробелов.
Выведите «True» или «False».
| Ввод | Вывод |
|
{[()]} |
True |
Ограниченная очередь
Астрологи объявили день очередей ограниченного размера. Тимофею нужно
написать класс MyQueueSized, который принимает параметр max_size, означающий
максимально допустимое количество элементов в очереди.
Помогите ему —– реализуйте программу, которая будет эмулировать работу такой
очереди. Функции, которые надо поддержать, описаны в формате ввода.
В первой строке записано одно число — количество команд, оно не превосходит 5000.
Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000.
Далее идут команды по одной на строке. Команды могут быть следующих видов:
- push(x) — добавить число x в очередь;
- pop() — удалить число из очереди и вывести на печать;
- peek() — напечатать первое число в очереди;
- size() — вернуть размер очереди;
При превышении допустимого размера очереди нужно вывести «error».
При вызове операций pop() или peek() для пустой очереди нужно вывести «None».
Напечатайте результаты выполнения нужных команд, по одному на строке.
| Ввод | Вывод |
|
8 2 peek push 5 push 2 peek size size push 1 size |
None 5 2 2 error 2 |
Списочная очередь
Любимый вариант очереди Тимофея — очередь, написанная с использованием
связного списка. Помогите ему с реализацией. Очередь должна поддерживать
выполнение трёх команд:
- get() — вывести элемент, находящийся в голове очереди, и удалить его.
Если очередь пуста, то вывести «error».
- put(x) — добавить число x в очередь
- size() — вывести текущий размер очереди
В первой строке записано количество команд n — целое число, не превосходящее
1000. В каждой из следующих n строк записаны команды по одной строке.
Выведите ответ на каждый запрос по одному в строке.
| Ввод | Вывод |
|
10 put -34 put -23 get size get size get get put 80 size |
-34 1 -23 0 error error 1 |
Рекурсивные числа Фибоначчи
У Тимофея было n(0≤n≤32) стажёров. Каждый стажёр хотел быть лучше своих
предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали
два предыдущих стажёра в сумме. Два первых стажёра были менее
инициативными —– они сделали по одному коммиту.
Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля).
Тогда выполняется следующее: F0=F1=1. Для всех i≥2 выполнено Fi=F(i−1)+F(i−2).
Определите, сколько кода напишет следующий стажёр –— найдите Fn.
Решение должно быть реализовано рекурсивно.
На вход подаётся n — целое число в диапазоне от 0 до 32.
Нужно вывести Fn.
| Ввод | Вывод |
|
3 |
3 |
Фибоначчи по модулю
У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 10^6) человек. Каждый
стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал
столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых
стажёра были менее инициативными — они сделали по одному коммиту.
Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля).
Первые два стажёра сделали по одному коммиту: F0=F1=1. Для всех i≥ 2
выполнено Fi=Fi−1+Fi−2.
Определите, сколько кода напишет следующий стажёр –— найдите последние k цифр
числа Fn.
**Как найти k последних цифр**,
Чтобы вычислить k последних цифр некоторого числа x, достаточно взять остаток
от его деления на число 10k. Эта операция обозначается как x mod 10k.
Узнайте, как записывается операция взятия остатка по модулю в вашем языке
программирования.
Также обратите внимание на возможное переполнение целочисленных типов, если в
вашем языке такое случается.
#### Формат ввода
В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 10^6)
и k (1 ≤ k ≤ 8).
Выведите единственное число – последние k цифр числа Fn.
Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.
| Ввод | Вывод |
|
3 1 |
3 |
Дек | Финальная задача №1
Гоша реализовал структуру данных Дек, максимальный размер которого определяется
заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front()
работали корректно. Но, если в деке было много элементов, программа работала
очень долго. Дело в том, что не все операции выполнялись за O(1).
Помогите Гоше! Напишите эффективную реализацию.
**Внимание: при реализации используйте кольцевой буфер.**
В первой строке записано количество команд n — целое число, не превосходящее
100000. Во второй строке записано число m — максимальный размер дека. Он не
100001. превосходит 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 |
Калькулятор | Финальная задача №2
Задание связано с обратной польской нотацией. Она используется для парсинга
арифметических выражений. Еще её иногда называют постфиксной нотацией.
В постфиксной нотации операнды расположены перед знаками операций.
Пример 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. Обработка входного символа:
- Если на вход подан операнд, он помещается на вершину стека.
- Если на вход подан знак операции, то эта операция выполняется над требуемым количеством значений, взятых из стека в порядке добавления. Результат выполненной операции помещается на вершину стека.
2. Если входной набор символов обработан не полностью, перейти к шагу 1.
3. После полной обработки входного набора символов результат вычисления выражения находится в вершине стека. Если в стеке осталось несколько чисел, то надо вывести только верхний элемент.
**Замечание про отрицательные числа и деление:** в этой задаче под делением понимается математическое целочисленное деление. Это значит, что округление всегда происходит вниз. А именно: если a / b = c, то b ⋅ c — это наибольшее число, которое не превосходит a и одновременно делится без остатка на b.
Например, -1 / 3 = -1. Будьте осторожны: в C++, Java и Go, например, деление чисел работает иначе.
В текущей задаче гарантируется, что деления на отрицательное число нет.
В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел.
На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000.
Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.
Выведите единственное число — значение выражения.
| Ввод | Вывод |
|
2 1 + 3 * |
9 |