github тренировки по алгоритмам

Github тренировки по алгоритмам

Задачи по алгоритмам и структурам данных

Основные структуры данных.

A. Кружки. Вывод уникальных элементов по одному на строке, в порядке появления во входных данных.
B. Мониторинг. Транспонирование матрицы
C. Подстроки. Длина наибольшей подстроки, которая не содержит повторяющиеся символы
D. Соседи. Дана матрица. Нужно написать функцию, которая для элемента возвращает всех его соседей.

Односвязный список (Linked List).

Реализована структура данных список и вставка нового узла в список
E. Список дел. Заполнение связного списка (данные подаются в обратном порядке)
F. Нелюбимое дело. Удаление элемента из односвязного списка (ф-ция принимает на вход голову списка и номер удаляемого дела и возвращает голову обновлённого списка)
G. Заботливая мама. Определение индекса первого вхождения передаваемого ей на вход значения в связном списке

Двусвязный список (Doubly Linked Node).

Реализована структура данных двусвязный список.
H. Все наоборот. Функция, которая вернёт двусвязный список в обратном порядке

M. Очередь. Реализована структура данных очередь. Реализованы операции добавления, удаления, получения элемента, определение текущего размера, и метод, показывающий, пуста ли очередь или нет. Очередь реализована на основе массива.
N. Ограниченная очередь. Реализован класс MyQueueSized(), который принимает параметр max_size, означающий максимально допустимое количество элементов в очереди.
O. Шифрование. Число анаграмм шаблона в строке.
P. Списочная очередь. Реализована очередь, написанная с использованием связного списка.

Q. Дек. Эффективная реализация дека. Все операции работают за O(1)

Проект: Структуры данных.

A. Калькулятор. В единственной строке дано выражение, записанное в обратной польской нотации. Производится вычисление выражения.
B. Циклы. Программа определяет есть ли цикл в связном списке

Базовый и рекурсивный случай.

E. Кондратиева система шифрования. Вычисление факториала
F. Циклический факториал. Реализация факториала при помощи цикла

Преимущества и недостатки рекурсии.

L. Банкомат. Найти число способов, которым можно набрать нужную сумму используя заданные типы монет (количество монет каждого типа бесконечно).
M. Земельный участок. Дан прямоугольный участок. Найти максимально возможный размер квадратных участков.
N. Безупречные коэффициенты. НОД(x,y) = ax + by. Найти НОД(x,y) и a, b.

Примеры задач на рекурсию.

A. Расписание. Дано расписание предметов. Нужно составить расписание, в соответствии с которым в классе можно будет провести как можно больше уроков.
B. Биржа. Дан массив цен акций. На i-й позиции массива — цена в i-й день. Акции можно покупать и продавать, но только по одной штуке. В одно время не должно быть более одной открытой транзакции. Какую максимальную прибыль она может получить.
C. Подпоследовательность. Даны 2 строки, и нужно понять, является ли первая из них подпоследовательностью второй.
D. Ценный рюкзак. В n строках записано по 2 числа, разделенные пробелом: стоимость предмета и его вес. Найти те предметы, которыми можно было наполнить рюкзак т.ч. его стоимость была максимальной.
E. Печеньки. К Васе в гости пришли одноклассники. Его мама решила угостить ребят печеньем. Печенья могут быть разного размера. У каждого ребёнка есть фактор жадности — минимальный размер печенья, которое он возьмёт. Нужно выяснить, сколько ребят останутся довольными.
F. Отсортированные строки. Дан набор строк одинаковой длины, состоящих из маленьких латинских букв. Нужно определить, какое минимальное число позиций в каждой из строк нужно удалить, чтобы буквы в строках, соответствующие каждому индексу из оставшихся, были лексикографически отсортированы по неубыванию.
G. Закручивающаяся спираль. В n строках записано по m чисел. Нужно вывести на печать по спирали элементы матрицы: начиная с левого верхнего угла вправо.
H. Возрастающий подмассив. Найти длину наибольшего возрастающего подмассива.
I. Одинаковые суммы. Определить, возможно ли разделить массив на две части так чтобы суммы элементов в них были одинаковыми
K. Ипотека. Дан массив из стоимостей домов и фиксированная сумма. Нужно определить какое максимальное количество домов можно приобрести на данную сумму.
L. Лестница Для каждой ступеньки известно, на какое максимальное количество ступенек вверх с неё можно допрыгнуть. Нужно помочь Евлампии определить, сможет ли она добраться с нижней ступеньки на верхнюю.

