Алгоритмы

948 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Фабрика игрушек#100800

Для школьного праздника нужно изготовить не менее K игрушек. На фабрике есть N автоматов. Автомат с номером i изготавливает одну игрушку за Ai минут.

Все автоматы начинают работу одновременно в момент времени 0 и работают независимо друг от друга. Закончив игрушку, автомат сразу начинает следующую. Материалов достаточно, готовых игрушек в начале нет.

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

Найдите минимальное время, за которое будет готово не менее K игрушек.

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

В первой строке записаны два целых числа N K — количество автоматов и необходимое количество игрушек.

Во второй строке записаны N целых чисел A1, A2, …, AN — время изготовления одной игрушки каждым автоматом.

1 ≤ N ≤ 1000; 1 ≤ K ≤ 109; 1 ≤ Ai ≤ 106.

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

Выведите одно целое число — минимальное время в минутах.

Алгоритмы поискаБинарный поиск
✓ 5✗ 7—Войти и решать
Карточки на квадратном стенде#100799

К школьной выставке подготовили N одинаковых прямоугольных карточек. Ширина каждой карточки — A сантиметров, высота — B сантиметров.

Карточки нужно разместить на квадратном стенде ровными горизонтальными рядами. В каждом ряду карточки стоят рядом, а ряды располагаются один над другим. Все карточки ориентированы одинаково: сторона A расположена горизонтально, сторона B — вертикально. Поворачивать карточки, накладывать их друг на друга и выпускать за края стенда нельзя. Зазоры между карточками не нужны; часть мест может остаться пустой.

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

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

В одной строке записаны три целых числа A B N.

1 ≤ A, B ≤ 1000; 1 ≤ N ≤ 106.

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

Выведите одно целое число — минимальную длину стороны стенда в сантиметрах.

Алгоритмы поискаБинарный поиск
✓ 13✗ 13—Войти и решать
3.3. Алекс и рюкзак исследователя#100094

Алекс выбирает приборы для экспедиции. У него есть n разных приборов. Каждый существует в единственном экземпляре и имеет массу wᵢ и научную ценность vᵢ. Массы и ценности выбранных приборов складываются.

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

Найдите максимальную ценность и соответствующую минимальную массу.

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

Первая строка содержит целые числа n и W (1 ≤ n ≤ 200, 1 ≤ W ≤ 10 000). Следующие n строк содержат wᵢ и vᵢ (1 ≤ wᵢ ≤ 20 000, 1 ≤ vᵢ ≤ 109).

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

Выведите два целых числа: максимальную ценность и минимальную массу набора с этой ценностью.

Пояснения к примерам

Пример 1. Нужно взять третий и четвёртый приборы: ценность 6 + 12 = 18, масса 2 + 5 = 7.

Пример 2. Ценность обоих одиночных наборов равна 5, поэтому выбираем более лёгкий.

АлгоритмыЗадача о рюкзаке
—Войти и решать
2.2. Алекс и журнал измерений#100088

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

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

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

Первая строка содержит целые числа n и K (1 ≤ n ≤ 200 000, 1 ≤ K ≤ 109). Вторая строка содержит n чисел aᵢ (0 ≤ aᵢ ≤ 109).

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

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

Пояснения к примерам

Пример 1. Подходят фрагменты [1,2], [1,3], [1,5], [3,3], [3,5], [4,5], [2,4]; в скобках указаны номера границ.

Пример 2. Подходят все шесть непустых фрагментов.

АлгоритмыОстатки
—Войти и решать
2.1. Алекс и мастерская значков#100087

К фестивалю Алекс готовит k значков. В мастерской работают n независимых станков. В момент 0 Алекс включает их все.

Станок i сначала прогревается sᵢ секунд, затем изготавливает один значок за pᵢ секунд. Его первый значок готов в момент sᵢ + pᵢ, второй — в момент sᵢ + 2pᵢ и так далее. Между значками станок не останавливается. Материалов достаточно.

Найдите самый ранний целый момент времени, когда суммарно будет готово не менее k значков. Значок, завершённый ровно в этот момент, уже считается готовым.

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

Первая строка содержит целые числа n и k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).

Следующие n строк содержат по два целых числа sᵢ и pᵢ (0 ≤ sᵢ ≤ 109, 1 ≤ pᵢ ≤ 109).

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

Выведите одно целое число — искомый момент времени в секундах.

Пояснения к примерам

Пример 1. К моменту 8 готовы 2 + 2 = 4 значка, а к моменту 9 — 3 + 2 = 5.

