Информатика

7 592 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Bessie's Dream#90338
После столь обильного поедания фруктов на кухне Фермера Джона, Беси посетили странные мечты. Она попала в лабиринт в форме решётки клеток \(N \times M\) (\(1 \le N, M \le 1,000\)). Она начинает в левой верхней клетке и хочет попасть в правую нижнюю. Когда она стоит в клетке, он может шагнуть в любом из четырёх направлений (вверх, вниз, вправо, вверх).

Однако подождите! Каждая клетка имеет свой цвет, и каждый цвет имеет различные свойства:

  • Если клетка red (красная), то в неё ходить нельзя
  • Если клетка pink (розовая), то в неё можно ходить
  • Если клетка orange (оранжевая), то в неё можно ходить, но Беси станет пахнуть как апельсин.
  • Если клетка blue (синяя) , то она содержит пираний, которые позволят Беси пройти только если она пахнет как апельсин.
  • Если клетка purple (пурпурная), то Беси проскальзывает в следующую клетку в этом направлении (если только в следующую клетку можно заходить). Если следующая клетка также пурпурная, Беси продолжает скользить, пока не попадёт в не пурпурную клетку или остановится перед непроходимой клеткой. Скольжение одной клетки засчитывается как один шаг. Пурпурные клетки также удаляют запах.

(Пример ниже подробнее поясняет "пурпурные" клетки)

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

ФОРМАТ ВВОДА (файл dream.in):

Первая строка ввода содержит два целых числа \(N\) и \(M\), представляющие количество строк и столбцов лабиринта.

Каждая из следующих \(N\) строк имеет по \(M\) целых чисел, представляющих лабиринт:

  • Целое число '0' это красная клетка
  • Целое число '1' это розовая клетка
  • Целое число '2' это оранжевая клетка
  • Целое число '3' это синяя клетка
  • Целое число '4' это пурпурная клетка

Левая-верхняя и правая-нижняя клетки всегда будут '1'.

ФОРМАТ ВЫВОДА (файл dream.out):

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

Обход в ширину
—Войти и решать
Speeding Ticket#90337
Беси, которая всегда создаёт проблемы, украла трактор Фермера Джона и помчалась вниз по дороге!

Дорога имеет длину ровно 100 миль и Беси едет по ней, пока её не остановит офицер полиции и не вручит ей квитанцию о превышении скорости.

Дорога поделена на \(N\) участков, каждый описывается положительной длиной в милях, а также целым числом - пределом скорости на этом участке, в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль, суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль, со скоростным пределом 60 миль в час.

Движение Беси тоже может быть описано серией участков - \(M\) штук. На каждом участке она проезжает определённое количество миль с определённой целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65, а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.

По заданной выше информации, определите максимальное превышение скорости, которое допустила Беси во время путешествия.

Формат ввода (файл speeding.in):

Первая строка ввода содержит \(N\) и \(M\), разделённые одним пробелом.

Каждая из следующих \(N\) строк содержит два целых числа, описывающих участок дороги: задавая его длину и предел скорости

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

Формат вывода (файл speeding.out):

Выведите одну строку, содержащую максимальное превышение предела скорости, которое допустила Беси. Если она никогда не превысила скорость, выведите 0.

Задачи на моделирование
—Войти и решать
Fence Painting#90336
Несколько сезонов жарких лет и холодных зим изрядно подпортили изгородь Фермера Джона, и он решил перекрасить её с помощью своей любимой коровы Беси. Беси отлично красит, но к несчастью плохо понимает команды ФД.

Если мы рассмотрим изгородь ФД как одномерную числовую прямую, то ФД закрашивает интервал между \(x=a\) and \(x=b\). Например, если \(a=3\) and \(b=5\), то ФД закрашивает интервал длиной 2. Беси, не понимая команды ФД, закрашивает интервал от \(x=c\) to \(x=d\), который может частично или полностью перекрываться с интервалом ФД. Пожалуйста, определите общую длину изгороди которую покрасят ФД и Беси.

Формат ввода (файл paint.in):

Первая строка ввода содержит целые числа \(a\) и \(b\), разделённые одним пробелом (\(a < b\)).

