Алгоритмы

Дан массив \([a_1, a_2, \ldots, a_n]\), состоящий из неотрицательных целых чисел.

Рассмотрим разбиение массива на \(k\) непустых отрезков подряд идущих элементов. Назовем перекосом разбиения разность между максимальной и минимальной суммой чисел в отрезках разбиения. Требуется найти максимальный перекос разбиения данного массива на \(k\) подотрезков.

Например, если массив равен \([2, 1, 3, 4]\), то у разбиения \([2, 1, 3][4]\) перекос равен \(6-4=2\), у разбиения \([2, 1] [3, 4]\) перекос равен \(7-3=4\), а у разбиения \([2] [1, 3, 4]\) перекос равен \(8-2=6\). Последний вариант является оптимальным среди всех разбиений массива на два непустых отрезка.

Формат входных данных
Первая строка содержит два целых числа \(n\) и \(k\) (\(2 \le k \le n \le 300\,000\)) — длину массива и количество подотрезков, соответственно.

Вторая строка содержит \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 10^9\)) — элементы массива.

Формат выходных данных
Выведите одно число — максимальный перекос разбиения данного массива на \(k\) отрезков.

Примечание
Первый пример разобран в условии задачи.

Во втором примере оптимальным разбиением является \([2][1][3, 4][1]\). Максимальная сумма на подотрезках в данном разбиении равна \(3 + 4 = 7\), минимальная сумма равна \(1\), таким образом, перекос равен \(6\).

На доске были выписаны два квадрата натуральных чисел: \(x^2\) и \(y^2\), где \(l \le y^2 < x^2 \le r\). Числа \(x^2\) и \(y^2\) стерли и выписали на доске их разность \(d\).

По заданным \(l\), \(r\) и \(d\) выясните, сколько различных пар натуральных чисел \(x^2, y^2\) могло быть выписано на доске.

Формат выходных данных
В первой строке даны три числа \(d\), \(l\) и \(r\) (\(1 \le d \le 10^9, 1 \le l \le r \le 10^{18}\)).

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

Примечание
В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 256 и 196.

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

Представим область для поисков как таблицу из \(k\) строк и \(n\) столбцов. Нумерация строк идет от \(1\) до \(k\) сверху вниз, нумерация столбцов от \(1\) до \(n\) слева направо. В каждой клетке таблицы могут находиться полезные ископаемые.

Сканер работает следующим образом: он может быть запущен в столбце \(p\) и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца \(p\), верхние \(k-1\) клетку столбца \(p-1\), верхние \(k-2\) клетки столбца \(p-2\), и так далее. На рисунке показана зона сканирования для поля с \(k = 3\), \(n=5\) и всех значений \(p\).

Вам даны значения, которые вернул сканер для всех \(p\), обозначим за \(b_p\) значение в столбце \(p\). Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения \([2, 1, 2, 3, 2]\), то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником):

По заданным значениям, которые вернул сканер, определите количество корректных таблиц и выведите остаток от деления этого количества на число \(10^9+7\). Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести \(0\).

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

Во второй строке даны \(n\) чисел \(b_1, b_2, \ldots, b_n\) — значения, которые вернул сканер (\(0 \le b_i \le k^2\)).

Формат выходных данных
Выведите единственное число — остаток от деления количества различных корректных таблиц на \(10^9 + 7\).

Назовём число простоватым, если произведение цифр этого числа в десятичной системе счисления является простым числом. Например, простоватым является число 12, а число 29 не является.

Требуется посчитать количество простоватых чисел от \(l\) до \(r\).

Напомним, что целое число \(p > 1\) называется простым, если оно имеет ровно два делителя: \(1\) и \(p\).

Формат входных данных
Первая строка содержит одно целое число \(l\) (\(1 \le l \le 10^{100\,000}\)).

Вторая строка содержит одно целое число \(r\) (\(l \le r \le 10^{100\,000}\)).

Обратите внимание, что числа во вводе не помещаются в стандартные типы данных для целых чисел в большинстве языков программирования, в частности, в C++. Необходимо каким-либо специальным образом считывать входные данные, например, в виде строки.

