Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

50096#50096

Требуется разделить заданный текст на английском языке на 3 группы слов по их первой букве так, чтобы количество слов в группах отличалось на минимальную величину. Группы могут формироваться только на основе алфавитного порядка латинских букв и задаются в виде диапазонов, например a-i, j-o, p-z.

Входные данные
В первой строке записано число N, не превышающее 10⁶ - количество строк в тексте. Далее записано N строк текста, в каждой из которых не более 1000 символов. Текст состоит из латинских букв разного регистра, пробелов и знаков препинания ".", ",", "!", "?", ":".
После каждого знака препинания обязательно ставится пробел либо строка заканчивается.
Переносы слов с одной строки на другую отсутствуют.

Выходные данные
Одно число - величина, на которую отличается количество слов в группе, где их больше всего, от количества слов в группе, где их меньше всего.

Примеры

№	Входные данные	Выходные данные	Примечание
1	3 Above all zoo the blue bird soars. Hippopotamus hopes high honey hotel?	2	Слова можно разбить на 3 группы: 1-я - 4 слова на буквы a и b; 2-я - 5 слов на букву h; 3-я - 3 слова на буквы s-z.
2	2 A a a a, o. O o o! A?	5	Слова можно разбить на 2 группы: 1-я - все слова на букву a; 2-я - все слова на букву o; 3-я - пустая.

Строки

✓ 9✗ 24900средняяВойти и решать

50095#50095

Для заданного в 10-й с/с дробного числа требуется определить разницу длин целой и дробной части этого числа в 5-й с/с при переводе с точностью до 8 разрядов.
Входные данные
положительное число в 10-й с/с, целая и дробная часть которого не превышают 8 разрядов каждая. Целая и дробная части разделяются точкой. Дробная часть может отсутствовать.
Выходные данные
неотрицательное целое число - разница между количеством разрядов целой и дробной части в пятеричной системе счисления.

Примеры

№	Входные данные	Выходные данные	Примечание
1	8.4	1	8.4₁₀=13.2₅, количество разрядов целой части на 1 больше, чем дробной
2	1.5	7	1.5₁₀=1.(2)₅=1.22222222₅, в 5-й с/с дробь не имеет конечного представления, поэтому ограничиваем длину 8 дробными разрядами

Вещественные числа Разные системы счисления

✓ 10✗ 511 000средняяВойти и решать

Устный счет#49860

Отвлечемся от задач про программистов и перенесемся в совершенно обыкновенные ясли, где мальчик Вова (3 годика) практикуется в устном счете, а если точнее — в вычислении арифметических выражений по модулю \(10^9 + 7\).

Совсем недавно Вова придумал длинное и очень красивое арифметическое выражение. Выражение состяло из \(n\) целых неотрицательных чисел, меньших \(10^9 + 7\), и знаков сложения и умножения между ними. Первым же делом он вычислил это выражение по модулю \(10^9 + 7\), после чего выписал само выражение и результат на лист бумаги. Все числа он выписал без ведущих нулей.

Пока шел тихий час, Вова спал, а хулиганы стерли несколько цифр в выражении и заменили их на другие. Менять знаки или результат вычисления выражения хулиганы не решились, даже для них это слишком низко. Когда Вова проснулся, он обнаружил рядом с его листочком ластик и карандаш. У Вовы есть принципы — если хулиганы изменили не более двух цифр, то он их простит, иначе они будут наказаны по всей строгости ясельных законов.

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

Формат входных данных
Единственная строка входного файла содержит выражение, которое обнаружил Вова у себя на листке. Выражение состоит из двух частей, разеделенных знаком ‘=’.

Первая часть содержит \(n\) целых неотрицательных чисел, разделенных знаками сложения (‘+’) и умножения (‘*’) (\(1 \le n \le 10^5\)). Вторая часть — целое неотрицательное число, означающее результат вычисления выражения.

Числа и все знаки разделяются одним пробелом. Гарантируется, что все числа строго меньше \(10^9 + 7\) и записаны без ведущих нулей.

Формат выходных данных
В случае, если данное выражение не может быть получено из верного равенства заменой не более двух цифр, выведите <<NO>>.