Вторая строка содержит целые числа \(c\) и \(d\), разделённые одним пробелом (\(c < d\)).

Значения \(a\), \(b\), \(c\), \(d\) все лежат в интервале \(0 \ldots 100\), включительно.

Формат вывода (файл paint.out):

Выведите в одной строке общую длину изгороди, покрытой краской.

Разбор случаев
—Войти и решать
Contaminated Milk#90335
Фермер Джон, известный качеством молока, производимого на его ферме, проводит молочную вечеринку для \(N\) своих лучших друзей (\(1 \leq N \leq 50\)). Из \(M\) сортов молока, подготовленных к вечеринке , (\(1 \leq M \leq 50\)) ровно один испортился, но ФД не знает какой. Тому, кто его выпьет, станет плохо.

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

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

Первая строка ввода содержит числа \(N\), \(M\), \(D\), \(S\).

Каждая из следующих \(D\) строк (\(1 \leq D \leq 1000\)) содержит три целых числа \(p, m, t\), указывающих, что персона \(p\) выпила сорт молока \(m\) в момент времени \(t\). Значение \(p\) находится в интервале \(1 \ldots N\), \(m\) в интервале \(1 \ldots M\), и \(t\) в интервале \(1 \ldots 100\). Кажды человек может пить один и тот же сорт молока несколько раз, и может пить несколько сортов молока в один и тот же момент времени.

Каждая из следующих \(S\) строк (\(1 \leq S \leq N\)) содержит два целых числа \(p, t\), указывающих, что персона \(p\) заболела в момент времени \(t\). Значение \(p\) в интервале \(1 \ldots N\), а значение \(t\) в интервале $1 \ldots 100$. Каждый человек заболеет не более одного раза, как следствие того, что он выпил плохое молоко в какой-то строго более ранний момент времени.

Формат вывода (файл badmilk.out):

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

Перебор
—Войти и решать
Piggyback#90334

Беси и её сестра Эльза пасутся на различных полях в течение дня, а вечером обе хотят вернуться в амбар отдыхать. Будучи умными коровами, они хотят составить план, чтобы минимизировать суммарное количество энергии, которое они обе потратят на это путешествие.
Беси тратит B единиц энергии, когда она переходит с одного поля на соседнее поле, а Эльза тратит E единиц энергии при переходе на соседнее поле. Однако, если Беси и Эльза оказались на одном поле, то Беси может нести Эльзу на своих плечах, и тогда обе могут переместиться на соседнее поле, потратив только P единиц энергии, (где P может быть существенно меньше, чем B+E - количество энергии, которое затрачивается двумя коровами вместе, если они перемещаются на соседнее поле по отдельности). Если P очень маленькое, то коровам выгоднее перемещаться вместе, а если P очень большое - то по отдельности.
По заданным B, E, P и расположению полей на ферме, вычислите минимальное количество энергии, которое потребуется Беси и Эльзе, чтобы добраться до амбара.
Формат входных данных
Первая строка ввода содержит положительные числа B, E, P, N, M. Все они не превышают 40,000. B, E, P описаны выше. N - количество полей на ферме, пронумерованных от 1 до N, N>=3. M - количество дорожек между полями. Беси и Эльза начинают в полях 1 и 2 соответственно. Амбар расположен в поле N.
Каждая из следующих M строк ввода описывает дорожку между парой различных полей, указанную номерами этих полей. Дорожки двунаправленные. Всегда можно добраться от поля 1 до поля N и от поля 2 до поля N посредством некоторого количества дорожек.

Формат выходных данных
Одно целое число, указывающее минимальное количество энергии, которое суммарно потратят Беси и Эльза, чтобы добраться до амбара. В примере, приведенном выше, Беси перемещается от 1 к 4, Эльза перемещается от 2 к 3, затем к 4. Потом они перемещаются вместе от 4 к 7, затем к 8.

Обход в ширину
—Войти и решать
Marathon#90333

Беси участвует в марафоне.
Маршрут марафона состоит из N контрольных точек (3 <= N <= 500),
которые надо посетить по порядку, причём контрольная точка 1 -
старт, контрольная точка N - финиш.

