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

Вася делает тест по математике: вычисляет значение функций в различных точках. Стоит отличная погода, и друзья зовут Васю гулять. Но мальчик решил сначала закончить тест и только после этого идти к друзьям. К сожалению, Вася пока не умеет программировать. Зато вы умеете. Помогите Васе написать код функции, вычисляющей 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

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

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

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

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

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

• Пример 1

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

• Пример 2

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

• Пример 3

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

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

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

Например, в матрице 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

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

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

• Под температурой воздуха в конкретный день будем понимать максимальную температуру в этот день.
• Под хаотичностью погоды за 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

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

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

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

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

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

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

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

• Пример 1

  Ввод

  19
  i love segment tree
  

  Вывод

  segment
  7
  

• Пример 2

  Ввод

  21
  frog jumps from river
  

  Вывод

  jumps
  5
  

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

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

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

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

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

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

• Пример 1

  Ввод

  A man, a plan, a canal: Panama
  

  Вывод

  True
  

• Пример 2

  Ввод

  zo
  

  Вывод

  False
  

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

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

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

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

• Пример 1

  Ввод

  5
  

  Вывод

  101
  

• Пример 2

  Ввод

  14
  

  Вывод

  1110
  

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

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

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

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

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

• Пример 1

  Ввод

  1010
  1011
  

  Вывод
  10101

• Пример 2

  Ввод

  1
  1
  

  Вывод
  10

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

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

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

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

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

• Пример 1

  Ввод

  15
  

  Вывод

  False
  

• Пример 2

  Ввод

  16
  

  Вывод

  True
  

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

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

• Число 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
  

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

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

Для неотрицательного целого числа 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
  

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

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

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

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

• Пример 1

  Ввод

  abcd
  abcde
  

  Вывод

  e
  

• Пример 2

  Ввод

  go
  ogg
  

  Вывод

  g
  

• Пример 2

  Ввод

  xtkpx
  xkctpx
  

  Вывод

  c
  

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

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

Есть матрица размера 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
  

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

Васе нужно распечатать свой список дел на сегодня. Помогите ему: напишите функцию, которая печатает все его дела. Известно, что дел у Васи не больше 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
  

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

Нужно реализовать класс 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
  

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

Реализуйте класс 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
  

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

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

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

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

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

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

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

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

• Пример 1

  Ввод

  {[()]}
  

  Вывод

  True
  

• Пример 2

  Ввод

  ()
  

  Вывод

  True
  

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

Астрологи объявили день очередей ограниченного размера. Тимофею нужно написать класс 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
  

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

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

• 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
  

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

У Тимофея было 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
  

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

У Тимофея было очень много стажёров, целых 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
  

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

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

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

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

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

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

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

• Пример 1

  Ввод

  3
  

  Вывод

  ((()))
  (()())
  (())()
  ()(())
  ()()()
  

• Пример 2

  Ввод

  2
  

  Вывод

  (())
  ()()
  

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

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

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
  

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

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

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

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

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

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

• Пример 1

  Ввод

  abc
  ahbgdcu
  

  Вывод

  True
  

• Пример 2

  Ввод

  abcp
  ahpc
  

  Вывод

  False
  

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

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

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

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

В первой строке записано 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
  

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

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

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

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

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

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

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

• Пример 1

  Ввод

  3 300
  999 999 999
  

  Вывод

  0
  

• Пример 2

  Ввод

  3 1000
  350 999 200
  

  Вывод

  2
  

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

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

Напомним, что из трёх отрезков с длинами 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
  

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

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

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

В первой строке задано количество предметов в гардеробе: 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
  

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

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

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

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

• Пример 1

  Ввод

  3
  15 56 2
  

  Вывод

  56215
  

• Пример 2

  Ввод

  3
  1 783 2
  

  Вывод

  78321
  

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

На 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
  

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

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

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

На каждой итерации проходим по массиву, поочередно сравнивая пары соседних элементов. Если элемент на позиции 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
  

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

Гоше дали задание написать красивую сортировку слиянием. Поэтому Гоше обязательно надо реализовать отдельно функцию 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].

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