Skip to content

viator3m/algorithms

BranchesTags

Repository files navigation

algorithms

Решение алгоритмических задач

Спринт 1. Введение в алгоритмы
  • A. Значения функции

    Ссылка на решение

    Вася делает тест по математике: вычисляет значение функций в различных точках. Стоит отличная погода, и друзья зовут Васю гулять. Но мальчик решил сначала закончить тест и только после этого идти к друзьям. К сожалению, Вася пока не умеет программировать. Зато вы умеете. Помогите Васе написать код функции, вычисляющей y = ax2 + bx + c. Напишите программу, которая будет по коэффициентам a, b, c и числу x выводить значение функции в точке x.

    Формат ввода

    На вход через пробел подаются целые числа a, x, b, c. В конце ввода находится перенос строки.

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

    Выведите одно число — значение функции в точке x.

    • Пример 1

      Ввод
      -8 -5 -2 7
      Вывод
      -183

    • Пример 2

      Ввод
      8 2 9 -10
      Вывод
      40

    • Пример 3

      Ввод
      8 2 9 -10
      Вывод
      40

  • B. Чётные и нечётные числа

    Ссылка на решение

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

    Напишите программу, которая по трём числам определяет, выиграл игрок или нет.

    Формат ввода

    В первой строке записаны три случайных целых числа a, b и c. Числа не превосходят 109 по модулю.

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

    Выведите «WIN», если игрок выиграл, и «FAIL» в противном случае.

    • Пример 1

      Ввод
      1 2 -3
      Вывод
      FAIL

    • Пример 2

      Ввод
      7 11 7
      Вывод
      WIN

    • Пример 3

      Ввод
      6 -2 0
      Вывод
      WIN

  • C. Соседи

    Ссылка на решение

    Дана матрица. Нужно написать функцию, которая для элемента возвращает всех его соседей. Соседним считается элемент, находящийся от текущего на одну ячейку влево, вправо, вверх или вниз. Диагональные элементы соседними не считаются.

    Например, в матрице A соседними элементами для (0, 0) будут 2 и 0. А для (2, 1) –— 1, 2, 7, 7.

    Формат ввода

    В первой строке задано n — количество строк матрицы. Во второй — количество столбцов m. Числа m и n не превосходят 1000. В следующих n строках задана матрица. Элементы матрицы — целые числа, по модулю не превосходящие 1000. В последних двух строках записаны координаты элемента, соседей которого нужно найти. Индексация начинается с нуля.

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

    Напечатайте нужные числа в возрастающем порядке через пробел.

    • Пример 1

      Ввод

      4
3
1 2 3
0 2 6
7 4 1
2 7 0
3
0

      Вывод
      7 7

    • Пример 2

      Ввод

      4
3
1 2 3
0 2 6
7 4 1
2 7 0
0
0

      Вывод
      0 2

  • D. Хаотичность погоды

    Ссылка на решение

    Метеорологическая служба вашего города решила исследовать погоду новым способом.

    • Под температурой воздуха в конкретный день будем понимать максимальную температуру в этот день.
    • Под хаотичностью погоды за n дней служба понимает количество дней, в которые температура строго больше, чем в день до (если такой существует) и в день после текущего (если такой существует). Например, если за 5 дней максимальная температура воздуха составляла [1, 2, 5, 4, 8] градусов, то хаотичность за этот период равна 2: в 3-й и 5-й дни выполнялись описанные условия.

    Определите по ежедневным показаниям температуры хаотичность погоды за этот период.
    Заметим, что если число показаний n=1, то единственный день будет хаотичным.

    Формат ввода

    В первой строке дано число n –— длина периода измерений в днях, 1 ≤ n≤ 105. Во второй строке даны n целых чисел –— значения температуры в каждый из n дней. Значения температуры не превосходят 273 по модулю.

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

    Выведите единственное число — хаотичность за данный период.

    • Пример 1

      Ввод

      7
-1 -10 -8 0 2 0 5

      Вывод
      3

    • Пример 2

      Ввод

      5