Беси решил пропустить до K (K сократить себе маршрут. Она не может пропустить контрольные точки
1 и N.

Определите минимальное расстояние которое пробежит Беси, если она
может пропустить до K контрольных точек.

Поскольку марафон проводится на улицах Манхэттена, то и расстояние
между точками (x1, y1) и (x2, y2) нужно определять манхэттенское:
|x1-x2| + |y1-y2|.

INPUT: (файл marathon.in)

В первой строке задаются N и K.
Каждая из следующих N строк содержит два разделённых пробелом целых
числа x и y, представляющих контрольную точку (-1000 <= x <= 1000,
-1000 <= y <= 1000). Контрольные точки даны в порядке, в котором они
должны посещаться.

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

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

Выведите миниальное расстояние, которое Беси может пробежать,
пропустив до K контрольных точек. В данном примере, пропустив
точки (8,3) и (10,-5) она пробежит минимальное растояние, равное 4.

Задача на реализацию
—Войти и решать
Cow Jog#90332

N (1 <= N <= 100,000) коров бегут по одной бесконечно длинной дорожке.
Все коровы начинают в различных позициях и некоторые коровы бегут с
разной скоростью.

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

Забег длится T минут (1 <= T <= 1,000,000,000).
Определите, сколько групп образуется к концу забега.
Две коровы рассматриваются принадлежащими к одной группе, если
они окажутся в одной позиции в конце T минут.

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

Первая строка ввода содержит два целых числа N и T.

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

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

Одно целое число, указывающее сколько групп останется после T минут.

Жадный алгоритм
—Войти и решать
Marathon#90331

Беси спланировала марафон, специфицировав N контрольных точек
(1 <= N <= 100,000), которые нужно последовательно посетить.

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

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

Поскольку марафон проходит на улицах Манхэттена, расстояние между двумя
контрольными точками с координатами (x1, y1) и (x2, y2) надо вычислять
как манхэттенское: |x1-x2| + |y1-y2|.

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

В первой стоке хадаются N и Q (1 <= Q <= 100,000).
Последующие N строк содержат (x,y)- положение N контрольных точек в порядке
их посещения вдоль маршрута. Все координаты в интервале -1000 .. 1000.
Последующие Q строк состоят из изменений и запросов по одному в строке,
которые необходимо обрабатывать в том порядке, в котором они заданы.
Эти строки имеют вид "U I X Y" или "Q I J".

Строка в форме "U I X Y" указывает, что местоположение точки с номером
I (1 <= I <= N) должно быть изменено на (X Y).

Строка в форме "Q I J" спрашивает минимальное время прохождения подмаршрута
от контрольной точки I до контрольной точки J (I<=J), с учётом того, что
коровы могут выбрать пропустить одну контрольную точку вдоль этого подмаршрута
(кроме точек I и J).

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

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

Префиксные суммы(минимумы, ...)
—Войти и решать
Guard Mark#90330

Фермер Джон и его стадо играют в фрисби. Беси бросает фрисби в поле,
и соирается бежать прямо к Марку.
Марк имеет высоту H (1 <= H <= 1,000,000,000), но имеется также N
(2 <= N <= 20) коров из команды Беси вокруг Марка . Они могут поймать
Фрисби, только если став друг на друга, они построят пирамиду высотой
не менее, чем высота Марка.
Каждая из N коров имеет высоту, вес и силу.
Сила указывает максимальный суммарный вес, который может находиться
выше её.

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

Максимальный коэффициент безопасности пирамиды - количество веса,
которое может быть добавлено, на её вершину, так чтобы не превысить
силу ни одной из коров.

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

Первая строка ввода содержит N и H.

Каждая из следующих N строк ввода описывает одну корову, задавая
её высоту, вес и силу. Все числа положительные, не превышающие
1 миллиард.

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

Если команда Беси может построить пирамиду, достаточную, чтобы поймать
фрисби, выведите максимально достижимый фактор безопасности для такой
пирамиды. Иначе выведите фразу "Mark is too tall" (без кавычек).

Задача о рюкзаке
—Войти и решать
Cow Jog#90329

N (1 <= N <= 100,000) коров фермера Джона бегут по бесконечной
трассе. Все коровы начинают в различных позициях и некоторые
коровы бегут с различной скоростью.

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

Фермер Джон хочет, чтобы никакая корова не меняла свою дорожку
или изменяла свою скорость. И он интересуется, сколько дорожек
ему нужно, если коровы будут бежать T минут (1 <= T <= 1,000,000,000).

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

Первая строка ввода содержит N и T.
Каждая из последующих N строк содержит начальную позицию и скорость
одной коровы. Позиция - это неотрицательное целое число, а скорость -
положительное целое число, оба не более 1 миллиарда. Все коровы начинают
в различных позициях, заданных в порядке возрастания на вводе.

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

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

Жадный алгоритм
—Войти и решать
Learning by Example#90327

Фермер Джон решил использовать данные о своём стаде коров,
чтобы построить автоматический распознаватель, имеет корова
пятна или нет.

К несчастью, ФД не ученье удачно собрал данные о своих коровах
Для каждой из его N(1 <= N <= 50,000) коров, всё что он знает, это
вес коровы и имеет или нет она пятна. Все его коровы имеют
различный вес. По этим данным он построил то, что он назвал,
"классификатор ближайшего соседа". Чтобы угадать, есть у новой
коровы C пятно или нет, он сначала находит в своём стаде корову С'
такую, что её вес ближайший к C'. Если корова C' имеет пятна,
то ФД предполагает, что корова C имеет пятна, если корова C'
не имеет пятен, то ФД предполагает, что и корова C не имеет пятен.
Если же уникального ближайшего соседа нет, а есть две коровы
на одинаковом минимальном расстоянии от C', тогда ФД предполагает,
что корова C имеет пятна, если одна из двух ближайших коров
также имеется пятна.

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

Пожалуйста, определите, сколько из этих коров будут классифицированы
как имеющие пятна. Заметим, что классификатор делает предсказание,
основываясь на данных об N существующих коровах.
Также заметим, что A и B могут быть достаточно большими числами,
так что просто проверка всех чисел по одному от A до B не пройдёт
по времени.

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

Первая строка ввода содержит три целых числа N,A,B
(1 <= A <= B <= 1,000,000,000).

Каждая из следующих N строк описывают одну корову. Каждая строка
содержит либо S W, означающее, что корова с весом W имеет пятна
или NS W, означающее, что корова с весом W не имеет пятен.
Все веса - целые числа в интервале 1 ... 1 000 000 000.

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

Одно целое число - количество коров из прибывших,
которых алгоритм ФД классифицирует как пятнистых.

В приведенном примере новые коровы с весами
1, 2, 7, 8, 9, 10
будут классифицированы как пятнистые.

Классификация по фиксированному правилу
—Войти и решать
Crosswords#90326

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

Вам даётся кроссворд, как решётка N*M (3 <= N <=
50, 3 <= M <= 50). Некоторые из клеток пусты (обычно они
белые), а некоторые заблокированы (обычно они чёрные).

Теперь процесс присвоения номеров загаданным словам -
это простой процесс из двух логических шагов:

Шаг 1: Для каждой ячейки мы определяем, начинает ли она
горизонтальное загаданное слово, или вертикальное
загаданное слово. Чтобы ячейка начинала горизонтальное
загаданное слово, нужно, чтобы её левая соседка была
заблокированной ячейкой или лежала вне кроссворда и две
клетки вправо от неё должны быть пустыми. (То есть
горизонтальное загаданное слово всегда содержит 3 или более
символов). Правила для ячейки, начинающей вертикальное
загаданное слово аналогичны: ячейка сверху должна быть
заблокирована или вне кроссворда и две клетки вниз
должны быть пустыми.

Шаг 2: Мы назначаем номер каждой ячейке, которая начинает
слово, последовательно от 1 в том же порядке, в котором
мы читаем книгу.
В первой строке назначаем числа слева направо, затем во
второй строке назначаем числа слева направо и т.д.
Числа назначаются только ячейкам, начинающим слова.

Например, рассмотрим кроссворд, где пустые ячейки отмечены
символами '.'. а блокированные ячейки отмечены символами '#'.

...
#..
...
..#
.##

Ячейки, которым могут быт присвоены номера
горизонтальных или вертикальных загаданных слов
помечены символами !.

!!!
#..
!..
..#
.##

Номера должны быть таковы:

123
#..
4..
..#
.##

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

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

Первая строка ввода содержит N и M, разделённые
одиночным пробелом.

Последующие N строк ввода описывают строки
решётки. Каждая состоит из M символов, каждый из которых
либо '.' (пустая ячейка) либо '#' (блокированная ячейка).

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

На первой строке выведите количество загаданных слов.
На каждой из оставшихся строк выведите строку и колонку
дающую позицию одного слова (в порядке, описанном выше).
Верхняя левая ячейка имеет позицию (1,1). Нижняя правая
ячейка имеет позицию (N,M).

Задача на реализацию
—Войти и решать
Cow Jog#90325

Имеется N коров, бегающих вдоль бесконечно-длинной прямой
трассы. (1 <= N <= 100,000). Каждая корова начинает
с уникальной позиции и некоторые коровы бегут с различной скоростью.
Трасса имеет только одну дорожку и корова не может
перепрыгнуть другую. Поэтому, когда более быстрая корова
настигает более медленную, она замедляет свою скорость
и становится частью некоторой бегущей группы коров.

Фермер Джон хочет, чтобы ВЫ посчитали,
сколько таких групп образуется.

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

Первая строк ввода содержит целое число N.
Каждая из последующих строк содержит начальную позицию
и скорость одной коровы. Позиция - это неотрицательное
целое число, а скорость - положительное целое число,
оба числа не более 1,000,000,000.
Все коровы начинают в различных позициях, которые
задаются в порядке возрастания на вводе.

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

Одно целое число, указывающее, сколько групп останется.

Жадный алгоритм
—Войти и решать
Compatible Pairs#90322

Фермер Джон заметил, что имеется \(N\) (\(1\le N\le 2\cdot 10^5\)) уникальных ID-номеров и для каждого уникального ID \(d_i\) (\(0\le d_i\le 10^9\)), имеется \(n_i\) (\(1\le n_i\le 10^9\)) коров с таким ID.

Эти коровы могут коммуницировать в парах, их секретный метод шифрования имеет одно строгое правило: две коровы могут обмениваться информацией если это не одна и та же корова и сумма их ID-номеров равна или \(A\) или \(B\) (\(0\le A\le B\le 2\cdot 10^9\)). В один момент времени, корова может быть вовлечена только в одну беседу (то есть никакая корова не может быть частью более чем одной пары)

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

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\), \(A\), \(B\).

