Яндекс.Практикум. Алгоритмы
A. Найди id В медиа-сервисе зарегистрировано n пользователей. Все пользователи, за исключением двух, в последние два месяца посещали сайт. Нужно определить id пользователей, которые сайт не посещали.
Формат ввода:
Первая строка содержит число n — количество зарегистрированных пользователей.
Во второй строке через пробел заданы различные n - 2 целых числа. Каждое из них не превосходит n и больше нуля.
Формат вывода: Нужно в одной строке вывести по возрастанию два пропущенных числа, разделённые пробелом.
Пример
Ввод:
7
6 4 1 2 3
Вывод:
5 7
В примечании было сказано, что алгоритм должен работать не дольше, чем O(n).
Решил попробовать на языке, который совсем недавно пришел в мою жизнь, и крепко в ней закрепился (Python).
Краткий алгоритм:
-
Сортируем введенный массив
-
В цикле проверяем на совпадение итератора и значения массива
-
При несовпадении - добавляем недостающий элемент, а также этот элемент добавляем в другой массив.
B. Три фишки
Маша и Медведь играют в игру. У Маши есть фишки с указанным на них количеством очков. На каждой фишке — k очков, k находится в промежутке от до . Медведь называет число, а Маша должна выбрать три фишки, сумма очков на которых наиболее близка с заданному числу.
Формат ввода:
Первая строка содержит целое число n в диапазоне от до число, названное первым участником. Во второй строке через пробел заданы целые числа для фишек второго участника.
Формат вывода:
Нужно вывести целое число — сумму очков трёх фишек, наиболее близкую к n.
Пример
Ввод:
6
-1 -1 -9 -7 3 -6
Вывод:
1
C. Разгадай шифр
Шерлок Холмс и доктор Ватсон передают друг другу зашифрованные сообщения, состоящие из чисел. Каждое число может обозначать одну букву, слово или знак препинания. Получая последовательность чисел, Холмс и Ватсон могут расшифровывать сообщения друг друга. Однако они стали подозревать, что кто-то разгадал их шифр и повысили уровень безопасности. Теперь каждое сообщение зашифровано в матрице. Чтобы его прочитать, нужно распечатать значения матрицы по спирали, начиная от центра вверх и далее по часовой стрелке.
Формат ввода:
Первая строка содержит целое нечётное число m в диапазоне от 1 до 1000 — количество строк и столбцов матрицы.
В каждой из следующих m строк даны m целых чисел в диапазоне от -1000 до 1000, разделённых пробелом.
Формат вывода:
Нужно вывести значения в матрице, начиная с центра по спирали. Движение вверх, далее по часовой стрелке. Каждое число выводится в отдельной строке.
Пример
Ввод:
3
9 10 7
0 7 7
8 3 4
Вывод:
7
10
7
7
4
3
8
0
9
D. Морской бой
Поиграем в морской бой. Поле представлено матрицей n на m. Длина кораблей ограничена размерами матрицы. Корабли могут быть расположены либо горизонтально, либо вертикально. Соприкасаться друг с другом они могут, пересекаться — нет. По полю несколько раз выстрелили. Нужно выяснить, сколько кораблей было сбито и сколько ранено.
Формат ввода
В первой строке подаются числа n и m, В следующей строке — количество кораблей k, В следующих k строках — описание кораблей: 4 числа через пробел. Первая пара чисел определяет ячейку матрицы, то есть номер строки и столбца, где расположено начало корабля. Вторая пара соответствует концу корабля. Нумерация строк и столбцов начинается с 0. Далее следует s — количество выстрелов, целое число в диапазоне от 0 до 10000.
В следующих s строках — описание выстрелов: пара чисел через пробел. Первое число соответствует номеру строки на поле для ячейки, куда попал выстрел, второе — номеру столбца. Стрелять в ячейку более одного раза нельзя.
Формат вывода
Нужно вывести 2 числа в строке, разделённые пробелом. Первое число — количество раненых кораблей, второе число — количество сбитых. Корабль считается сбитым, если выстрелы попали во все занимаемые им ячейки. Раненым — если задета хоть одна ячейка.
Пример
Ввод:
5 5
4
4 0 4 1
4 3 4 4
2 2 2 2
1 4 2 4
5
4 0
4 1
0 0
4 4
2 2
Вывод:
1 2
E. Самый пиццовый квартал
Мэр города Плужникова решил открыть серию пиццерий в городе. Город представлен в виде матрицы NxN, где каждая ячейка на позиции [i][j] — это отдельный квартал. Доставка из каждой пиццерии возможна не далее, чем на R кварталов от её расположения. Расстояние определяется минимальным количеством кварталов, которые пройдёт доставщик, если он передвигается по горизонтали или по вертикали. Ходить по диагонали нельзя. Например, представим, что N=5,R=2, и пиццерия расположена в ячейке (3,3). Тогда доставить пиццу можно в кварталы, помеченные символом X.
00X00
0XXX0
XXXXX
0XXX0
00X00
Артёмка очень любит пиццу. Он хочет попасть в квартал, где доступно максимальное количество заказов из разных пиццерий, чтобы выбрать лучшую. Помогите Артёмке найти максимальное количество доступных пиццерий, если он попадет в квартал, где это значение не меньше, чем в любом другом.
Формат ввода
В первой строке заданы через пробел два числа: N и M, оба принадлежат отрезку [1, 1000].N обозначает размерность города в кварталах по горизонтали и по вертикали. M — число пиццерий в городе. В следующих M строках каждая пиццерия описана значениями X,Y,R. X и Y— это квартал, где пиццерия расположена. (1≤X,Y≤N), R— максимальная дистанция, на которую можно заказать доставку. (1≤R≤100). Формат вывода
Выведите одно число — максимально возможное количество пиццерий, из которых доставляют в квартал, где это значение не меньше любого другого.
Пример
Ввод:
8 2
5 3 3
6 1 5
Вывод:
2