1 2 5 4 8

      Вывод
      2

  • E. Самое длинное слово

    Ссылка на решение

    Чтобы подготовиться к семинару, Гоше надо прочитать статью по эффективному менеджменту. Так как Гоша хочет спланировать день заранее, ему необходимо оценить сложность статьи.

    Он придумал такой метод оценки: берётся случайное предложение из текста и в нём ищется самое длинное слово. Его длина и будет условной сложностью статьи.

    Помогите Гоше справиться с этой задачей.

    Формат ввода

    В первой строке дана длина текста L (1 ≤ L ≤ 10^5).

    В следующей строке записан текст, состоящий из строчных латинских букв и пробелов. Слово —– последовательность букв, не разделённых пробелами. Пробелы могут стоять в самом начале строки и в самом её конце. Текст заканчивается переносом строки, этот символ не включается в число остальных L символов.

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

    В первой строке выведите самое длинное слово. Во второй строке выведите его длину. Если подходящих слов несколько, выведите то, которое встречается раньше.

    • Пример 1

      Ввод

      19
i love segment tree

      Вывод

      segment
7
    • Пример 2

      Ввод

      21
frog jumps from river

      Вывод

      jumps
5
  • F. Палиндром

    Ссылка на решение

    Помогите Васе понять, будет ли фраза палиндромом‎. Учитываются только буквы и цифры, заглавные и строчные буквы считаются одинаковыми.

    Решение должно работать за O(N), где N — длина строки на входе.

    Формат ввода

    В единственной строке записана фраза или слово. Буквы могут быть только латинские. Длина текста не превосходит 20000 символов.

    Фраза может состоять из строчных и прописных латинских букв, цифр, знаков препинания.

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

    Выведите «True», если фраза является палиндромом, и «False», если не является.

    • Пример 1

      Ввод

      A man, a plan, a canal: Panama

      Вывод

      True
    • Пример 2

      Ввод

      zo

      Вывод

      False
  • G. Работа из дома

    Ссылка на решение

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

    Формат ввода

    На вход подаётся целое число в диапазоне от 0 до 10000.

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

    Выведите двоичное представление этого числа.

    • Пример 1

      Ввод

      5

      Вывод

      101
    • Пример 2

      Ввод

      14

      Вывод

      1110
  • H. Двоичная система

    Ссылка на решение

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

    Решение должно работать за O(N), где N –— количество разрядов максимального числа на входе.

    Формат ввода

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

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

    Одно число в двоичной системе счисления.

    • Пример 1

      Ввод

      1010
1011

      Вывод
      10101

    • Пример 2

      Ввод

      1
1

      Вывод
      10

  • I. Степень четырёх

    Ссылка на решение

    Напишите программу, которая определяет, будет ли положительное целое число степенью четвёрки.

    Подсказка: степенью четвёрки будут все числа вида 4^n, где n – целое неотрицательное число.

    Формат ввода

    На вход подаётся целое число в диапазоне от 1 до 10000.

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

    Выведите «True», если число является степенью четырёх, «False» –— в обратном случае.

    • Пример 1

      Ввод

      15

      Вывод

      False
    • Пример 2

      Ввод

      16

      Вывод

      True
  • J. Факторизация

    Ссылка на решение

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

    • Число 8 можно представить как 2 × 2 × 2.
    • Число 50 –— как 2 × 5 × 5 (или 5 × 5 × 2, или 5 × 2 × 5). Три варианта отличаются лишь порядком следования множителей. Разложение числа на простые множители называется факторизацией числа.

    Напишите программу, которая производит факторизацию переданного числа.

    Формат ввода

    В единственной строке дано число n (2 ≤ n ≤ 10^9), которое нужно факторизовать.

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

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

    • Пример 1

      Ввод

      8

      Вывод

      2 2 2
    • Пример 2

      Ввод

      13

      Вывод

      13
    • Пример 3

      Ввод

      100

      Вывод

      2 2 5 5
  • K. Списочная форма

    Ссылка на решение

    Вася просил Аллу помочь решить задачу. На этот раз по информатике.

    Для неотрицательного целого числа X списочная форма –— это массив его цифр слева направо. К примеру, для 1231 списочная форма будет [1,2,3,1]. На вход подается количество цифр числа Х, списочная форма неотрицательного числа Х и неотрицательное число K. Числа К и Х не превосходят 10000.

    Нужно вернуть списочную форму числа X + K.

    Формат ввода

    В первой строке — длина списочной формы числа X. На следующей строке — сама списочная форма с цифрами записанными через пробел.

    В последней строке записано число K, 0 ≤ K ≤ 10000.

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

    Выведите списочную форму числа X+K.

    • Пример 1

      Ввод

      4