Каждая из последующих \(N\) строк содержит \(n_i\) и \(d_i\). Никакие два \(d_i\) не совпадают.

ФОРМАТ ВЫВОДА (на экран / stdout):

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

В задаче может потребоваться использование 64-битного целого типа данных (например, "long long" в C/C++).

Жадный алгоритм
—Войти и решать
Lazy Sort#90320

У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 5\cdot 10^6\)) и пытается заставить их отсортировать неотрицательный целочисленный массив \(A\) длины \(N\), полагаясь на их лень. У него много тяжелых коробок, поэтому он выстраивает коров одну за другой, где корова \(i+1\) находится за коровой \(i\), и дает \(a_i\) коробок корове \(i\) (\(0\le a_i\)).

Коровы по своей природе ленивы, поэтому они всегда ищут способ передать свою работу кому-то другому. От коровы \(1\) до \(N-1\) по порядку каждая корова смотрит на корову позади себя. Если у коровы \(i\) строго больше коробок, чем у коровы \(i+1\), корова \(i\) считает, что это «несправедливо» и отдает одну из своих коробок корове \(i+1\). Этот процесс повторяется, пока каждая корова не будет удовлетворена.

Фермер Джон пометил количество ящиков \(b_i\), которое каждая корова \(i\) держит и создал массив \(B\) из этих величин. Если \(B = sorted(A)\) тогда ФД счастлив. К несчастью. ФД забыл все кроме \(Q\) величин массива \(A\). (\(2 \leq Q \leq \min(N, 100)\)). К счастью, эти величины включают количество ящиков, которое он собирается дать первой и последней корове. Каждое число, которое помнит ФД задано в виде \(c_i \; v_i\), представляющее, что \(a_{c_i}=v_i\). (\(1 \leq c_i \leq N\), \(1\le v_i\le 10^9\)). Определите количество различных способов, которыми могут быть заполнены пропущенные величины так чтобы ФД был счастливым. ответ выводите по модулю \(10^9+7\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит два разделённых пробелом целых числа \(N\) и \(Q\) представляющие количество коров и запросов соответственно.

Следующие \(Q\) строк содержат два разделённых пробелом целых числа \(c_i \; v_i\) представляющих что корова \(c_i\) изначально держит \(v_i\) ящиков. Гарантируется, что \(c_1 = 1\), \(c_Q = N\), и \(c_i < c_{i+1}\) (порядок коров строго возрастающий).

ФОРМАТ ВЫВОДА (на экран / stdout):

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

дпЖадный алгоритм
—Войти и решать
OohMoo Milk#90318

У Фермера Джона есть \(N\) \((1 \leq N \leq 10^5)\) бутылок, которые он хочет наполнить молоком. Каждая бутылка изначально содержит некоторое количество молока \(m_i\) \((0 \leq m_i \leq 10^9)\). Каждый день он берёт \(A\) \((1 \le A \le N)\) бутылок и наполняет одной единицей молока.

К несчастью, Фермер Нхой, соперник ФД по бизнесу, знает об этом процессе ФД и намерен навредить. Каждый день после того, как ФД заполнит свои \(A\) бутылок, ФН незаметно крадёт одну единицу молока из \(B\) \((0 \le B < A)\) различных непустых бутылок. Чтобы оставаться незамеченным, ФН выбирает \(B\) так, чтобы оно было строго меньше чем \(A\).

После \(D\) (\(1 \leq D \leq 10^9\)) дней ФД продаёт своё молоко. Если в бутылке \(M\) единиц молока, он продаёт эту бутылку за \(M^2\) денежных единиц.

Пусть \(P\) - уникальная прибыль, такая, что FJ может гарантировать, что он получит не менее \(P\) прибыли независимо от того, как ведет себя FN, а FN может гарантировать, что FJ получит не более \(P\) прибыли независимо от того, как ведет себя FJ. Выведите значение \(P\) по модулю \(10^9+7\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(N\) и \(D\), где \(N\) это количество бутылок, а \(D\) - количество дней.

Вторая строка содержит \(A\) и \(B\) количество единиц молока, которое ФД добавляет, а ФН вычитает соответственно.

Третья строка содержит \(N\) разделённых пробелами целых чисел \(m_i\), представляющих изначальное количество молока в бутылках.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите значение \(P\) по модулю \(10^9+7\).

Жадный алгоритм
—Войти и решать
Moo Decomposition#90317

Вам дана длинная строка \(S\) из символов M и O и целое число \(K \geq 1\). Посчитайте количество способов разбить \(S\) на подпоследовательности так, что каждая подпоследовательность MOOOO....O с ровно \(K\) O, по модулю \(10^9+7\).

Поскольку строка очень длинная, Вам она не дана точно. Вместо этого Вам дано целое число \(L\) (\(1 \leq L \leq 10^{18}\)), и строка \(T\) длины \(N\) (\(1 \leq N \leq 10^6\)). Строка \(S\) есть конкатенация \(L\) копий строки \(T\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(K\), \(N\), \(L\).

Вторая строка содержит строку \(T\) длины \(N\). Каждый символ или M или O.

Гарантируется, что количество декомпозиций \(S\) не равно 0.

ФОРМАТ ВВОДА (на экран / stdout):

Выведите количество разбиений строки \(S\), по модулю modulo \(10^9+7\).

дпразделяй и властвуйРекуррентные последовательности
—Войти и решать
More Cow Photos#90315

Фермер Джон выстроил коров в ряд и хочет их сфотографировать.

Каждая из \(N\) коров \((1 \le N \le 10^5)\) имеет целую высоту от \(1\) до \(N\). ФД хочет сфотографировать их в определённом порядке. Если коровы с высотами \(h_1, \dots, h_K\) стоят в ряд слева направо, он хочет, чтобы для их высот выполнялись следующие три свойства:

  • Чтобы высоты коров сначала возрастали, а потом убывали. Формально, должно существовать такое целое число \(i\), что \(h_1 \le \dots \le h_i \ge \dots \ge h_K\).
  • Чтобы рядом стояли коровы с одинаковой высотой. Формально, \(h_i \neq h_{i+1}\) для \(1 \le i < K\).
  • Чтобы фотография была симметричной. Формально, если \(i + j = K+1\), then \(h_i = h_j\).

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

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Имеется множество подтестов.

Первая строка ввода содержит одно целое число \(T\) (\(1 \leq T \leq 10^5\)), обозначающее количество подтестов. Далее следуют \(T\) подтестов.

Первая строка каждого подтеста содержит одно целое число \(N\). Вторая строка каждого подтеста содержит \(N\) целых чисел, высоты имеющихся \(N\) коров. Эти числа в интервале от \(1\) до \(N\).

Гарантируется, что сумма \(N\) по всем подтестам не превысит \(10^6\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите \(T\) строк, \(i\)-ая строка содержит ответ на \(i\)-ый подтест - целое число, обозначающее максимальное количество коров, которых ФД может включить в фотографию.

Жадный алгоритм
—Войти и решать
It's Mooin' Time III#90314

Беси анализирует строку из \(N\) (\(3 \leq N \leq 10^5\)) маленьких латинских букв \(s_1s_2 \ldots s_N\). Эльза рассматривает строку \(t\), содержащую три символа как MOO если \(t_2 = t_3\) и \(t_2 \neq t_1\).

Триплет \((i, j, k)\) валидный, если \(i < j < k\) и строка \(s_i s_j s_k\) формирует MOO. Для этого триплета ФД выполняет следующее, чтобы вычислить его величину

  • ФД сгибает строку \(s\) на 90-градусов в индексе \(j\)
  • Величина триплета - удвоенная площадь \(\Delta ijk\).

Другими словами, величина триплета есть \((j-i)(k-j)\).

Беси задаёт Вам \(Q\) (\(1 \leq Q \leq 3 \cdot 10^4\)) вопросов. В каждом вопросе она даёт Вам два целых числа \(l\) и \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1 \ge 3\)) и просит Вас определить максимальную величину среди всех валидных триплетов \((i, j, k)\) таких, что \(l \leq i\) и \(k \leq r\). Если валидных триплетов нет, выведите \(-1\).

Решение задачи может потребовать использовать 64-й целый тип (например, "long long" in C/C++).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит два целых числа \(N\) и \(Q\).

Следующая строка содержит символы \(s_1 s_2, \ldots s_N\).

Последующие \(Q\) строк содержат по два целых числа \(l\) и \(r\), обозначающих запрос.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите ответ на каждый вопрос в отдельной строке.
Отрезки
—Войти и решать
Farmer John's Favorite Operation#90311

У Фермера Джона есть массив \(a\) из \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) неотрицательных целых чисел и целое число \(M\) (\(1 \leq M \leq 10^9\)). Затем ФД спрашивает у Беси число \(x\). За одну операцию ФД может выбрать индекс \(i\) и вычесть или прибавить \(1\) к \(a_i\). ФД называет число скучным - если оно равно минимальному количеству операций, которые он должен выполнить, чтобы \(a_i-x\) стало делится на \(M\) для всех \(1 \leq i \leq N\).

Среди всех возможных \(x\) выберите минимально возможное скучное число.

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит \(T\) (\(1 \leq T \leq 10\)), количество независимых подтестов.

Первая строка каждого подтеста содержит числа \(N\) и \(M\).

Вторая строка каждого подтеста содержит \(a_1, a_2, ..., a_N\) (\(0 \leq a_i \leq 10^9\)).

Гарантируется, что сумма \(N\) по всем подтестам не превысит \(5 \cdot 10^5\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Для каждого подтеста выведите целое число - минимальное скучное число по всем возможным \(x\).

Префиксные суммы(минимумы, ...)сортировкитеория чисел
—Войти и решать
Поделиться
Класснуть