Формат выходных данных
Выведите количество простоватых чисел от \(l\) до \(r\).

В 2025 году в Берляндии впервые будет проводиться трёхдневный межпланетный съезд по вопросам проведения олимпиад по информатике. Доклады съезда разбиты на 12 секций, и теперь организаторам необходимо распределить секции по дням: в каждый день будут проводиться 4 секции.

Известно, что в съезде примут участие \(n\) человек. Каждый участник съезда выбрал 3 секции, которые он хочет посетить. Но поскольку в один день секции будут проводиться одновременно, каждый участник в один день может присутствовать не более чем на одной секции. Поэтому если в один день будут идти две или три секции, выбранные каким-то участником, то он всё равно сможет посетить только одну из них. Если же выбранные секции будут проходить в разные дни, участник сможет посетить их все.

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(1 \leq n \leq 10\,000\)) — количество участников съезда.

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

Формат выходных данных
Программа должна вывести \(3\) строки, в каждой из которых должны быть \(4\) числа через пробел — номера секций, проводимых в первый, второй и третий день съезда соответственно. Каждое из чисел от 1 до 12 должно встречаться в выводе ровно один раз. Если возможных оптимальных расписаний несколько, можно вывести любое из них.

Примечание
В примере из условия расписание составлено так, что второй и третий участник посетят все желаемые секции, а первый — две секции (\(5\) и одну из секций \(1\), \(6\)). Таким образом, суммарно будут посещены 8 секций. Можно показать, что этот результат улучшить нельзя.

Арсений очень любит пользоваться городским транспортом. В городе, где он живёт, существует карта <<Тройка>>, позволяющая оплачивать проезд при помощи тарифа <<Кошелёк>>. Есть два вида тарифа:

• <<Единый>> (57 рублей) — одна поездка на любом виде транспорта;

• <<90 минут>> (85 рублей) — не более одной поездки на метро и любое количество поездок на наземном транспорте в течение не более 90 минут с момента начала первой поездки (между началом поездки и началом первой поездки должно пройти не более 90 минут).

Так как Арсений коллекционирует карты <<Тройка>>, у него их очень много, поэтому он может использовать неограниченное количество билетов одновременно.

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) — количество поездок, которые были запланированы, \(1 \le n \le 10^5\).

Следующие \(n\) строк содержат два значения, разделённые пробелом. Сначала указан вид транспорта: заглавная английская буква <<B>>, если Арсений будет использовать наземный транспорт, или заглавная английская буква <<M>>, если он воспользуется метро. Затем указано время начала поездки в формате ЧЧ:ММ (в виде двузначного количества часов и затем двузначного количества минут).

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

Также гарантируется, что разница времени совершения двух поездок составляет не менее 10 минут.

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

Примечание
В первом примере все три поездки могут быть оплачены одним тарифом <<90 минут>> за \(85\) рублей.

Во втором примере нужно одним билетом <<90 минут>> за \(85\) рублей оплатить первую (23:59), вторую (00:29) и четвёртую (01:29) поездки. Третью поездку (00:59) нельзя оплатить тем же билетом, потому что в тарифе <<90 минут>> может быть не более одной поездки на метро, для этой поездки придётся использовать отдельный билет за 57 рублей.

В третьем примере первую поездку (22:00) нужно оплатить отдельным билетом за 57 рублей, а следующие три поездки (23:00, 23:50, 00:30) — билетом <<90 минут>>.

Дана клетчатая сетка, состоящая из \(n \times m\) клеток со стороной 1, в каждой клетке проведены обе диагонали.

Например, сетка \(1 \times 2\) выглядит следующим образом:

Назовём прямоугольник на данной сетке подходящим, если его вершины расположены в узлах сетки, а длины его стороны равны \(1\) или \(2\) (то есть подходящими являются прямоугольники \(1\times1\), \(1\times2\), \(2\times1\), \(2\times2\)).

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