Проект: Жадные алгоритмы и Рекурсия.

A. Фотокопии. Всего есть N датацентров c разной вместимостью в шт. фотографий. Каждую фотографию нужно хранить в двух экземплярах. Нужно вывести число, равное максимальному количеству фотографий, для которых можно хранить копии в этих датацентрах.
B. Поиск в сломанном массиве. Данные имеют 1 «дефект» в сортировке. Необходимо найти индекс требуемого элемента.

A. Пузырек. Реализация алгоритма пузырьковой сортировки.
B. Сортировка вставками. Реализация алгоритма сортировки вставкой.

Алгоритм сортировки слиянием для связного списка.

Реализован алгоритм сортировки слиянием для связного списка.

A. Большое число. Даны числа. Нужно определить, какое самое большое число можно из них составить.
B. Radix Sort. Реализация алгоритма поразрядной сортировки.

A. Счастливый билет. Дано число. С этим числом производят преобразования: заменяют каждую цифру числа её второй степенью, складывают получившиеся значения, повторяют алгоритм для результата предыдущего шага. Станет ли это число после данных преобразований равным 1?
B. Легкие числа. Количество простых чисел меньше заданного.
C. Анаграммная группировка. Дан перечень слов. Нужно вывести списки индексов слов являющиеся анаграммами.
D. Строковые числа. Выведите строковое представление результата вычисления выражения a/b. Если при делении двух чисел получается периодическая дробь, нужно вывести период в скобках.
E. Соревнование Поиск максимального числа подряд идущих раундов, по результатам которых получается ничья.
F. Странное сравнение. Даны две строки. Нужно определить существует ли между этими строками изоморфизм, заданный заменой букв.
G. МногоГоша. Дана строка, состоящая из заданных букв. Нужно найти все подстроки длины 10, которые встречаются более одного раза.
H. Общий подмассив. Дано два массива чисел. Определить максимальную длину подстроки лежащую в пересечении множества подстрок.
I. Полиномиальный хеш. Реализована функция, вычисляющая полиномиальный хеш строки.
L. Сумма четверок. Дан массив чисел и целевое число. Нужно вывести все множества четверок чисел из массива в сумме дающие целевое число.
M. Проверка паттерна. Необходимо проверить текст на соответствие некоторому паттерну, который задан в виде последовательности букв. Между буквами паттерна и словами текста должно устанавливаться взаимно однозначное соответствие при сохранении порядка букв паттерна и слов текста.
N. Самый длинный палиндром. Необходимо узнать, палиндром какой наибольшей длины можно составить из букв данной строки.
O. Периметр. На клетчатом поле из нулей нарисована некоторая односвязная фигура из единичек. Найдите периметр этой фигуры, каждая сторона клетки имеет длину 1.
P. Собери словарь. Собирается словарь из двух списков.

A. Кондратиева пирамида. Нужно отсортировать данные так, чтобы они удовлетворяли следующим требованиям: Если сумма набранных очков участника A больше, чем у участника В, то А должен идти в списке раньше. При подсчете суммы нужно учитывать только положительные значения очков. Если суммы равны, то первым должен идти участник, чье имя лексикографически меньше. При совпадении имен раньше должен идти участник, который во входных данных находится позже. При этом, если из имени участника можно составить английский вариант имени Кондратий (например, если имя nekondratiy или drkonxxxiyatt), то все правила отменяются. Он должен идти в списке раньше. Если таких участников больше одного, то раньше должен идти тот, кто находится позже во входных данных. (Заработанные очки не рассматриваются).

About

Задачи по алгоритмам и структурам данных. Яндекс Практикум

Источник

Github тренировки по алгоритмам

Введение в алгориты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

У вас есть несколько камней известного веса w1, …, wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.

Ввод содержит количество камней n (1 ≤ n ≤ 20) и веса камней w1, …, wn (1 ≤ wi ≤ 100 000) — целые, разделённые пробельными символами.