В противном случае в первой строке выведите <<YES>>. На следующей строке выведите целое число \(k \leq 2\) — количество чисел, которые были изменены.

В следующих \(k\) строках выведите по два числа — позицию измененнного числа в выражении (от \(1\) до \(n\)) и его исходное значение.

Суммарно должно быть изменено не более двух цифр. В процессе замены в числах не должны появиться ведущие нули и числа должны остаться меньше \(10^9 + 7\). Если существует несколько вариантов ответа, выведите любой из них.

Вывод формулы реализация

✓ 0✗ 3—Войти и решать

Перекладывание ответственности#49858

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

Всего в команде разработчиков \(n\) человек. Также есть \(n\) задач, которые необходимо подготовить. Подготовка \(i\)-й задачи требует подготовки ровно \(c_i\) ее элементов, и разработка каждого элемента \(i\)-й задачи имеет сложность \(w_i\).

Было решено, что каждый разработчик будет отвечать за столько же элементов, за сколько он бы отвечал, если бы разрабатывал целиком соответствующую задачу. Иными словами, \(i\)-му разработчику будет назначено ровно \(c_i\) элементов из различных задач. Распределение элементов по разработчикам происходит следующим образом:

Сначала первому разработчику выдается \(c_1\) элементов, затем второму — \(c_2\), и так далее. Переход к \((i+1)\)-му разработчику происходит в тот момент, когда \(i\)-му назначается ровно \(c_i\) элементов.
Элементы, за которые будет отвечать каждый разработчик, выбираются по одному из всех еще не до конца распределенных задач по очереди. Сначала будет выбран один этап из первой задачи, затем — из второй, из третьей, и так далее по кругу. Если в какой-то задаче не осталось нераспределенных этапов, она пропускается.
Элементы, назначаемые очередному разработчику, выбираются начиная с той задачи, на которой остановился предыдущий разработчик. То есть, если последний элемент, назначенный предыдущему разработчику, был из \(x\)-й задачи, то первый элемент, назначенный следующему, будет из задачи \((x+1) \bmod n\) (если в ней еще остались нераспределенные элементы).

Иными словами, поддерживается набор еще не до конца распределенных задач и указатель \(x\) на <<текущую>> задачу. Когда надо выдать текущему разработчику очередной элемент, ему выдается один элемент из задачи \(x\), после чего \(x\) сдвигается по кругу вперед на следующую задачу.

Жюри считает, что такой способ позволяет более честно распределить сложность подготовки олимпиады. Определите суммарную сложность разработки элементов, доставшихся каждому из \(n\) разработчиков.

Формат входных данных
В первой строке дано целое число \(n\) — количество разработчиков (\(1 \le n \le 500\,000\)).

В \(i\)-й из следующих \(n\) строк через пробел даны два целых числа \(c_i\) и \(w_i\) — количество элементов в \(i\)-й задаче и сложность их разработки (\(1 \le c_i, w_i \le 10^9\)).

Формат выходных данных
В единственной строке выведите через пробел \(n\) чисел, \(i\)-е из которых равно суммарной сложности разработки элементов, доставшихся \(i\)-му разработчику.

Замечание
Иллюстрацию к третьему примеру можно видеть ниже. Слева показаны элементы, из которых состоят задачи, справа — элементы, назначенные каждому разработчику.

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

Задача на реализацию Задачи на моделирование

✓ 1✗ 1—Войти и решать

Биржа - 2#49776

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

Торги проходят в течении \(n\) дней, всего на рынке представлены акции \(m\) компаний, цены акций компании фиксированы в течении одного дня. Сделки бывают двух типов:

Купить \(x\) акций компании \(comp\)
Продать все акции компании \(comp\)

За каждую сделку надо заплатить 1% комиссии. Например, если купить 10 акций по 300 рублей, то суммарно заплатить придется 3030 рублей. Если же продавать 10 акций стоимостью 300 рублей каждая, то за них можно получить 2970 рублей.