Посчитайте количество хороших треугольников на данной сетке.

Формат входных данных
Программа получает на вход два числа \(n\) и \(m\), записанных в отдельных строках, — размеры сетки, \(1 \le n \le 10^{8}\), \(1 \le m \le 10^{8}\).

Формат выходных данных
Программа должна вывести одно целое число — количество искомых треугольников.

Обратите внимание на то, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

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

Все треугольники из первого примера:

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

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

Для подъёма вверх по течению реки судно тратит \(a\) минут на один километр, а для спуска вниз по течению реки — \(b\) минут на один километр. Определите, на какой пристани должны начинаться оба маршрута, чтобы их продолжительности различались как можно меньше. Это значит, что необходимо минимизировать модуль разности времени в пути двух маршрутов.

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(3\le n\le 2\cdot 10^9\)) — общее количество пристаней на маршруте. Вторая строка содержит число \(a\) — время подъёма судна на один километр вверх по течению реки, третья строка содержит число \(b\) — время спуска на один километр вниз по течению, \(1\le b < a\le 2\cdot 10^9\).

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

Примечание
В примере из условия начальным пунктом маршрутов нужно сделать пристань 3. Тогда вверх по течению судно поднимется за \((3-1)\times 7=14\) минут, а вниз по течению реки спустится за \((8-3)\times3=15\) минут. Разница в продолжительности маршрутов составит 1, меньшей разности в данном примере достичь невозможно.

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

У Старца Летовца есть набор чисел. Эти числа можно склеивать друг с другом (или не склеивать вовсе), чтобы получать новые числа. Например, из набора чисел 12, 2 и 10 можно склеить число 12210, а можно 10212 — вариантов много, но выбрать придётся только один, потому что все числа в наборе в единственном виде.
Летовёнок задумался: какое максимальное количество чисел, делящихся на три, можно получить из этого набора?

Помогите ему решить эту задачу.

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

В первой строке ввода дано единственное число n (1<= n <=1000). Во второй строке ввода через пробел даны n чисел numi (1<=numi<=1000).

Формат выходных данных
Выведите одно число - максимальное количество чисел, кратных трём, которые можно получить из набора.


Примечание
В первом тестовом примере можно склеить числа 2 и 10 (получить 210 или 102) и в итоге получится 2 числа, кратные трём.

Во втором тестовом примере ничего склеивать не надо, так как. все числа уже кратны трём.

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

Формат входных данных
В первой строке вводится натуральное число n - количество туристических маршрутов в городе (1 <= n <= 10⁵). Во следующих n строках вводятся сами маршруты. Каждая строка с маршрутов представляет собой список достопримечательностей (слов), разделенных одним пробелом. Количество достопримечательностей в каждой строке не превышает 10⁹. Каждая достопримечательность записана в виде отдельного слова, состоящего только из английских букв и/или цифр.
Последняя строка содержит список достопримечетельностей, которые хочет увитеть турист.  Формат этой строки такой же как и в строках выше.
Гарантируется, что самый короткий подходящий маршрут существует и он единственный.

Формат выходных данных
Выведите самый короткий маршрут, включающий все выбранные туристом достопримечательности. Строка с маршрутом должна соответствовать какой-либо одной строке из входных данных.

В городе Летовецк  "Фестиваль Чисел" отмечается всегда в день с магической датой. Дата называется магической, если день, номер месяца и две последние цифры года совпадают. Например, 01.01.01 - магическая дата. 
По текущей дате, записанной в формате дд.мм.гг определите дату, когда будет отмечатся ближайший "Фестиваль чисел". То есть первую магическую дату, которая была бы не ранее текущей.

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

Рассмотрим все представления числа \(n\) в виде суммы различных целых возрастающих слагаемых: \(n = a_1 + a_2 + \ldots + a_k\), \(a_1 < a_2 < \ldots < a_k\).

Будем называть такое разбиение быстро возрастающим, если для него выполнено следующее условие: для любых трех подряд идущих слагаемых разница между большим и средним строго больше, чем между средним и меньшим, иначе говоря, \(a_{i+2} - a_{i+1} > a_{i+1} - a_i\).

