В заданиях этого листка часть заданий нужно выполнять на языке C++, часть заданий — на языке Python.
Во всех задачах предполагается решение сложности O(размер входных данных), либо сортировка входных данных и последующая обработка за O(размер входных данных).
Для сортировки массива чисел в языке C++ можно использовать следующую конструкцию:
#include<algorithm> ... int a[n]; // или int * a = new int[n]; sort(a, a + n);то есть функция
sort получает два указателя: на начало массива и на элемент, следующий
за последним элементом массива.
На бал пришли \(n\) мальчиков и \(m\) девочек. Пара из мальчика и девочки будет красиво смотреться, если величины их ростов отличаются не более чем на 1. Определите, какое максимальное число красивых пар можно составить.
Программа получает на вход число \(n\), \(1\le n \le 10^5\). В следующей строке записаны через пробел \(n\) положительных чисел \(a_i\), не превосходящих \(10^9\), — значения роста мальчиков. Затем дано число \(m\), \(1\le m \le 10^5\). В следующей строке записаны через пробел \(m\) положительных чисел \(b_i\), не превосходящих \(10^9\), — значения роста девочек.
Программа должна вывести одно целое число — максимальное число красивых пар.
| Ввод | Вывод |
|---|---|
3 |
2 |
В танце сиртаки участники становятся в круг и кладут руки на плечи соседей. Поэтому танцевать сиртаки неудобно, если рост участников сильно различается. Будем считать группу танцоров подходящей для сиртаки, если рост любых двух танцоров в группе отличается не более, чем на 15%, то есть \(h_i\le 1.15 h_j\).
Программа получает на вход число \(n\), \(1\le n \le 10^5\). В следующей строке записаны через пробел \(n\) положительных чисел \(h_i\), не превосходящих \(10^9\) — значения роста танцоров.
Программа должна вывести единственное число — максимальное количество танцоров, которых можно выбрать для cиртаки.
| Ввод | Вывод |
|---|---|
7 |
4 |
У вас есть полоска клетчатой бумаги длиной \(n\) клеток и шириной в 1 клетку. Каждая клетка покрашена либо в чёрный, либо в белый цвет. Вы можете покрасить любую белую клетку в чёрный цвет, после чего вам нужно вырезать кусок из \(k\) подряд идущих чёрных клеток. Определите, какое наименьшее число клеток вам нужно перекрасить.
Программа получает на вход строку из букв «B» и «W», означающих чёрную и белую клетки. Длина строки не превосходит \(10^6\). В следующей строке записано одно положительное число \(k\), не превосходящее длины данной строки.
Программа должна вывести одно число — минимальное количество клеток, которые нужно перекрасить.
| Ввод | Вывод |
|---|---|
BWBWBBWBW |
1 |
У вас есть полоска клетчатой бумаги длиной \(n\) клеток и шириной в 1 клетку. Каждая клетка покрашена либо в чёрный, либо в белый цвет. Вы можете не более \(k\) клеток покрасить в чёрный цвет, после чего вам необходимо вырезать непрерывный кусок максимального размера, содержащий только чёрные клетки. Определите длину этого куска.
Программа получает на вход строку из букв «B» и «W», означающих чёрную и белую клетки. Длина строки не превосходит \(10^6\). В следующей строке записано одно целое неотрицательное число \(k\).
Программа должна вывести одно число — максимальную длину чёрной полоски, которую можно получить перекрашиванием не более \(k\) клеток.
| Ввод | Вывод |
|---|---|
BWBWBBWBW |
4 |
В одной байдарке может плыть один или два человека, если их масса не превосходит значения \(W\). \(N\) человек собирается в поход, какое минимальное число байдарок им необходимо для этого?
Первая строка входных данных содержит два числа \(N\) (\(1\le N\le 10^{5}\)) и \(W\) (\(1\le W\le 10^9\)). Во второй строке записаны \(N\) положительных чисел, не превосходящих \(W\), — веса людей.
Программа должна вывести одно число — минимальное количество необходимых байдарок.
| Ввод | Вывод |
|---|---|
6 135 |
4 |
На столе лежат \(n\) конфет в ряд, масса \(i\)-й конфеты равна \(w_i\). Аня может съесть любое (в том числе ноль) конфет слева, то есть съесть целиком некоторый префикс последовательности. Боря может съесть любое (в том числе ноль) конфет справа, то есть съесть целиком некоторый суффикс последовательности.
Они хотят съесть конфеты честно, то есть суммарные массы съеденных ими конфет должны быть равны. При этом они хотят съесть как можно больше конфет. Определите, сколько конфет они съедят.
Первая строка входных данных содержит положительное число \(n\le10^5\) — количество конфет. В следующей строке записаны \(n\) целых положительных чисел, не превосходящих \(10^9\) — веса конфет.
Программа должна вывести два числа: количество конфет, которые съест Аня, и количество конфет, которые съест Боря.
| Ввод | Вывод |
|---|---|
9 |
3 4 |
Дана последовательность ненулевых целых чисел \(a_1\), \(a_2\), ..., \(a_n\). Подпоследовательностью называется последовательность, которая получается вычеркиванием из данной последовательности некоторого количества элементов.
Вам нужно получить из данной последовательности знакочередующуюся последовательность максимальной длины, а из всех таких подпоследовательностей выберите подпоследовательность с наибольшей суммой.
Программа получает на вход число \(n\le 10^5\). В следующей строке даны \(n\) целых ненулевых чисел, не превосходящих по модулю \(10^6\) — элементы последовательности.
Программа должна вывести элементы искомой подпоследовательности.
Указание. Если вы получаете TL и не используете массив, попробуйте считать все данные в массив, а затем уже обрабатывать массив.
| Ввод | Вывод |
|---|---|
5 |
3 -1 |
Дана строка состоящая только из символов «a», «b», «c». Найдите в ней минимальную по длине непрерывную подстроку, содержащую каждый из этих символов хотя бы по одному разу.
Программа получает на вход строку из символов «a», «b», «c», длина которой не превосходит \(10^5\).
Программа должна вывести два числа: длину наименьшей подходящей подстроки и номер её первого символа (в нумерации с единицы). Если ответов несколько — выведите тот, у которого меньше номер начального символа. Если ответа нет, выведите одно число 0.
| Ввод | Вывод |
|---|---|
aababaacca |
4 5 |
Строка состоит из произвольных строчных английских букв. Вам нужно найти максимальную по длине подстроку, в которой каждая буква встречается не более \(k\) раз.
Программа получает на вход положительное число \(k\), в следующей строке дана строка из строчных английский букв, длина строки не превосходит \(3\times 10^6\).
Программа должна вывести два числа: длину наибольшей подходящей подстроки и номер её первого символа (в нумерации с единицы). Если ответов несколько — выведите тот, у которого меньше номер начального символа.
| Ввод | Вывод |
|---|---|
2 |
5 2 |