Ваша программа должна вывести одно число — минимальную разность весов двух куч.

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Гиперпереход, открытый ещё в начале XXI-го века, и сейчас остаётся основным способом перемещения на расстояния до сотен тысяч парсеков. Но совсем недавно физиками открыто новое явление. Оказывается, длительностью альфа-фазы перехода можно легко управлять. Корабль, находящийся в альфа-фазе перехода, накапливает гравитационный потенциал. Чем больше накопленный гравитационный потенциал корабля, тем меньше энергии потребуется ему на прыжок сквозь пространство. Ваша цель — написать программу, которая позволит кораблю за счёт выбора времени начала альфа-фазы и её длительности накопить максимальный гравитационный потенциал. В самой грубой модели грави-интенсивность — это последовательность целых чисел pi. Будем считать, что если альфа-фаза началась в момент i и закончилась в момент j, то накопленный в течение альфа-фазы потенциал — это сумма всех чисел, стоящих в последовательности на местах от i до j.

В первой строке входа записано целое число N — длина последовательности, отвечающей за грави-интенсивность (0 ≤ N ≤ 60000). Далее идут N строк, в каждой записано целое число pi (−30000 ≤ pi ≤ 30000).

Максимальный гравитационный потенциал, который может накопить корабль в альфа-фазе прыжка. Считается, что потенциал корабля в начальный момент времени равен нулю.

2025. Стенка на стенку

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Бокс, каратэ, самбо… Классические боевые единоборства пресытили аудиторию. Поэтому известный спортивный канал запускает новый формат соревнований, основанный на традиционной русской забаве — боях стенка на стенку. В соревновании могут участвовать от двух до k команд, каждая из которых будет соперничать с остальными. Всего в соревновании примут участие n бойцов. Перед началом боя они должны разделиться на команды, каждый боец должен войти ровно в одну команду. За время боя два бойца сразятся, если они состоят в разных командах. Организаторы считают, что популярность соревнований будет тем выше, чем больше будет количество схваток между бойцами. Помогите распределить бойцов по командам так, чтобы максимизировать количество схваток между бойцами, и выведите это количество.

В первой строке дано количество тестов T (1 ≤ T ≤ 10). В следующих T строках перечислены тесты. В каждой из них записаны целые числа n и k через пробел (2 ≤ k ≤ n ≤ 104).

Для каждого теста в отдельной строке выведите одно целое число — ответ на задачу.

1207. Медиана на плоскости

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ

На плоскости находятся N точек (N чётно). Никакие три точки не лежат на одной прямой. Ваша задача — выбрать две точки так, что прямая линия, проходящая через них, делит множество точек на две части одинакового размера.

Первая строка содержит целое число N (4 ≤ N ≤ 10 000). Каждая из следующих N строк содержит пары целых чисел xi, yi (−106 ≤ xi, yi ≤ 106) — координаты i-й точки.

Выведите номера выбранных точек.

1604. В стране дураков

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Главный бульдог-полицейский Страны Дураков решил ввести ограничение скоростного режима на автомобильной трассе, ведущей от Поля Чудес к пруду Черепахи Тортиллы. Для этого он заказал у Папы Карло n знаков ограничения скорости. Папа Карло слабо разбирался в дорожном движении и поэтому изготовил знаки с разными ограничениями на скорость: 49 км/ч, 34 км/ч, 42 км/ч, и т.д. Всего получилось k различных ограничений: n1 знаков с одним ограничением, n2 знаков со вторым ограничением, и т.д. (n1 + … + nk = n) Бульдог-полицейский ничуть не расстроился, получив такие знаки, напротив, он решил извлечь из этого экономическую выгоду. Дело в том, что по Правилам дорожного движения Страны Дураков ограничение на скорость действует вплоть до следующего знака. Если на знаке написано число 60, это означает, что участок от данного знака до следующего нужно проехать ровно со скоростью 60 километров в час — не больше и не меньше. Бульдог распорядился расставить знаки так, чтобы обогатившимся на Поле Чудес автолюбителям во время своего движения по трассе приходилось как можно больше раз менять скорость. Для этого нужно расставить имеющиеся знаки в правильном порядке. Если Вы поможете бульдогу это сделать, то он готов будет поделиться с Вами частью своих доходов.

В первой строке дано число k — количество различных типов знаков с ограничением скорости (1 ≤ k ≤ 10000). Во второй строке через пробел перечислены целые положительные числа n1, …, nk. Сумма всех ni не превосходит 10000.

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