Пример 2. Значки единственного станка готовы в моменты 9, 13 и 17.

АлгоритмыБинарный поиск по ответу
—Войти и решать
1.4. Алекс и одноразовый пропуск#100085

Алекс должен пройти из зала s в зал t научного центра. Есть n залов и m двусторонних переходов. Каждый переход занимает одну минуту.

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

Найдите минимальное время пути. Использовать пропуск необязательно. Если добраться до цели невозможно, выведите −1.

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

Первая строка содержит целые числа n, m, s, t (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000, 1 ≤ s, t ≤ n). Старт и финиш могут совпадать.

Следующие m строк содержат u, v, c (1 ≤ u, v ≤ n, u ≠ v). При c = 0 переход открыт, при c = 1 — закрыт. Между парой залов не более одного перехода.

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

Выведите минимальное время в минутах либо −1, если допустимого маршрута нет.

Пояснения к примерам

Пример 1. Нужно идти 1 → 2 → 3 → 4 → 5 и использовать пропуск в конце. Быстрый переход 1 → 3 потратил бы пропуск слишком рано.

Пример 2. Чтобы пройти этот маршрут, понадобились бы два пропуска.

АлгоритмыОбход в ширину
—Войти и решать
1.1. Алекс и резервный генератор#100082

Алекс готовит оборудование экспедиции к испытаниям, которые продлятся n часов. В каждый час всё оборудование нужно обеспечить электричеством. В час i питание от основной сети стоит aᵢ монет, а питание от резервного генератора — bᵢ монет.

Генератор можно запустить не более одного раза. Сам запуск стоит C монет. После запуска генератор должен работать несколько последовательных полных часов, хотя бы один. Затем его можно выключить, но повторно включить уже нельзя. Пока генератор работает, всё оборудование питается от него, и плата за основную сеть не взимается.

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

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

Первая строка содержит целые числа n и C (1 ≤ n ≤ 200 000, 0 ≤ C ≤ 1014).

Вторая строка содержит n целых чисел a₁, …, aₙ — стоимость основной сети по часам. Третья строка содержит n целых чисел b₁, …, bₙ — стоимость работы генератора по часам. Для всех i: 0 ≤ aᵢ, bᵢ ≤ 109.

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

Выведите одно целое число — минимальную общую стоимость.

Пояснения к примерам

Пример 1. Выгодно включить генератор на часы со 2-го по 6-й. Эти часы стоят 2 + 7 + 2 + 7 + 2 = 20 монет. Ещё 5 монет стоит запуск, а в 1-й и 7-й часы сеть стоит по 2 монеты. Всего 29. В 3-й и 5-й часы генератор дороже сети, но включить его несколькими отдельными периодами нельзя.

Пример 2. Генератор дешевле в каждом часу, но за все три часа экономит только 3 монеты. Запуск за 10 монет не окупается; лучше пользоваться сетью.

АлгоритмыДинамическое программирование: один параметр
✓ 3✗ 2—Войти и решать
Cow Dance Show#90399
После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать \(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\)) пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время \(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\) немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени \(T\).

Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая максимально возможное значение величины \(T\). Ваша задача - определить минимально возможное подходящее значение \(K\).

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

Первая строка ввода содержит \(N\) и \(T_{max}\), где \(T_{max}\) - целое число, не более 1 000 000.

Следующие \(N\) строк задают длительности танцев \(d(1) \ldots d(N)\) для коров \(1 \ldots N\). Каждое из \(d(i)\) - целое число в интервале \(1 \ldots 100,000\).

Гарантируется, что если \(K=N\), шоу закончится вовремя.

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

Выведите наименьшее возможное значение \(K\) такое, что танцевальное шоу закончится не более чем через \(T_{max}\) единиц времени.

Бинарный поиск по ответуЖадный алгоритмОчередь
—Войти и решать
Counting Haybales#90366
Фермер Джон разместил свои \(N\) (\(1 \leq N \leq 100,000\)) стогов сена в различных точках одномерной дороги вдоль его фермы. Вам требуется ответить на \(Q\) (\(1 \leq Q \leq 100,000\)) запросов, о том сколько стогов сена находится внутри указанного участка дороги.

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

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

Следующая строка содержит \(N\) различных целых чисел, каждое в интервале \(0 \ldots 1,000,000,000\), указывающих местоположения стогов сена.