1 2 0 0
34

      Вывод

      1 2 3 4
    • Пример 2

      Ввод

      2
9 5
17

      Вывод

      1 1 2
  • L. Лишняя буква

    Ссылка на решение

    Васе очень нравятся задачи про строки, поэтому он придумал свою. Есть 2 строки s и t, состоящие только из строчных букв. Строка t получена перемешиванием букв строки s и добавлением 1 буквы в случайную позицию. Нужно найти добавленную букву.

    Формат ввода

    На вход подаются строки s и t, разделённые переносом строки. Длины строк не превосходят 1000 символов. Строки не бывают пустыми.

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

    Выведите лишнюю букву.

    • Пример 1

      Ввод

      abcd
abcde

      Вывод

      e
    • Пример 2

      Ввод

      go
ogg

      Вывод

      g
    • Пример 2

      Ввод

      xtkpx
xkctpx

      Вывод

      c
Спринт 2. Основные структуры данных
  • A. Мониторинг

    Ссылка на решение

    Алла получила задание, связанное с мониторингом работы различных серверов. Требуется понять, сколько времени обрабатываются определённые запросы на конкретных серверах. Эту информацию нужно хранить в матрице, где номер столбца соответствуют идентификатору запроса, а номер строки — идентификатору сервера. Алла перепутала строки и столбцы местами. С каждым бывает. Помогите ей исправить баг.

    Есть матрица размера m × n. Нужно написать функцию, которая её транспонирует.

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

    Например, для матрицы А (слева) транспонированной будет следующая матрица (справа):

    Формат ввода

    В первой строке задано число n — количество строк матрицы. Во второй строке задано m — число столбцов, m и n не превосходят 1000. В следующих n строках задана матрица. Числа в ней не превосходят по модулю 1000.

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

    Напечатайте транспонированную матрицу в том же формате, который задан во входных данных. Каждая строка матрицы выводится на отдельной строке, элементы разделяются пробелами.

    • Пример 1

      Ввод

      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
    • Пример 2

      Ввод

      9
5
-7 -1 0 -4 -9
5 -1 2 2 9
3 1 -8 -1 -7
9 0 8 -8 -1
2 4 5 2 8
-7 10 0 -4 -8
-3 10 -7 10 3
1 6 -7 -5 9
-1 9 9 1 9

      Вывод

      -7 5 3 9 2 -7 -3 1 -1
-1 -1 1 0 4 10 10 6 9
0 2 -8 8 5 0 -7 -7 9
-4 2 -1 -8 2 -4 10 -5 1
-9 9 -7 -1 8 -8 3 9 9
  • B. Список дел

    Ссылка на решение

    Васе нужно распечатать свой список дел на сегодня. Помогите ему: напишите функцию, которая печатает все его дела. Известно, что дел у Васи не больше 5000.

    Формат ввода

    В первой строке задано число n — количество строк матрицы. Во второй строке задано m — число столбцов, m и n не превосходят 1000. В следующих n строках задана матрица. Числа в ней не превосходят по модулю 1000.

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

    Напечатайте транспонированную матрицу в том же формате, который задан во входных данных. Каждая строка матрицы выводится на отдельной строке, элементы разделяются пробелами.

    • Пример 1

      Ввод

      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
    • Пример 2

      Ввод

      9
5
-7 -1 0 -4 -9
5 -1 2 2 9
3 1 -8 -1 -7
9 0 8 -8 -1
2 4 5 2 8
-7 10 0 -4 -8
-3 10 -7 10 3
1 6 -7 -5 9
-1 9 9 1 9

      Вывод

      -7 5 3 9 2 -7 -3 1 -1