Прибылью с продажи будем считать разность полученных при продаже денег и суммарно потраченных денег при покупках. Например, если 10 акций были куплены по 300 рублей, а затем еще 5 акций были куплены по 400 рублей, то в случае продажи по стоимости 500 прибыль составит: \(15 \cdot 500 \cdot 0.99 - (10 \cdot 300 \cdot 1.01 + 5 \cdot 400 \cdot 1.01) = 7425 - (3030 + 2020) = 2375\) рублей. При этом, акции могут быть проданы в убыток (за меньшую стоимость, чем были куплены), тогда прибыль с продажи будем считать отрицательной.

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

Вам даны \(k\) событий покупки/продажи. Необходимо найти минимальную суммарную прибыль среди всех моментов времени.

Входные данные
В первой строке входных данных содержится одно целое число \(t\) — число тестовых наборов (\(1 \le t \le 30\)).

Затем следуют \(t\) тестовых наборов. Каждый тестовый набор описывается следующим образом:

В первой строке тестового набора содержатся три целых числа \(n\), \(m\) и \(k\) — число дней, в которые проходят торги, число компаний на рынке и число событий, соответственно (\(1 \le n, m \le 100\), \(1 \le k \le 1000\)).

В следующих \(m\) строках записаны названия компаний и \(n\) чисел — стоимости акций компании в рублях в каждый из дней торгов. Названия компаний состоят из не более чем \(10\) строчных букв латинского алфавита и попарно различны. Стоимости акций — целые числа в диапазоне от \(1\) до \(10^5\) включительно.

В следующих \(k\) строках заданы события покупки/продажи в хронологическом порядке. Событие покупки задается в формате <день> buy <число акций> <название компании>, а событие продажи задается в формате <день> sell <название компании>. При этом <день> — целое число от \(1\) до \(n\), а <число акций> — целое число от \(1\) до \(1000\). Гарантируется, что все события следуют в порядке неубывания дней и корректны, а именно нет продаж некупленных акций и покупок акций, которых нет на рынке.

Выходные данные
Для каждого тестового набора выведите в отдельной строке минимальную прибыль среди всех моментов времени, с относительной или абсолютной погрешностью не более \(10^{-4}\).

Примечание

В первом тестовом наборе изначально до продаж суммарная прибыль равна \(0\), после первой продаже суммарная прибыль становится \(2375\) (случай разобран в примере).

Во втором тестовом наборе промежуточные прибыли равны \(0\), \(-11.11\) (акция продана дороже, но комиссия больше разницы) и \(1948.89\).

В третьем тестовом наборе промежуточные прибыли равны \(0\) и \(-2080\).

В четвертом тестовом наборе промежуточные прибыли равны \(0\) и \(979.9\), деньги потраченные на непроданные акции не учитываются.

Задача на реализацию Задачи на моделирование

✓ 1✗ 1—Войти и решать

Биржа#49775

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

Купить \(x\) акций компании \(comp\)
Продать все акции компании \(comp\)

Вам даны \(k\) событий покупки/продажи. Необходимо найти максимальную суммарную прибыль среди всех моментов времени.

Затем следуют \(t\) тестовых наборов. Каждый тестовый набор описывается следующим образом:

Выходные данные
Для каждого тестового набора выведите в отдельной строке максимальную прибыль среди всех моментов времени, с относительной или абсолютной погрешностью не более \(10^{-4}\).

Примечание

В третьем тестовом наборе промежуточные прибыли равны \(0\) и \(-2080\).

Задача на реализацию Задачи на моделирование

✓ 2✗ 2900средняяВойти и решать

Трансформация массива - 2#49774

Вам дано \(t\) пар массивов \(a_i\) и \(b_i\) равной длины.

За одну операцию модификации можно:

Поменять местами любые два элемента массива \(a_i\), но каждый элемент массива может участвовать не более чем в одном обмене.
Прибавить к любому элементу массива \(a_i\) единицу. Данную операцию можно применять неограниченное число раз к любому элементу массива.

Для каждой пары массивов найдите минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или определите, что это невозможно.

Входные данные
В первой строке дано число \(t\) — число пар массивов (\(1 \le t \le 40\)).

В следующих \(3t\) строках содержатся описания пар массивов. Каждая пара описывается тремя строками.