1726. Кто ходит в гости…

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Программный комитет школьных соревнований по программированию, проходящих в УрГУ — многочисленная, весёлая и дружная команда. Дружная настолько, что общения в университете им явно не хватает, поэтому они часто ходят друг к другу в гости. Все ребята в программном комитете очень спортивные и ходят только пешком. Однажды хранитель традиций олимпиадного движения УрГУ подумал, что на пешие прогулки от дома к дому члены программного комитета тратят слишком много времени, которое могли бы вместо этого потратить на придумывание и подготовку задач. Чтобы доказать это, он решил посчитать, какое расстояние в среднем преодолевают члены комитета, когда ходят друг к другу в гости. Хранитель традиций достал карту Екатеринбурга, нашёл на ней дома всех членов программного комитета и выписал их координаты. Но координат оказалось так много, что хранитель не смог справиться с этой задачей самостоятельно и попросил вас помочь ему. Город Екатеринбург представляет собой прямоугольник со сторонами, ориентированными по сторонам света. Все улицы города идут строго с запада на восток или с севера на юг, проходя через весь город от края до края. Дома всех членов программного комитета расположены строго на пересечении каких-то двух перпендикулярных улиц. Известно, что все члены комитета ходят только по улицам, поскольку идти по тротуару гораздо приятнее, чем по дворовым тропинкам. И, конечно, при переходе от дома к дому они всегда выбирают кратчайший путь. Программный комитет очень дружный, и все его члены ходят в гости ко всем одинаково часто.

Первая строка содержит целое число n — количество членов программного комитета (2 ≤ n ≤ 105). В i-й из следующих n строк через пробел записаны целые числа xi, yi — координаты дома i-го члена программного комитета (1 ≤ xi, yi ≤ 106).

Выведите среднее расстояние, которое проходит член программного комитета от своего дома до дома своего товарища, округлённое вниз до целых.

Ограничение времени: 2.0 секунды Ограничение памяти: 64 МБ

Hacker Bill has accidentally lost all the information from his workstation’s hard drive and he has no backup copies of its contents. He does not regret for the loss of the files themselves, but for the very nice and convenient directory structure that he had created and cherished during years of work. Fortunately, Bill has several copies of directory listings from his hard drive. Using those listings he was able to recover full paths (like «WINNT\SYSTEM32\CERTSRV\CERTCO

1\X86″) for some directories. He put all of them in a file by writing each path he has found on a separate line. Your task is to write a program that will help Bill to restore his state of the art directory structure by providing nicely formatted directory tree.

The first line of the input contains single integer number N (1 ≤ N ≤ 500) that denotes a total number of distinct directory paths. Then N lines with directory paths follow. Each directory path occupies a single line and does not contain any spaces, including leading or trailing ones. No path exceeds 80 characters. Each path is listed once and consists of a number of directory names separated by a back slash («»). Each directory name consists of 1 to 8 uppercase letters, numbers, or the special characters from the following list: exclamation mark, number sign, dollar sign, percent sign, ampersand, apostrophe, opening and closing parenthesis, hyphen sign, commercial at, circumflex accent, underscore, grave accent, opening and closing curly bracket, and tilde («!#$%&'()-@^_`<>

Write to the output the formatted directory tree. Each directory name shall be listed on its own line preceded by a number of spaces that indicate its depth in the directory hierarchy. The subdirectories shall be listed in lexicographic order immediately after their parent directories preceded by one more space than their parent directory. Top level directories shall have no spaces printed before their names and shall be listed in lexicographic order. See sample below for clarification of the output format.

1\X86SYSTEM32CERTSRVCERTO

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Стол для монобильярда, установленный в игровом доме уездного города N, оказался очень прибыльным вложением. До того, как в городе появился небезызвестный господин Чичиков. Раз за разом он выигрывал, и хозяин, подсчитывая убытки, понимал, что дело тут нечисто. Однако уличить подлеца в жульничестве не удавалось до прибытия в город N ревизора из Петербурга. Правила игры в монобильярд очень просты: нужно последовательно закатить в единственную лузу шары с номерами 1, 2, …, N (именно в этом порядке). Пока господин Чичиков играл, ревизор несколько раз подходил к столу и забирал из лузы последний закатившийся туда шар. В конце концов, оказалось, что Чичиков закатил в лузу все шары, а ревизор все шары достал и обследовал. Аферист утверждал, что закатил шары в правильном порядке. Хозяин понял, что это его шанс: ревизор должен помнить, в каком порядке он доставал шары. Однако так ли легко будет доказать жульничество?

В первой строке записано целое число N — количество бильярдных шаров (1 ≤ N ≤ 100000). В следующих N строках даны номера этих шаров в том порядке, в котором ревизор забирал их из лузы.

Выведите слово «Cheater», если Чичиков не мог закатить все N шаров в правильном порядке. Иначе выведите «Not a proof».

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

1521. Военные учения 2

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Единственная строка содержит целые числа N (1 ≤ N ≤ 100000) и K (1 ≤ K ≤ N).

Вывести через пробел номера солдат в порядке их выбывания из круга.

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ

В первой строке записано число n — количество миллиардеров (1 ≤ n ≤ 10000). Каждая из следующих n строк содержит данные на определённого человека: его имя, название города, где он находился в первый день данного периода, и размер состояния. В следующей строке записаны два числа: m — количество дней, о которых есть данные (1 ≤ m ≤ 50000), k — количество зарегистрированных перемещений миллиардеров (0 ≤ k ≤ 50000). Следующие k строк содержат список перемещений в формате: номер дня (от 1 до m − 1), имя человека, название города назначения. Вы можете считать, что миллиардеры путешествуют не чаще одного раза в день, и что они отбывают поздно вечером и прибывают в город назначения рано утром следующего дня. Список упорядочен по возрастанию номера дня. Все имена и названия городов состоят не более чем из 20 латинских букв, регистр букв имеет значение. Состояния миллиардеров лежат в пределах от 1 до 100 миллиардов

В каждой строке должно содержаться название города и, через пробел, количество дней, в течение которых этот город лидировал по общему состоянию миллиардеров, находящихся в нём. Если таких дней не было, пропустите этот город. Города должны быть отсортированы по алфавиту (используйте обычный порядок символов: ABC. Zabc. z).

1080. Раскраска карты

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Рассмотрим географическую карту с N странами, занумерованными от 1 до N (0

В первой строке записано число N. Из следующих N строк i-я строка содержит номера стран, с которыми i-я страна имеет границу. Каждое целое число в i-й строке больше, чем i, кроме последнего, которое равно 0 и обозначает конец списка соседей i-й страны. Если строка содержит 0, это значит, что i-я страна не соединена ни с одной страной с бoльшим номером.

Вывод содержит ровно одну строку. Если раскраска возможна, эта строка должна содержать список нулей и единиц без разделителей между ними. i-я цифра в этой последовательности обозначает цвет i-й страны. 0 соответствует красному цвету, единица — синему. Если раскраска невозможна, выведите целое число –1.

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

1450. Российские газопроводы

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ

Сеть российских газопроводов представляет собой N перекачивающих станций, некоторые из которых соединены газопроводами. Для каждого из M газопроводов известны номера станций A[i] и B[i], которые он соединяет, и его прибыльность C[i], т.е. то количество долларов, которое будет ежесуточно приносить в виде налогов перекачка газа по этому газопроводу. Каждая пара станций соединена не более чем одним газопроводом. Сеть была построена советскими инженерами, которые точно знали, что газ поставляется из месторождений Украины в Сибирь, а не наоборот. Поэтому все газопроводы являются однонаправленными, т.е. для каждого газопровода перекачка газа возможна только в направлении из станции с номером A[i] на станцию с номером B[i]. Более того, для любых двух станций X и Y верно, что если возможна перекачка газа из X на Y (возможно, через промежуточные станции), то обратная перекачка из Y на X невозможна. Известно, что газ поступает на начальную станцию с номером S и отгружается потребителям на конечной станции с номером F. Президент потребовал от Правительства указать маршрут (т.е. линейную последовательность попарно соединённых газопроводами станций) перекачки газа из начальной станции на конечную, причём прибыльность этого маршрута должна быть максимальной. Под прибыльностью маршрута понимается суммарная прибыльность входящих в него газопроводов. К сожалению, Президент не учёл того факта, что многие газопроводы изначальной сети уже давно прекратили существование, в результате чего может оказаться, что перекачка газа из начальной станции на конечную вообще невозможна.

Первая строка содержит целые числа N (2 ≤ N ≤ 500) и M (0 ≤ M ≤ 124750). Каждая из следующих M строк содержит целые числа A[i], B[i] (1 ≤ A[i], B[i] ≤ N) и C[i] (1 ≤ C[i] ≤ 10000) для соответствующего газопровода. Последняя строка содержит целые числа S и F (1 ≤ S, F ≤ N; S ≠ F).

Если искомый маршрут существует, выведите его прибыльность. Иначе выведите «No solution».

Источник