-1 -1 1 0 4 10 10 6 9
0 2 -8 8 5 0 -7 -7 9
-4 2 -1 -8 2 -4 10 -5 1
-9 9 -7 -1 8 -8 3 9 9
  • F. Стек - 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».

    • Пример 1

      Ввод

      8
get_max
push 7
pop
push -2
push -1
pop
get_max
get_max

      Вывод

      None
-2 
-2
    • Пример 2

      Ввод

      7
get_max
pop -9
pop
pop-7
push 101
get_max
push -9 -8
0 3
9

      Вывод

      None
error
error
error1
10
  • G. Стек - MaxEffective

    Ссылка на решение

    Реализуйте класс StackMaxEffective, поддерживающий операцию определения максимума среди элементов в стеке. Сложность операции должна быть O(1). Для пустого стека операция должна возвращать None. При этом push(x) и pop() также должны выполняться за константное время.

    Формат ввода

    В первой строке записано одно число n — количество команд, которое не превосходит 10000. В следующих n строках идут команды. Команды могут быть следующих видов:

    • push(x) — добавить число x в стек;
    • pop() — удалить число с вершины стека;
    • get_max() — напечатать максимальное число в стеке; Если стек пуст, при вызове команды get_max() нужно напечатать «None», для команды pop() — «error».
    Формат вывода

    Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».

    • Пример 1

      Ввод

      10
pop
pop
push 4
push -5
push 7
pop
pop
get_max

      Вывод

      error
error
4
    • Пример 2

      Ввод

      10
get_max
push -6
pop
pop
get_max
push 2
get_max
pop
push -2

      Вывод

      None
error
None
21
  • H. Скобочная последовательность

    Ссылка на решение

    Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная.

    Дана скобочная последовательность. Нужно определить, правильная ли она.

    Будем придерживаться такого определения:

    • пустая строка —– правильная скобочная последовательность;
    • правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность;
    • правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная.

    На вход подаётся последовательность из скобок трёх видов: [], (), {}.
    Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.

    Формат ввода

    На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.

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

    Выведите «True» или «False».

    • Пример 1

      Ввод

      {[()]}

      Вывод

      True
    • Пример 2

      Ввод

      ()

      Вывод

      True
  • I. Ограниченная очередь

    Ссылка на решение

    Астрологи объявили день очередей ограниченного размера. Тимофею нужно написать класс MyQueueSized, который принимает параметр max_size, означающий максимально допустимое количество элементов в очереди.

    Помогите ему —– реализуйте программу, которая будет эмулировать работу такой очереди. Функции, которые надо поддержать, описаны в формате ввода.

    Формат ввода

    В первой строке записано одно число — количество команд, оно не превосходит 5000. Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000. Далее идут команды по одной на строке. Команды могут быть следующих видов:

    • push(x) — добавить число x в очередь;
    • pop() — удалить число из очереди и вывести на печать;
    • peek() — напечатать первое число в очереди;
    • size() — вернуть размер очереди; При превышении допустимого размера очереди нужно вывести «error». При вызове операций pop() или peek() для пустой очереди нужно вывести «None».
    Формат вывода

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

    • Пример 1

      Ввод

      8
2
peek
push 5
push 2
peek
size
size
push 1

      Вывод

      None
5
2
    • Пример 2

      Ввод

      10
1
push 1
size
push 3
size
push 1
pop
push 1
pop

      Вывод

      1
error
1
error
  • J. Списочная очередь

    Ссылка на решение

    Любимый вариант очереди Тимофея — очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:

    • get() — вывести элемент, находящийся в голове очереди, и удалить его. Если очередь пуста, то вывести «error».
    • put(x) — добавить число x в очередь
    • size() — вывести текущий размер очереди
    Формат ввода

    В первой строке записано количество команд n — целое число, не превосходящее 1000. В каждой из следующих n строк записаны команды по одной строке.

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

    Выведите ответ на каждый запрос по одному в строке.

    • Пример 1

      Ввод

      10
put -34
put -23
get
size
get
size
get
get

      Вывод

      -34
1
-23
0
error
error
1
    • Пример 2

      Ввод

      6