Каждая из последующих \(Q\) строк содержит два целых числа \(A\) и \(B\) (\(0 \leq A \leq B \leq 1,000,000,000\)) задающих запрос на количество стогов сена между \(A\) и \(B\), включительно.

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

Вы должны вывести \(Q\) строк. Для каждого запроса выведите количество стогов сена в соответствующем интервале.

Бинарный поиск в массивеИспользование сортировки
—Войти и решать
Moocast#90361
\(N\) (\(1 \leq N \leq 1000\)) коров Фермера Джона хотят организовать безопасную систему для передачи важных сообщений.

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

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до \(\sqrt{X}\). То есть, квадрат расстояния между коровами стоит не более \(X\) чтобы обеспечить их коммуникацией.

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

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

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

Каждая из \(N\) последующих строк содержит \(x\) и \(y\) координаты одной коровы. И то и другое - целое в интервале \(0 \ldots 25,000\).

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

Напишите в одну строку целое \(X\) - минимальное количество денег, которое коровы должны потратить на "воки-токи"

Бинарный поиск по ответуграфыПоиск компонент связности
—Войти и решать
Square Pasture#90357
Фермер Джон решил улучшить геометрию своей фермы. Раньше его коровы паслись на двух прямоугольных пастбищах. Фермер Джон хочет заменить их одним квадратным пастбищем минимального размера, который будет содержать эти два прямоугольника.

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

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

Первая строка входного файла описывает одно из оригинальных прямоугольных пастбищ четырьмя целыми числами, разделённых одиночными пробелами \(x_1\) \(y_1\) \(x_2\) \(y_2\) (все числа в диапазоне \(0 \ldots 10\)). Левый нижний угол пастбища – точка \((x_1, y_1)\), правый верхний угол – точка \((x_2, y_2)\), причём \(x_2 > x_1\) и \(y_2 > y_1\).

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

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

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

Задачи на моделированиеЭлементарная геометрия
—Войти и решать
High Card Wins#90354
Корова Беси - фанат карточных игр. Однако у неё нет достойных противников. Все они играют в полностью предсказуемой манере. Однако надо ещё придумать, как выиграть у них.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\). Они делят её поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

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

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

Первая строка ввода содержит значение N (\(1 \leq N \leq 50,000\)).

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

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

Выведите в одной строке максимальное количество очков, которое может заработать Беси.

Жадный алгоритмИспользование сортировки
—Войти и решать
High Card Low Card (Platinum)#90348
Беси и Эльза играютв простую карточную игру. Берётся колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\), и делится на две части по \(N\) карт для Беси и \(N\) карт для Эльзы. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте. Изначально, одно очко за каждый раунд выигрывает игрок, у которого карта больше. Однако однажды за всю игру Беси может переключить правила игры так, что до конца игры выигрывать одно очко за раунд будет игрок, карта которого меньше. Беси может также выбрать не использовать эту опцию, оставляя на всю игру правило "выигрывает бОльшая карта" или она может включить это правило перед первыми раундом, и тогда вся игра ведётся по правилу "выигрывает меньшая карта".

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

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

Первая строка ввода содержит значение N (\(2 \leq N \leq 50,000\)).

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

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

Выведите одну строку, содержащую максимальное количество очков, которое может заработать Беси.

Жадный алгоритмИспользование сортировки
—Войти и решать
Grass Segments#90276

Беси посадила траву на положительной вещественной прямой. У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы. И она посадит траву \(i\)-го сорта на интервале \([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).

Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\) (\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\) перекрываются на длину не менее \(k_i\).

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

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

Каждая из последующих \(N\) строк содержит три разделённых одиночными пробелами целых числа \(\ell_i\), \(r_i\), \(k_i\).

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

Ответы для всех сортов на отдельных строках.

SCORING:

  • Тесты 4-5: \(N \leq 5000\)
  • Тесты 6-11: \(k\) одинаковое для всех интервалов
  • Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).

Автор: Benjamin Qi

ОтрезкиПрефиксные суммы(минимумы, ...)Сортировка событий
—Войти и решать
Cowmpetency#90270

Фермер Джон нанимает нового вожака стада для своих коров. Для этого он интервьюирует \(N\) (\(2 \leq N \leq 10^5\)) коров на эту позицию. После интервью \(i\)-го кандидата он назначает целое число "уровень компетенции" \(c_i\) от \(1\) дo \(C\) включительно (\(1 \leq C \leq 10^9\)).