В первой из них дано число \(n_i\) — количество элементов в каждом массиве \(i\)-й пары(\(1 \le n_i \le 10\)). Во второй строке заданы \(n_i\) чисел \(a_{i,j}\) — элементы массива \(a_i\) (\(1 \le a_{i,j} \le 1000\)). В третьей строке заданы \(n_i\) чисел \(b_{i,j}\) — элементы массива \(b_i\) (\(1 \le b_{i,j} \le 1000\)).

Гарантируется, что сумма \(n_i\) по всем тестовым наборам не превосходит \(150\).

Выходные данные
Для каждого пары массивов выведите одно число — минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или \(-1\), если для данной пары это невозможно.

Жадный алгоритм Задача на реализацию

✓ 1✗ 5—Войти и решать

Сортировка строк#49712

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

Входные данные

В первой строке записаны через пробел размеры матрицы: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами. В последней строке вводится номер столбца K .

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	4 5 21 22 23 24 25 26 12 18 29 33 11 37 31 14 39 16 17 18 5 20 1	26 12 18 29 33 21 22 23 24 25 16 17 18 5 20 11 37 31 14 39

Алгоритмы сортировки Двумерные массивы

✓ 49✗ 53700средняяВойти и решать

Контрольное значение кратное 14#49439

Профессор Селезнев передает Алисе зашифрованную информацию, которая представляет собой последовательность целых чисел. Все числа данной последовательности не превышают 1000. Чтобы понять, что данные переданы правильно, Алисе необходимо определить контрольное значение, которое равно наибольшему произведению каких-либо двух переданных элементов последовательности и при этом данное произведение должно делится на 14.
Помогите Алисе определить контрольное значение.

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

Формат выходных данных
Выведите одно число - контрольное значение.

Линейные алгоритмы

✓ 9✗ 63700средняяВойти и решать

Магический квадрат подрядка N#49391

Магическим квадратом порядка N называется квадратная матрица размера NхN, составленная из чисел 1, 2, ..., N²так, называется квадратная матрица размера NхN, такая что суммы по каждому столбцу, каждой строке и каждой из двух больших диагоналей равны между собой. Напишите программу, которая проверяет, является ли заданная квадратная матрица магическим квадратом.

Формат входных данных
В первой строке вводится размер матрицы N (0 < N <= 100). В следующих N строках вводятся строки матрицы, по N значений в каждой, разделённые пробелами.

Формат выходных данных
Программа должна вывести слово 'YES', если матрица является магическим квадратом, и слово 'NO', если не является.

Двумерные массивы

✓ 1✗ 411 200средняяВойти и решать

Подпоследовательность с особыми числами - 1#49320

На вход программе подается последовательность чисел и значение K. Особыми называются простые числа, перед которыми стоит знак «минус».
Рассмотрим все непрерывные подпоследовательности исходной последовательности, в которых количество особых чисел кратно K. Найдите максимальную сумму одной из таких подпоследовательностей.

Формат входных данных
В первой строке количество чисел N (100 ≤ N ≤ 5000000) и значение K. Каждая из следующих N строк содержит одно целое число, не превышающее по модулю 1000000. Гарантируется, что сумма любой подпоследовательности не превышает 10⁹.

Формат выходных данных
Выведите одно число – максимальную сумму такой последовательности.

ЕГЭ - вычислительные задачи

✓ 3✗ 401 100средняяВойти и решать

Обработка пар чисел - 1#49317

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

Формат входных данных
В первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.

Формат выходных данных
Выведите значение найденной максимальной суммы. Если такой суммы нет, то выведите -1.

Жадный алгоритм Линейные алгоритмы Остатки

✓ 10✗ 63900средняяВойти и решать

Угадай число#49316

Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

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

Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделенных пробелами. После каждой строки с вопросом идет ответ Августа: YES или NO.

Наконец, последняя строка входных данных содержит одно слово HELP.

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

Вы должны вывести (через пробел, в порядке возрастания) все числа, которые мог задумать Август.

Множества

✓ 50✗ 203900средняяВойти и решать

Облако хештегов#49295