Задано число \(n\). Выведите все его быстро возрастающие разбиения на слагаемые.

Формат входных данных
На ввод подается целое число \(n\) (\(1 \le n \le 100\)).

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

Выведите все быстро возрастающие разбиения на слагаемые числа \(n\). Разбиения можно выводить в любом порядке. Выводите слагаемые в каждом разбиении, разделяя их знаком <<+>> без пробелов.

Будем называть пару различных целых чисел похожими, если у них \(k\) последних цифр совпадает.

Дано число \(n\), найдите количество пар различных похожих чисел, состоящих из \(n\) цифр. Ведущие нули запрещены. Пары \((a, b)\) и \((b, a)\) считаются одинаковыми.

Формат входных данных
На первой строке находится целое число \(n\) (\(1 \le n \le 10\)).

На второй строке находится целое число \(k\) (\(1 \le k \le n\)).

Формат выходных данных
Выведите одно число — количество пар похожих чисел, состоящих из \(n\) цифр.

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

–Т—Л–≤–µ–і–Є—В–µ –і–≤–∞–і—Ж–∞—В—М –њ–µ—А–≤—Л—Е –њ—А–Њ—Б—В—Л—Е —З–Є—Б–µ–ї
 

Муми-Тролли хотят украсить свою ёлку гирляндами, чтобы она светилась во время новогоднего праздника. Известно, что длина всех витков гирлянды, необходимых для полного обвивания ёлки, составляет L метров. Каждая гирлянда имеет длину M метров. Помогите муми-троллям посчитать сколько всего гирлянд необходимо муми-троллям?

Формат входных данных
В первой строке записано натуральное число L (L < 10⁹). Во второй строке - натуральное число M (M < 10⁹).

Формат выходных данных
Выведите одно число - количество необходимых гирлянд

В биоинформатике перевод ДНК-последовательности в последовательность аминокислот — ключевой шаг в анализе генетических данных. Каждая группа из трёх нуклеотидов (триплет или кодон) кодирует определённую аминокислоту в соответствии с генетическим кодом.

Необходимо:

1. Найти старт-кодон ATG.
2. Найти ближайший стоп-кодон (TAA, TAG, TGA) после старт-кодона.
3. Перевести последовательность между старт- и стоп-кодонами в аминокислотную последовательность.
4. Повторить процесс для всех возможных белков в последовательности.

Можете использовать словарь генетического кода: https://silvertests.ru/NoteBook.aspx?id=58286

В процессе трансляции последовательность ДНК сначала транскрибируется в РНК, а затем транслируется в белок. Белки кодируются участками между старт-кодоном (ATG) и ближайшим стоп-кодоном (TAA, TAG, TGA). Длина белка измеряется количеством аминокислотных остатков, где каждые три нуклеотида (триплет) кодируют одну аминокислоту.
Надо написать программу, которая:

• Найти все белковые последовательности в заданной цепочке ДНК.
• Подсчитать длину каждой белковой последовательности (в аминокислотах).
• Вывести все найденные белки и их длины.

Длина белка в аминокислотах - это количество триплетов между старт- и стоп-кодонами.

Кодоны — это триплеты нуклеотидов (три буквы), которые определяют аминокислоты в процессе трансляции (синтеза белка).

1. Старт-кодон — кодон, с которого начинается считывание белковой последовательности. В ДНК это всегда ATG.
2. Стоп-кодоны — кодоны, которые сигнализируют окончание считывания. В ДНК это:
   • TAA
   • TAG
   • TGA

 

Надо написать программу, которая:

1. Находит все стартовые (ATG) и стоп-кодоны (TAA, TAG, TGA) в последовательности ДНК.
2. Возвращает их позиции (индексы).

Формат входных данных
Строка содержит последовательность ДНК

Формат выходных данных
В первой строке вывести позиции старт-кодонов в порядке возрастания, во второй строке вывести позиции стоп-кодонов в порядке возрастания.