put -66
put 981
size
size3
get
get

      Вывод

      2
2
-66
98
  • K. Рекурсивные числа Фибоначчи

    Ссылка на решение

    У Тимофея было n(0 ≤ n ≤ 32) стажёров. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными —– они сделали по одному коммиту. Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Тогда выполняется следующее: F0 = F1 = 1. Для всех i ≥ 2 выполнено Fi = F(i−1) + F(i−2). Определите, сколько кода напишет следующий стажёр –— найдите Fn . Решение должно быть реализовано рекурсивно.

    Формат ввода

    На вход подаётся n — целое число в диапазоне от 0 до 32.

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

    Нужно вывести Fn.

    • Пример 1

      Ввод

      3

      Вывод

      3
    • Пример 2

      Ввод

      0

      Вывод

      1
  • L. Фибоначчи по модулю

    Ссылка на решение

    У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 106) человек. Каждый стажёр хотел быть лучше своих предшественников, поэтому 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 цифр, то выведите само число без ведущих нулей.

    • Пример 1

      Ввод

      3 1

      Вывод

      3
    • Пример 2

      Ввод

      10 1

      Вывод

      9
Спринт 3. Рекурсии и сортировки
  • A. Генератор скобок

    Ссылка на решение с помощью стека
    Ссылка на решение с помощью рекурсии

    Рита по поручению Тимофея наводит порядок в правильных скобочных последовательностях (ПСП), состоящих только из круглых скобок (). Для этого ей надо сгенерировать все ПСП длины 2n в алфавитном порядке —– алфавит состоит из ( и ) и открывающая скобка идёт раньше закрывающей.

    Помогите Рите —– напишите программу, которая по заданному n выведет все ПСП в нужном порядке.

    Рассмотрим второй пример. Надо вывести ПСП из четырёх символов. Таких всего две:

    1. (())
    2. ()() (()) идёт раньше ()(), так как первый символ у них одинаковый, а на второй позиции у первой ПСП стоит (, который идёт раньше ). Например, для матрицы А (слева) транспонированной будет следующая матрица (справа):
    Формат ввода

    На вход функция принимает n — целое число от 0 до 10.

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

    Функция должна напечатать все возможные скобочные последовательности заданной длины в алфавитном (лексикографическом) порядке.

    • Пример 1

      Ввод

      3

      Вывод

      ((()))
(()())
(())()
()(())
()()()
    • Пример 2

      Ввод

      2

      Вывод

      (())
()()
  • B. Комбинации

    Ссылка на решение

    На клавиатуре старых мобильных телефонов каждой цифре соответствовало несколько букв. Примерно так:

    2:'abc',
    3:'def',
    4:'ghi',
    5:'jkl',
    6:'mno',
    7:'pqrs',
    8:'tuv',
    9:'wxyz'

    Вам известно в каком порядке были нажаты кнопки телефона, без учета повторов. Напечатайте все комбинации букв, которые можно набрать такой последовательностью нажатий.

    Формат ввода

    На вход подается строка, состоящая из цифр 2-9 включительно. Длина строки не превосходит 10 символов.

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

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

    • Пример 1

      Ввод

      23

      Вывод

      ad ae af bd be bf cd ce cf
    • Пример 2

      Ввод

      92

      Вывод

      wa wb wc xa xb xc ya yb yc za zb zc
  • C. Подпоследовательность

    Ссылка на решение

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

    Формат ввода

    В первой строке записана строка s.

    Во второй —- строка t.

    Обе строки состоят из маленьких латинских букв, длины строк не превосходят 150000. Строки не могут быть пустыми.

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

    Выведите True, если s является подпоследовательностью t, иначе —– False.

    • Пример 1

      Ввод

      abc
ahbgdcu

      Вывод

      True
    • Пример 2

      Ввод

      abcp