Вася ведёт публичную страницу организации “Мышь и клавиатура”, где постоянно публикует различные новости из мира спортивного программирования. Для удобства поиска по новостям Вася прикрепляет к каждой из них список хештегов. В данной задаче хештегом называется строка, состоящая из маленьких букв английского алфавита и ровно одного символа ‘#’, расположенного в начале строки. Длиной хештега будем называть количество символов в нём, без учёта символа ‘#’.

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

Поскольку вам не хочется менять порядок хештегов в уже написанной новости, вы решили удалить у некоторых хештегов некоторый суффикс (какое-то количество последних символов), при этом можно даже удалить весь текст хештега, оставив только символ ‘#’, но сам символ ‘#’ удалять нельзя. Из всех возможных вариантов такого удаления вы хотите выбрать тот, в котором суммарно будет удалено минимальное количество символов. Если и таких вариантов несколько, то разрешается использовать любой из них.

Формат входных данных
В первой строке находится одно число \(n\) (\(1 \leq n \leq 500\,000\)) — количество хештегов в новости.

Каждая из следующих \(n\) строк содержит ровно один хештег положительной длины.

Обозначим через \(L\) суммарную длину всех хештегов. Гарантируется, \(L\) не превосходит \(500\,000\).

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

Замечание

Слово \(a_1, a_2, \ldots, a_m\) длины \(m\) лексикографически меньше слова \(b_1, b_2, \ldots, b_k\) длины \(k\), если выполняется одно из двух:

либо в первой позиции \(i\), такой что \(a_i \neq b_i\), символ \(a_i\) идёт раньше по алфавиту, чем символ \(b_i\), то есть в первой различающейся позиции символ слова \(a\) меньше символа слова \(b\);
либо (если такой позиции нет) \(m < k\), то есть второе слово начинается с первого, но при этом не совпадает с ним.

Про последовательность слов говорят, что они идут в лексикографическом порядке, если каждое слово в нём (кроме последнего) лексикографически не превосходит следующее за ним.

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

Слово, состоящее только из символа ‘#’, лексикографически меньше любого другого хештега. Поэтому в третьем примере мы не можем оставить два первых слова и сократить два вторых.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 35 тестах будут доступны во время соревнования. Результаты работы на остальных 15 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n, L \leq 15\), наберут не менее \(20\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 1\,000\), наберут не менее \(50\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 100\,000\), наберут не менее \(70\) баллов.

Задачи на моделирование Строки

✓ 2✗ 4—Войти и решать

Игра в напёрстки#49293

В свободное время Бомбослав любит наблюдать из окна как ребята во дворе играют “на интерес” в известную игру в напёрстки. Для игры требуется два человека, ведущий и игрок. Ведущий берёт три одинаковых непрозрачных напёрстка и прячет под один из них шарик. Затем он несколько раз меняет некоторые пары напёрстков местами, после чего игрок должен угадать, под каким напёрстком сейчас находится шарик.

Бомбослав заметил, что ребята во дворе не очень изобретательны в своих действиях, и всегда меняют местами левый напёрсток со средним на нечётных действиях (то есть на первом, третьем, пятом и так далее) и средний с правым на чётных действиях (то есть на втором, четвёртом и так далее).

Пронумеруем напёрстки от \(0\) до \(2\) слева направо. То есть левый напёрстком имеет номер \(0\), средний номер \(1\), а правый номер \(2\). Бомбослав не успел увидеть начало игры, но посчитал, что ведущий совершил \(n\) действий и в итоге шарик оказался под напёрстком \(x\). Под каким напёрстком находился шарик в самом начале?

Формат входных данных
В первой строке входных данных записано одно цело число \(n\) (\(1 \leq n \leq 2 \cdot 10^9\)) — количество действий, совершённых ведущим.

Во второй строке записано одно целое число \(x\) (\(0 \leq x \leq 2\)) — номер напёрстка, под которым оказался шарик через \(n\) действий.

Формат выходных данных
Выведите одно целое число от \(0\) до \(2\), означающее номер напёрстка, под которым находился шарик в самом начале.

Замечание

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

Первым действием ведущий поменял местами левый и средний напёрстки. В результате шарик оказался под левым напёрстком.
Вторым действием ведущий поменял местами средний и правый напёрстки. Шарик остался под левым напёрстком.
Третьим действием ведущий снова поменял местами левый и средний напёрстки. В результате шарик снова оказался посередине.
Последним четвёртым действием ведущий опять поменял местами средний и правый напёрстки и шарик оказался под правым напёрстком.

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, верно работающие при \(n \leq 100\,000\) будут набирать не менее 50 баллов.

Вывод формулы

✓ 3✗ 11—Войти и решать

Подсчет прибыли#49190

Финансовый аналитик компании "Хлебосушки" анализирует прибыль компании на протяжении N месяцев. Аналитику поставили задачу найти интервал длиной не менее K месяцев с максимальной прибылью. Месяцы имеют сквозную нумерацию, начиная с 1 (с месяца открытия компании).
Вы - ведущий программист компании. Вам дали задачу написать программу, которая бы находила максимальную прибыль в непрерывном интервале длиной не менее K месяцев.

Формат входных данных
Первая строка содержит натуральное число N (1 < N ≤ 1 000 000) – количество месяцев существования компании и натуральное число K (1 < K < N) – минимально допустимый интервал. В каждой из следующих N строк находится одно целое число profit_i, не превышающее по модулю 10 000 000: прибыль компании за i^й месяц.

Формат выходных данных
Выведите одно число - максимальную прибыль в интервале длиной не менее K месяцев. Гарантируется, что ответ к задаче не превышает 10⁹.

ЕГЭ - вычислительные задачи Префиксные суммы(минимумы, ...)

✓ 14✗ 63800средняяВойти и решать

Тестирование мессенджера - 2#49030

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

генерируется случайный сценарий взаимодействия пользователей с приложением;
в приложении симулируется выполнение этого сценария;
проверяется корректность итогового состояния приложения.

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

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

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

Формат входных данных
В первой строке ввода дано единственное целое число \(T\) — количество сценариев, которое вам необходимо обработать (\(1 \le T \le 100\)).

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

События первого набора задаются в формате <<REG \(\mathtt{id}_i\) BY \(\mathtt{handle}_i\) AT \(t_i\)>>.
События второго набора задаются в формате <<CHANGE \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.
События третьего набора задаются в формате <<SEND FROM \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

Гарантируется, что в каждом наборе входных данных все \(t_i\) различны. Гарантируется, что успешно зарегистрированный пользователь не предпринимает попытки зарегистрироваться еще раз.

Формат выходных данных
Для каждого сценария выведите требуемую статистику для каждого пользователя.

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> RECEIVED <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> FROM <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество полученных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, от которого он получил больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, полученных от пользователя \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, отправивших ему максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не получал сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

Задача на реализацию Сортировка событий Хеш

✓ 1✗ 2—Войти и решать

Система контроля версий#49012

IT-компания <<VK>> имеет огромную инфраструктуру проектов, и чтобы разработчики могли гармонично работать вместе и структурировать вносимые в код изменения, им необходима система контроля версий (VCS).

Полноценные системы контроля версий устроены достаточно сложно, и некоторые компании даже разрабатывают свои собственные VCS, заточенные под конкретные нужды или особенности рабочего процесса. Разумеется, разработчики из <<VK>> могут справиться с задачей реализовать свою VCS, но сегодня эта задача предлагается вам.

Ваша примитивная система контроля версий должна иметь вид ацикличного ориентированного графа изменений состояния проекта.

<<Исток>> графа — стартовая вершина, соответствующая изначальному состоянию проекта. Это единственная вершина, в которую не входят ребра.
Каждая вершина, кроме корня, соответствует определенному коммиту. Коммит — блок из одного или более изменений.
Версия проекта, задаваемая вершиной — набор всех изменений на путях между стартовой вершиной и данной.
Есть несколько выделенных веток, каждая имеет уникальное имя и задается указателем на определенную вершину графа. С веткой ассоциируется версия проекта, соответствующая вершине, на которую она указывает.
Из всех веток выделяется текущая ветка — версия проекта, с которой сейчас работает пользователь. Вершину, на которую указывает текущая ветка, будем обозначать как HEAD.

Пример графа можно видеть ниже. Рядом с каждым коммитом указаны соответствующие ему изменения. Вершина номер \(8\) соответствует команде merge между ветками <<main>> и <<new_config>> (описание команд см. ниже). Набор команд, позволяющий получить приведенную структуру графа версий, приведен в первом тесте. Пошаговые иллюстрации изменения графа версий можно видеть в прикрепленном к условию архиве.

Изначально граф состоит из единственной вершины с номером \(1\), на которую указывает текущая ветка <<main>>. Требуется поддерживать следующие команды:

<<add <файл> <хеш изменений>>> — запомнить изменения, внесенные в данный файл. Хеш однозначно описывает набор изменений в файле. Иными словами, хеши двух независимых изменений совпадают тогда и только тогда, когда состояния файла до и после изменения одинаковы.

Иными словами, если в пустой файл добавляется строчка <<print(something)>>, и в непустой файл добавляется та же строчка, хеши этих двух изменений будут различными.
<<commit>> — подвесить к HEAD новую вершину, состоящую из всех изменений (add), сделанных с момента предыдущего успешного коммита. Новой вершине присваивается первый неиспользованный натуральный номер, после чего HEAD перемещается на нее.

Операция возможна только тогда, когда множество сделанных изменений непустое. В противном случае требуется выдать ошибку <<ERROR: no changes>>, при этом новая вершина не создается.
<<reset <номер>>> — переместить HEAD на вершину с данным номером.

Гарантируется, что вершина с данным номером существует. Если присутствуют несохраненные (commit) изменения (add), операция отклоняется с ошибкой <<ERROR: uncommitted changes>>.
<<checkout <имя ветки>>> — поменять текущую ветку на ветку с указанным именем (и, соответственно, переместить HEAD на версию, соответствующую выбранной ветке). Если ветки с таким именем не существует, создать новую ветку с таким именем, которая будет указывать на HEAD, после чего сделать ее текущей.

Если присутствуют несохраненные изменения, операция отклоняется с ошибкой <<ERROR: uncommitted changes>>, аналолгично операции reset.
<<merge <имя ветки>>> — объединить изменения в текущей ветке и в ветке с указанным именем. При этом создается новая вершина, которая подвешивается к HEAD и к вершине, соответствующей второй ветке. HEAD при этом перемещается на новую вершину, а указатель второй ветки не двигается. Гарантируется, что имя второй ветки не совпадает с текущей.

Если есть незакоммиченные изменения, операция отклоняется с ошибкой <<ERROR: uncommitted changes>>.

Если несохраненных изменений нет, проверяется отсутствие конфликтов при объединении. Конфликтом считается ситуация, когда в состояниях проекта, соответствующим данным веткам, с одним и тем же файлом сделаны различные изменения. Иными словами, если обозначить множество изменений определенного файла в текущей ветке как \(D_1\), а во второй — как \(D_2\), то конфликт возникает, когда оба множества \(D_1 \setminus D_2\) и \(D_2 \setminus D_1\) непустые. В таком случае операция отклоняется с ошибкой <<ERROR: conflicts detected>>.

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

Если какое-то изменение содержится в версиях разное ненулевое количество раз (например, изменение может присутствовать дважды после merge двух веток, в которые оно входило), конфликт не возникает. Конфликт возникает только если в каждой версии есть измененение одного и того же файла, которого нет в другой версии.

Ниже можно найти иллюстрации к успешным и конфликтным вызовам операции merge.

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово <<OK>> и номер вершины, на которую указывает HEAD, если команда выполнена успешно, или же соответствующую ошибку, если команда отклонена.

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных, которые вам предстоит обработать (\(1 \le T \le 20\)). Далее следуют описания наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное целое число \(n\) — количество команд в наборе (\(0 \le n \le 400\)). В \(i\)-й из следующих \(n\) строк задается \(i\)-я команда.

Гарантируется, что имена веток состоят только из маленьких латинских букв (‘a’ – ‘z’) и нижних подчеркиваний (‘_’), а хеши изменений — уникальные шестнадцатеричные строки длины ровно \(6\) (состоят из цифр и маленьких латинских букв от ‘a’ до ‘f’). Имена файлов в команде add состоят из маленьких латинских букв, точек и слешей (‘/’).

Также гарантируется, что команде reset всегда передается существующая вершина, а команде merge — существующая ветка, не совпадающая с текущей.

Формат выходных данных
Для каждого набора входных данных в порядке их следования во вводе сначала выведите строку <<Test case <номер>>> (наборы нумеруются от \(1\) до \(T\)), а затем \(n\) результатов выполнения команд, каждый в своей строке.

Результат выполнения каждой команды должен соответствовать либо формату <<OK <HEAD>>>, либо формату <<ERROR: <сообщение об ошибке>>>.

графы Задача на реализацию

✓ 1✗ 01 100средняяВойти и решать

Игра с таблицей#48967

Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);
выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу \(s\), и если да, то какие операции и в каком порядке необходимо применить.

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

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

В первой строке выведите строку <<YES>>.
Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).
В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array}\)

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array}\)

Во втором примере можно показать, что разрешенными операциями невозможно получить таблицу с суммой чисел \(5\) из исходной.

В третьем примере изначально дана таблица:

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array}\)

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array}\)

meet in the middle Битовые операции

✓ 3✗ 391 000средняяВойти и решать

Посадка в самолет#48965

В самолетах авиакомпании Битавиа кресла расположены в \(n\) рядов, при этом в каждом ряду по шесть мест, между третьим и четвертым местом находится проход. Некоторые пассажиры регистрируются заранее онлайн, другие пассажиры регистрируются на стойке регистрации в аэропорту.

При онлайн-регистрации пассажир может выбрать любое место и не может его затем менять. Например, при \(n = 6\) рассадка в самолете после онлайн-регистрации может выглядеть так (крестиками отмечены занятые места):

На стойку регистрации придут \(m\) пассажиров. По правилам Битавиа нужно рассадить их в самолете таким образом, чтобы итоговая рассадка в самолете была симметрична относительно прохода. То есть, если в некотором ряду на первом кресле сидит пассажир, то в том же ряду на шестом кресле тоже должен сидеть пассажир. То же самое справедливо для второго и пятого, третьего и четвертого кресел, соответственно. При этом пересаживать пассажиров, прошедших онлайн-регистрацию нельзя. В исходную рассадку, показанную на рисунке выше, можно добавить семь пассажиров, удовлетворив условие симметрии, например, следующим образом:

Вам дана рассадка пассажиров после онлайн-регистрации. Требуется рассадить \(m\) пассажиров так, чтобы итоговая рассадка в самолете была симметрична относительно прохода, или определить, что это невозможно.

Формат входных данных
В первой строке содержатся два целых числа \(n\) и \(m\) — количество рядов в самолете и количество пассажиров, которые придут на стойку регистрации (\(1 \le n \le 1000\), \(0 \le m \le 6000\)).

В следующих \(n\) строках задана изначальная рассадка в самолете после онлайн-регистрации. В каждой строке содержится по шесть символов, при этом \(i\)-й символ \(j\)-й строки равен <<X>> (заглавная английская X), если \(i\)-е место в \(j\)-м ряду уже занято и <<.>> (точка) иначе.

Формат выходных данных
Если искомой рассадки не существует, выведите <<Impossible>>.

Иначе выведите \(n\) строк по шесть символов — итоговую рассадку в самолете. При этом \(i\)-й символ \(j\)-й строки должен быть равен <<X>>, если место занято, и <<.>>, если свободно. Если существует несколько решений, разрешается вывести любое.

Ниже приведены пять примеров входных данных.

В первом примере \(m = 0\), а рассадка в самолете симметрична, поэтому итоговая рассадка совпадает с исходной.
Во втором примере есть только один способ рассадить пассажиров симметрично.
В третьем примере существовало бы решение, при \(m = 1\), но при \(m = 2\) не существует способа рассадить всех пассажиров симметрично.
В четвертом примере требуется рассадить больше пассажиров чем свободных мест в самолете.
Пятый примере соответствует ситуации, рассмотренной на рисунках в тексте условия. В этом примере существует несколько решений, приведено одно из них.

Задача на реализацию

✓ 16✗ 70900средняяВойти и решать