Поскольку ФД интервьюировал много коров, он не помнит все \(c_i\). Однако он помнит \(Q\) (\(1 \leq Q < N\)) пар чисел \((a_j, h_j)\) где корова \(h_j\) компетенция которой была строго больше, чем уровень компетенции коров от \(1\) до \(a_j\) (\(1 \leq a_j < h_j \leq N\)).

ФД говорит Вам последовательность \(c_1, \dots, c_N\) (где \(c_i = 0\) означает, что он забыл уровень компетенции коровы \(i\), и \(Q\) пар \((a_j, h_j)\). Помогите ему определить лексикографически минимальную последовательность уровней компетенции, соответствующую этой информации или указать, что такой последовательности не существует. Последовательность чисел называется лексикографически меньше другой последовательности если в ней меньшее число не первой позиции, где эти последовательности различаются.

Каждый ввод содержит \(T\) \((1 \leq T \leq 20)\) независимых подтестов. Гарантируется, что сумма \(N\) по всем подтестам не превысит \(3 \cdot 10^5\).

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

Первая строка содержит \(T\), количество независимых подтестов. Каждый подтест описывается так:
  1. Первая строка содержит \(N\), \(Q\), \(C\).
  2. Следующая строка содержит c1, \dots, cN\( \)(0 \leq ci \leq C)$.
  3. Каждая из последующих \(Q\) строк содержит пару \((a_j, h_j)\). Гарантируется что все \(a_j\) в текущем подтесте различны.

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

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

Жадный алгоритмЗадача на реализациюЗадачи на моделирование
—Войти и решать
Nap Sort#90264

Беси сортирует массив целых чисел собственным алгоритмом. У неё есть куча из \(N\) \((1 \leq N \leq 2\cdot 10^5)\) целых чисел \(a_1,a_2,\dots,a_N\) \((1 \leq a_i \leq 10^{11})\), которые она хочет перенести в другой массив в отсортированном порядке. Она постоянно ищет минимальный элемент в куче, удаляет его и добавляет в конец массива. Беси требуется \(p\) секунд, чтобы найти минимальный элемент в куче из \(p\) целых чисел.

ФД выделил Беси в помощь неограниченное количество коров. Беси использует их следующим образом. Она разделила все свои целые числа на две кучи: куча Беси и куча Помощниц. Для каждого числа в своей куче она выполняет алгоритм как обычно. Для каждого целого числа в куче Помощниц Беси назначает его отдельной корове. И предлагает ей поступать так. Когда корова помощница получает число \(a_i\), она должна подождать \(a_i\) секунд и затем добавить это число в конец массива. Если Беси и корова-помощница добавляют число в одно и то же время, то сначала добавляется число Беси. Если нескольким коровам-помощницам было дано одно и то же число, они добавляют копии этого числа в одно и то же время.

Помогите Беси поделить её числа так, чтобы финальный массив был отсортирован, а время сортировки было минимально.

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

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

Каждый подтест имеет такую структуру:

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

Следующая строка содержит \(a_1, a_2, \dots, a_N\), - целые числа, которые сортирует Беси. Некоторые целые числа могут появится множество раз.

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

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

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

Жадный алгоритмЗадачи на моделирование
—Войти и решать
Majority Opinion#90262

У Фермера Джона важная задача - решить какой тип сена купить для своих коров.

У Фермера Джона есть \(N\) коров (\(2 \le N \le 10^5\)) пронумерованных от \(1\) до \(N\). Каждая корова любит ровно один тип сена \(h_i\) (\(1 \le h_i \le N\)). ФД хочет, чтобы все его коровы любили один тип сена.

Чтобы это случилось, ФД может сформировать фокус-группы. Фокус-группа состоит из всех коров в непрерывном интервале от \(i\) до \(j\), включительно. Если в фокус-группе более половины коров любит один и тот же некоторый тип сена, то все коровы начинают любить этот тип сена, иначе ни у одной коровы не изменяется любимый тип сена. Например, если фокус группа состоит из 16 коров, 9 или более из которых любят один и тот же тип сена, то и остальные 7 коров теперь будут любить этот же тип сена.

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

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

Сначала идёт одно целое число \(T\), которое обозначает количество независимых тестов \((1 \leq T \leq 10)\).

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

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

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

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

Выведите \(T\) строк, по одной для каждого теста.

Если возможно сделать, чтобы все коровы полюбили один и тот же тип сена, выведите все такие возможные типы сена в порядке возрастания. Иначе, выведите \(-1\). Когда выводите список чисел, выводите соседние числа через один пробел, и в конце этой строки не должно быть пробелов.

Жадный алгоритмЗадачи на моделированиереализация
—Войти и решать
Stamp Grid#90200

Штамп-живопись это раскрашивание чёрным и белым цветом холста размером \(N \times N\) ячеек, где определённые ячейки закрашиваются, а другие - нет. Этот холст может быть представлен массивом символов \(N\times N\) (\(1\le N\le 20\)). The \(i\)-ый вход \(j\)-ой колонки массива равен символу '*', если холст содержит чернила в этой ячейке и символ '.' в противном случае.

У Беси есть план рисунка, а Фермер Джон дал ей штамп размером \(K\times K\) (\(1\le K\le N\)) который она может использовать для закраски холста размером \(N \times N\). Беси может поворачивать штамп на \(90^{\circ}\) по часовой стрелке и применять его для закраски холста в любом месте, если штамп помещается целиком на холсте. Формально, Беси выбирает такие целые числа \(i,j\), что \(i \in [1,N-K+1]\) и \(j \in [1, N-K+1]\); и затем для каждого \((i',j')\) такого, что \(1 \le i', j' \le K\), ячейка холста \((i+i'-1, j+j'-1)\) закрашивается в чёрный цвет, если в штампе было чернило в позиции \((i', j')\). Беси может поворачивать свой штамп в любой момент между закрашиваниями. Если ячейку закрасили она остаётся закрашенной навсегда.

ФД интересно может ли Беси создать свой рисунок, используя его штамп. Для каждого из \(T\) (\(1 \le T \le 100\)) подтестов помогите ФД получить ответ.

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

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

Каждый подтест начинается с целого числа \(N\), за которым следуют \(N\) строк, состоящих их символов '*' и '.', представляющих рисунок, который Беси хочет нарисовать. Следующая строка содержит число \(K\), за которым следует \(K\) строк, каждая из которых содержит символы '*' и '.', представляющих штамп ФД.

Последовательные подтесты разделены пустыми строками.

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

Для каждого подтеста выведите "YES" или "NO" на отдельной строке.
Задача на реализациюЗадачи на моделированиеПеребор
—Войти и решать
Farmer John Actually Farms#90189

Фермер Джон вырастил \(N\) (\(1 \leq N \leq 2\cdot 10^5\)) аспарагусов на своей ферме. Однако некоторые из этих растений имеют генетические отличия, поэтому некоторые растения растут быстрее чем другие. Изначальная высота \(i\)-го растения равна \(h_i\) дюймов и после каждого дня \(i\)-ое растение вырастает на \(a_i\) дюймов.

ФД любит некоторые растения больше чем другие, и он хочет, чтобы некоторые растения были выше чем другие. Он дал Вам массив различных целых чисел \(t_1,\dots,t_N\), содержащих все целые числа от \(0\) до \(N-1\) и хочет, чтобы \(i\)-ое растение имело ровно \(t_i\) растений, которые выше этого. Определите минимальное количество дней, чтобы требование ФД было удовлетворено или укажите, что это невозможно.

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

Первая строка состоит из целого числа \(T\), обозначающего количество независимых тестов \((1 \leq T \leq 10)\).

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

Вторая строка состоит из \(N\) целых чисел \(h_i\) \((1 \leq h_i \leq 10^9)\), обозначающих изначальную высоту \(i\)-го растения в дюймах.

Третья строка состоит из \(N\) целых чисел \(a_i\) \((1 \leq a_i \leq 10^9)\), обозначающих количество дюймов, на которые \(i\)-ое растение вырастает каждый день.

Четвёртая строка содержит \(N\) различных целых чисел \(t_i\), обозначающих массив, который ФД даст Вам.

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

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

Выведите \(T\) строк, ответ на каждый тест на отдельной строке. Если невозможно, выведите -1.

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

Вывод формулыЖадный алгоритмЗадачи на моделирование
—Войти и решать
Cowntact Tracing 2#90188

Фермер Джон выстроил в ряд свои \(N\) коров (\(1 \leq N \leq 3\cdot 10^5\)). К несчастью, стала распространяться болезнь.

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

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

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

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

Следующая строка содержит \(N\)-символьную битовую строку из цифр \(1\) и \(0\) где \(1\) представляет инфицированную корову, а \(0\) представляет неинфицированную корову после некоторого количества ночей.

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

Выведите одно целое число: минимальное количество коров, с которых могла стартовать болезнь.

Жадный алгоритмЗадачи на моделирование
—Войти и решать
Поделиться
Класснуть