ahpc

      Вывод

      False
  • D. Печеньки

    Ссылка на решение

    К Васе в гости пришли одноклассники. Его мама решила угостить ребят печеньем.

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

    Каждый ребёнок может взять не больше одного печенья.

    Формат ввода

    В первой строке записано n —– количество детей.

    Во второй —– n чисел, разделённых пробелом, каждое из которых –— фактор жадности ребёнка. Это натуральные числа, не превосходящие 1000.

    В следующей строке записано число m –— количество печенек.

    Далее —– m натуральных чисел, разделённых пробелом —– размеры печенек. Размеры печенек не превосходят 1000.

    Оба числа n и m не превосходят 10000.

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

    Нужно вывести одно число –— количество детей, которые останутся довольными

    • Пример 1

      Ввод

      2
1 2
3
2 1 3

      Вывод

      2
    • Пример 2

      Ввод

      3
2 1 3
2
1 1

      Вывод

      1
  • E. Покупка домов

    Ссылка на решение

    Тимофей решил купить несколько домов на знаменитом среди разработчиков Алгосском архипелаге. Он нашёл n объявлений о продаже, где указана стоимость каждого дома в алгосских франках. А у Тимофея есть k франков. Помогите ему определить, какое наибольшее количество домов на Алгосах он сможет приобрести за эти деньги.

    Формат ввода

    В первой строке через пробел записаны натуральные числа n и k.

    n — количество домов, которые рассматривает Тимофей, оно не превосходит 100000;

    k — общий бюджет, не превосходит 100000;

    В следующей строке через пробел записано n стоимостей домов. Каждое из чисел не превосходит 100000. Все стоимости — натуральные числа.

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

    Выведите одно число —– наибольшее количество домов, которое может купить Тимофей.

    • Пример 1

      Ввод

      3 300
999 999 999

      Вывод

      0
    • Пример 2

      Ввод

      3 1000
350 999 200

      Вывод

      2
  • F. Периметр треугольника

    Ссылка на решение

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

    Напомним, что из трёх отрезков с длинами a ≤ b ≤ c можно составить треугольник, если выполнено неравенство треугольника: c < a + b

    Разберём пример: даны длины сторон 6, 3, 3, 2. Попробуем в качестве наибольшей стороны выбрать 6. Неравенство треугольника не может выполниться, так как остались 3, 3, 2 —– максимальная сумма из них равна 6.

    Без шестёрки оставшиеся три отрезка уже образуют треугольник со сторонами 3, 3, 2. Неравенство выполняется: 3 < 3 + 2. Периметр равен 3 + 3 + 2 = 8.

    Формат ввода

    В первой строке записано количество отрезков n, 3≤ n≤ 10000.

    Во второй строке записано n неотрицательных чисел, не превосходящих 10 000, –— длины отрезков.

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

    Нужно вывести одно число —– наибольший периметр треугольника.

    Гарантируется, что тройка чисел, которая может образовать треугольник, всегда есть.

    • Пример 1

      Ввод

      4
6 3 3 2

      Вывод

      8
    • Пример 2

      Ввод

      6
5 3 7 2 8 3

      Вывод

      20
  • G. Гардероб

    Ссылка на решение

    Рита решила оставить у себя одежду только трёх цветов: розового, жёлтого и малинового. После того как вещи других расцветок были убраны, Рита захотела отсортировать свой новый гардероб по цветам. Сначала должны идти вещи розового цвета, потом —– жёлтого, и в конце —– малинового. Помогите Рите справиться с этой задачей.

    Примечание: попробуйте решить задачу за один проход по массиву!

    Формат ввода

    В первой строке задано количество предметов в гардеробе: n –— оно не превосходит 1000000. Во второй строке даётся массив, в котором указан цвет для каждого предмета. Розовый цвет обозначен 0, жёлтый —– 1, малиновый –— 2.

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

    Нужно вывести в строку через пробел цвета предметов в правильном порядке.

    • Пример 1

      Ввод

      7
0 2 1 2 0 0 1

      Вывод

      0 0 0 1 1 2 2
    • Пример 2

      Ввод

      5
2 1 2 0 1

      Вывод

      0 1 1 2 2
  • H. Большое число

    Ссылка на решение

    Вечером ребята решили поиграть в игру «Большое число». Даны числа. Нужно определить, какое самое большое число можно из них составить.

    Формат ввода

    В первой строке записано n — количество чисел. Оно не превосходит 100. Во второй строке через пробел записаны n неотрицательных чисел, каждое из которых не превосходит 1000.

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

    Нужно вывести самое большое число, которое можно составить из данных чисел.

    • Пример 1

      Ввод

      3
15 56 2

      Вывод

      56215
    • Пример 2

      Ввод

      3
1 783 2

      Вывод

      78321
  • I. Любители конференций

    Ссылка на решение

    На IT-конференции присутствовали студенты из разных вузов со всей страны. Для каждого студента известен ID университета, в котором он учится.

    Тимофей предложил Рите выяснить, из каких k вузов на конференцию пришло больше всего учащихся.

    Формат ввода

    В первой строке дано количество студентов в списке —– n (1 ≤ n ≤ 15 000).

    Во второй строке через пробел записаны n целых чисел —– ID вуза каждого студента. Каждое из чисел находится в диапазоне от 0 до 10 000.

    В третьей строке записано одно число k.

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

    Выведите через пробел k ID вузов с максимальным числом участников.
    Они должны быть отсортированы по убыванию популярности (по количеству гостей от конкретного вуза). Если более одного вуза имеет одно и то же количество учащихся, то выводить их ID нужно в порядке возрастания.

    • Пример 1

      Ввод

      7
1 2 3 1 2 3 4
3

      Вывод

      1 2 3
    • Пример 2

      Ввод

      6
1 1 1 2 2 3
1

      Вывод

      1
  • J. Пузырёк

    Ссылка на решение

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

    Её алгоритм следующий (сортируем по неубыванию):

    На каждой итерации проходим по массиву, поочередно сравнивая пары соседних элементов. Если элемент на позиции i больше элемента на позиции i + 1, меняем их местами. После первой итерации самый большой элемент всплывёт в конце массива. Проходим по массиву, выполняя указанные действия до тех пор, пока на очередной итерации не окажется, что обмены больше не нужны, то есть массив уже отсортирован. После не более чем n – 1 итераций выполнение алгоритма заканчивается, так как на каждой итерации хотя бы один элемент оказывается на правильной позиции.

    Помогите Гоше написать код алгоритма.

    Формат ввода

    В первой строке на вход подаётся натуральное число n — длина массива, 2 ≤ n ≤ 1000. Во второй строке через пробел записано n целых чисел. Каждое из чисел по модулю не превосходит 1000.

    Обратите внимание, что считывать нужно только 2 строки: значение n и входной массив.

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

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

    • Пример 1

      Ввод

      5
4 3 9 2 1

      Вывод

      3 4 2 1 9
3 2 1 4 9
2 1 3 4 9
1 2 3 4 9
    • Пример 2

      Ввод

      5
12 8 9 10 11

      Вывод

      8 9 10 11 12
  • K. Сортировка слиянием

    Ссылка на решение

    Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию merge и функцию merge_sort.

    • Функция merge принимает два отсортированных массива, сливает их в один отсортированный массив и возвращает его. Если требуемая сигнатура имеет вид merge(array, left, mid, right), то первый массив задаётся полуинтервалом [left,mid) массива array, а второй – полуинтервалом [mid,right) массива array.
    • Функция merge_sort принимает некоторый подмассив, который нужно отсортировать. Подмассив задаётся полуинтервалом — его началом и концом. Функция должна отсортировать передаваемый в неё подмассив, она ничего не возвращает.
    • Функция merge_sort разбивает полуинтервал на две половинки и рекурсивно вызывает сортировку отдельно для каждой. Затем два отсортированных массива сливаются в один с помощью merge.

    Заметьте, что в функции передаются именно полуинтервалы [begin,end), то есть правый конец не включается. Например, если вызвать merge_sort(arr, 0, 4), где arr=[4,5,3,0,1,2], то будут отсортированы только первые четыре элемента, изменённый массив будет выглядеть как arr=[0,3,4,5,1,2].

    Реализуйте эти две функции.

About

Решение алгоритмических задач

Topics

python algorithms data-structures problems pure-python

Resources

Readme
Activity

Stars

8 stars

Watchers

1 watching

Forks

2 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages