Информатика

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

Всякий раз когда ФД строит новый амбар, он соединяет его не более чем одной двунаправленной дорожкой с существующим амбаром. Чтобы обеспечить достаточное удаление коров он иногда хочет определить расстояние от определённого амбара до самого дальнего амбара достижимого от этого амбара. Расстояние между двумя амбарами определяется как количество дорожек, по которым нужно пройти от одного амбара до другого.

ФД имеет \(Q\) (\(1 \leq Q \leq 10^5\)) запросов, каждый вида "построить" или "расстояние". Для запроса "построить" ФД строит амбар и соединяет его не более чем с одним из имеющихся амбаров. На запрос "расстояние" ФД спрашивает у Вас от определённого амбара до самого дальнего амбара достижимого от этого амбара по некоторой последовательности дорожек. Гарантируется, что амбар запроса уже построен. Ответьте на запросы ФД.

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

Первая строка содержит целое число \(Q\). каждая из последующих \(Q\) строк содержит запрос. Каждый запрос имеет вид "B p" или "Q k", соответственно построить амбар и соединить его с амбаром \(p\) или вывести дальнейшее расстояние по условию задачи от амбара \(k\). Если \(p = -1\), то новый амбар не соединяется ни с каким из старых. Иначе \(p\) - номер амбара в порядке построения. Амбары нумеруются от \(1\), т.е. Первый построенный амбар будет иметь номер \(1\), второй - \(2\), и т.д.

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

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

Двоичные подьемыНаименьший общий предок
—Войти и решать
Cow Gymnasts#90006
Соскучившись от жизни на ферме, коровы ушли в бродячий цирк. И с ними готовится новое шоу.

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

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

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

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

Ввод - олдно целое число, \(N\) (\(1 \leq N \leq 10^{12}\)).

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

Одно целое число - количество магических конфигураций по модулю \(10^9 + 7\).

Вывод формулыКомбинаторикатеория чисел
—Войти и решать
Mooyo Mooyo#89999
Имея много свободного времени, коровы Фермера Джона часто играют в видеоигры. Одна из их любимых игр похожа на Puyo Puyo. Коровья версия этой игры называется Му-Му.

Игра Му-Му происходит на высокой узкой решётке из \(N\) ячеек в высоту и (\(1 \leq N \leq 100\)) и 10 ячеек в ширину. Вот пример для \(N = 6\): 

0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

Каждая ячейка или пустая (обозначена 0) или содержит стог сена одного из 9 различных цветов (обозначенных символами 1..9). Гравитация вынуждает стоги сена падать вниз, поэтому никогда 0 не будет ниже, чем стог сена.

Две ячейки принадлежат одному и тому же связному региону, если они имеют общую вертикальную или горизонтальную сторону и один и тот же цвет, отличный от 0. Каждый раз, когда регион начинает содержать \(K\) или более ячеек, все его стоги сена исчезают - превращаются в 0. Если в один момент времени существует несколько таких регионов они исчезают все одновременно. Затем, гравитация может вынудить стоги сена заполнить некоторые из ячеек, которые стали нулевыми. В получившейся конфигурации могут снова образоваться региона размера не менее \(K\) ячеек. В этом случае они также исчезают (одновременно, если есть несколько таких регионов). Затем гравитация вновь двигает вниз стоги сена и процесс повторяется, пока есть хоть один регион, в котором не менее \(K\) стогов.

По заданной конфигурации доски для Му-Му вычислите финальную картинку доски после выполнения всех операций.

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

Первая строка ввода содержит \(N\) и \(K\) (\(1 \leq K \leq 10N\)). Оставшиеся \(N\) строк задают начальное состояние доски.

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

Выведите \(N\) строк, описывающих финальное состояние поля.

Задачи на моделированиеПоиск компонент связностиреализация
—Войти и решать
Diamond Collector#89963
Беси собрала \(N\) алмазов (\(N \leq 1000\)) различных размеров. И хочет разместить их специальным образом в амбаре.

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

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

Первая строка ввода содержит \(N\) и \(K\) (\(0 \leq K \leq 10,000\)). Каждая из следующих \(N\) строк содержит целое число, определяющее размер одного из алмазов. Все размеры - положительные числа, не превышающие \(10,000\)

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

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

"Два указателя"Использование сортировки
—Войти и решать
Bull in a China Shop#89962
Фермер Джон решил украсить свой дом. Посетив местный китайский магазинчик, увидел стеклянную фигурку коровы и решил её купить.

Форма этой коровы описывается решёткой из \(N \times N\) символов (\(3 \leq N \leq 8\)), пример показан ниже, где символы '#' представляют часть коровы, а символы '.' не части коровы. 

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

К несчастью, ФД ещё не спел купить корову, как в магазинчик ворвался бык, который поломал всё вокруг, включая корову ФД. Корова разломалась на две части, которые затерялись среди других \(K\) (\(3 \leq K \leq 10\)) кусков стекла на полу. Каждый из этих \(K\) кусков описывается решёткой \(N \times N\) символов, как и исходная фигурка.

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

ФД может двигать оба куска горизонтально и/или вертикально на любое количество позиций, но так, чтобы все символы '#' оставались внутри решётки \(N \times N\). Форма каждого из кусков необязательно состоит из связного региона символов '#'. Но при сдвиге все они сдвигаются на одинаковое количество позиций.

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

Первая строка ввода содержит \(N\) и \(K\). Следующие \(N\) строк описывают исходную фигурку ФД. Следующие \(KN\) строк задают \(K\) решёток символов, описывающих \(K\) кусков, которые ФД нашёл на полу.

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

Выведите одну строку, содержащую два разделённых пробелом целых числа, каждое в интервале \(1 \ldots K\), указывающих индексы двух кусков коровы ФД. Решение всегда существует и уникально. Числа, которые Вы выведете, должны быть в порядке возрастания.

Задачи на моделированиеПереборреализация
—Войти и решать
Trapped in the Haybales (Silver)#89961
Фермер Джон получил груз из \(N\) больших стогов сена (\(1 \le N \le 100,000\)), и разместил стога в различных позициях вдоль дороги, соединяющей амбар с его домом. Каждый стог с номером \(j\) имеет размер \(S_j\) и находится в уникальной позиции \(P_j\) определяющей его положение вдоль одномерной дороги. Корова Беси расположена в настоящий момент в позиции \(B\),где нет стога сена. Беси может передвигаться вдоль дороги вплоть до позиции, где расположен стог сена, но она не может проходить эту позицию. Как исключение, если она движется в некотором направлении \(D\) единиц расстояния, то она набирает скорость достаточную чтобы уничтожить любой стог сена с размером строго меньше, чем \(D\). Конечно после того как она сделает это, она может бежать дальше к другим стогам и уничтожать их аналогичным способом.

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

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

Первая строка ввода содержит \(N\) и начальную позицию Беси \(B\). Каждая из последующих \(N\) строк описывает стог и содержит два целых числа, определяющих его размер и местоположение. Все размеры и положения находятся в диапазоне \(1\ldots 10^9\).

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

Выведите одно целое число, определяющее минимальное количество сена, которое должен добавить ФД чтобы Беси не выбралась из ловушки. Выведите -1, если это сделать невозможно.

Жадный алгоритмОтрезкиреализация
—Войти и решать
Code Breaking#89946

Фермер Джон спрятал ключи от трактора в сейфе. Коровы пытаются взломать этот сейф. Сейф защищён сложной парольной системой. Она организована как корневое дерево из N (1 <= N <= 20,000) вершин, каждая из которых требует цифру от 0 до 9. Вершины пронумерованы от 0 до N-1.
Единственная информация, которой владеют коровы – что определённая последовательность длины 5 не случается на путях в этом дереве.
Например, предположим, то дерево выглядит так (с корнем в A):
A <- B <- C <- D <- E ^ | F
Коровы могут знать, что последовательность 01234 не случится начиная от F, И что последовательность 91234 не случится, начиная от E. Эта информация приводит к тому, что возможными остаются 19 паролей, все такого вида:
The cows might know that the sequence 01234 does not occur starting at F, and that the sequence 91234 does not occur starting at E. This information rules out 19 possible passcodes: all those of the form
4 <- 3 <- 2 <- 1 <- * ^ | 0
или
4 <- 3 <- 2 <- 1 <- 9 ^ | *
Что даёт 19 паролей, поскольку такой
4 <- 3 <- 2 <- 1 <- 9 ^ | 0
появится дважды
По заданным M (1 <= M <= 50,000) последовательностям длины 5, вместе с их стартовой позицией в дереве помогите коровам вычислить сколько паролей будет подходить. Вы должны выводить свой ответ по модулю 1234567.

PROBLEM NAME: code
Формат ввода:
* Строка 1: Два разделённых пробелом целых числа, N и M.
* Строки 2..N: Строка i+1 содержит одно целое число p(i), означающее родителя вершин I в дереве (0 <= p(i) < i).
* Строки N+1..N+M: Строка N+i описывает i-ую последовательность про которую известно, что она не произойдёт в коде. Строка содержит v(i) и s(i), разделённые пробелом. Здесь v(i) - стартовая вершина последовательности, s(i) – строка из 5 цифр, которая не встретится в шифре начиная с вершины v(i) если двигаться вверх по дереву. Гарантируется, что корень дерева находится не менее чем в 4 шагах от v(i).

Вывод формулыграфыДеревья
—Войти и решать
Cross Country Skiing#89932

Лыжная трасса описана решёткой из M x N высот (1 <= M,N <= 500), каждая из высот в диапазоне 0 .. 1,000,000,000.
Некоторые из этих ячеек обозначены как точки маршрута гонки. Организаторы хотят назначить маршруту рейтинг трудности D так, чтобы корова могла попасть в любую точки маршрута из любой другой точки маршрута, последовательно перемещаясь между соседними ячейками, абсолютная разность высот которых не превышает D. Две ячейки считаются соседними, если они граничат по стороне (в направлении на север, юг, запад или восток одна от другой). Рейтинг трудности маршрута это минимальное значение D такое, что все точки маршрута взаимно достижимы при выполнении вышеописанного требования.
PROBLEM NAME: ccski
Формат входных данных
* Строка 1: Целые числа M и N.
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин 0 или 1, 1 указывает, что данная высота – точка маршрута гонки.

Формат выходных данных
* Строка 1: Рейтинг трудности маршрута (минимальное значение D такое, что все точки маршрута взаимно достижимы)
Примечание
Если D = 21, то все 3 точки маршрута взаимно достижимы. Если D<21 верхняя правая точка не достижимы из других двух.

Бинарный поиск по ответуграфыОбход в ширину
—Войти и решать
The Cow Run#89893

Фермер Джон забыл заделать дыру в изгороди на своей ферме и его N (1 <= N <= 1,000) коров сбежали и бедокурят. Каждая минута, когда корова находится вне изгороди, она "бедокурит" на 1 доллар. ФД должен посетить каждую корову, чтобы "усмирить" ее и прекратить долларовые потери от нее.
К счастью, коровы находятся вдоль одной прямой на различных растояниях от фермы. ФД знает расстояние Pi (-500,000 <= Pi <= 500,000, Pi != 0) каждой коровы i относительно ворот (позиция 0), из которых он стартует.
ФД двигается на 1 единицу расстояния за минуту и "усмиряет" корову мгновенно. Определите порядок, в котором ФД дожен посещать коров, так чтобы минимизировать свои долларовые потери.
PROBLEM NAME: cowrun
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..N+1: Строка i+1 содержит целое число Pi.
Формат выходных данных
* Строка 1: Минимальная общая стоимость долларовых потерь
Примечание
Оптимальный порядок посещения --2, 3, 7, -12. ФД прибудет в позицию -2 на 2-ой минуте и получит ущерб в два доллара от этой коровы.
Потом он проследует в позицию 3 (расстояние 5), итого ущерб = 2+5=7 долларов от второй коровы.
Затем он потратит 4 минут чтобы добраться до коровы в позиции 7, с общей стоимостью потерь от этой коровы 7+4 = 11 долларов.
Наконец, он потратит 19 минут чтобы перейти в точку -12, и стоимость потерь от этой коровы будет 11 + 19 = 30 долларов.
Общие потери от всех коров будут 2 + 7 + 11 + 30 = 50 долларов.
Динамическое программирование: два параметраДинамическое программирование: один параметр
✓ 1✗ 0—Войти и решать
Island Travels#89883

Фермер Джон отвез саоих коров на океан. Коровы живут на N (1<=N<=15) островах, которые расположены на решетке R x C (1 <= R, C <= 50). Остров - это максимальная связная группа квадратов на решетке, помеченная символами 'X', где два 'X' связны, только если они имеют общую сторону. Квадраты имеющие общий угол, не обязательно связны.
Беси опоздала, она прилетела с ФД на вертолете. Она может приземлиться на любом острове. Она хочет посетить все N островов хотя бы один раз.
Вокруг островов находится мелководье (обозначено буквой 'S'). Беси может плыть по нему в четырех направлениях (север, юг, запад, восток) для того, чтобы путешествовать между островами. Она также может путешествовать между островом и мелководьем и наоборот.
Определите минимальное расстояние, которое Беси должна проплыть, чтобы посетить все острова (гарантируется, что это возможно). Расстояние, которое проплывет Беси, равно количеству различных раз, когда Беси посетит клеточку 'S'.
PROBLEM NAME: island
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: R и C.
* Строки 2..R+1: Строка i+1 содержит C символов, определяющих i-ую строку решетки. Глубокая вода обозначена '.', острова 'X', мелководье 'S'.
Формат выходных данных
* Строка 1: Одно целое число, представляющее минимальное расстояние, которое должна проплыть Беси, чтобы посетить все острова.
Примечание
Бэси может проплыть от левого верхнего сотрова к среднему, проплыв 1 клеточку, а затем от среднего острова к правому нижнему, проплыв 2 клеточки - всего 3.
графыМинимальный каркасОбход в ширину
—Войти и решать
Partitioning the Farm#89873

Ферма Джона разделена на N x N квадратов пастбищ (2<=N<=15). Снаружи есть изгородь, но между пастбищами коровы могут переходить свободно.
ФД решил построить изгороди, чтобы отделить коров друг от друга. Каждая изгородь может быть горизонтальной или вертикальной через всю ферму, и изгороди не могут проходить через пастбища. По финансовым соображениям ФД может построить не более чем K изгородей (1 <= K <= 2N - 2).
ФД хочет построить изгороди так, чтобы минимизировать размер наибольшей из получившихся в результате групп коров (две коровы находятся в одной группе, если они могут посетить друг друга, не пересекая никакую изгородь).
По заданным количествам коров на пастбищах, вычислите размер наибольшей группы коров, если ФД построит изгороди оптимально.

PROBLEM NAME: partition
Формат входных данных
* Строка 1: Два целых числа, N and K
* Строки 2..1+N: Имеется N чисел на каждой строке, описывающих количества коров в каждом пастбище одной строки фермы. На каждом пастбище не менее 0 и не более 1000 коров.


Формат выходных данных
* Строка 1: Минимально возможный размер наибольшей группы коров.
Примечание
ФД должен построить изгороди между колонками 2 и 3 и между строками 2 и 3. В результате получится 4 группы по 4 коровы в каждой.

Бинарный поиск по ответужадные алгоритмыЗадачи на моделирование
—Войти и решать
Cow Baseball#89861

N (3 <= N <= 1000) коров Фермера Джона стоят в ряд, каждая в различной позиции на числовой прямой. Они бросают друг другу мяч по кругу в порядке подготовки к важной игре с коровами с соседней фермы.
ФД заметил, что группа из 3 коров (X,Y,Z) делает два успешных броска. Корова X бросает мяч вправо от себя корове Y, а затем корова Y бросает Мяч вправо от себя корове Z. ФД заметил также, что второй бросок получается на расстояние не менее чем первый бросок и не более чем в два раза превышает первый бросок. Посчитайте количество возможных троек коров, которые ФД мог наблюдать.
PROBLEM NAME: baseball
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Каждая строка содержит целую координату одной коровы (целое число в диапазоне 0..100,000,000).
Формат выходных данных
* Строка 1: Количество троек коров (X,Y,Z), где Y справа от X, а Z справа от Y и расстояние от Y до Z находится между XY и 2XY (включительно), где XY представляет расстояние от X до Y.
Примечание
Три возможных тройки: 1-3-7, 1-4-7, 1-4-10, 4-7-10.
Бинарный поиск в массивеИспользование сортировки
—Войти и решать
Unlocking Blocks (Silver)#89860

Коровы любят головоломки. Фермер Джон подарил Беси на день рождения новую головоломку. Она состоит из трех твердых объектов, каждый из которых состоит из склеенных вместе квадратиков размера 1 х 1. Каждый из этих объектов имеет «связную» форму в том смысле, что Вы можете перейти из одного квадратика в любой другой, двигаясь по квадратикам этого объекта в одном из четырех направлений: север, юг, запад, восток.
Объект может перемещаться последовательно скольжением на одну единицу в одном из четырех направлений: север, юг, запад, восток. Цель головоломки - переместить объекты так, чтобы они разделились – то есть, чтобы граничные квадратики отошли друг от друга. Ваша задача – по заданным трем объектам определить, можно их разделить, или нет. Конфигурация, которую разделить нельзя, называется заблокированной.

Замечание: программы, которые не делают ничего, кроме угадывания ответа, могут быть дисквалифицированы.
PROBLEM NAME: unlock
Формат входных данных
* Строка 1: Три разделенных одиночными пробелами целых числа: N1, N2, and N3, описывающих количество квадратов соответственно в фигурах 1, 2, и 3.
* Строки 2..1+N1: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
* Строки 2+N1..1+N1+N2: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 2. Все координаты в интервале 0..9.
* Lines 2+N1+N2..1+N1+N2+N3: Каждая из этих строк описывает (x,y) координату юго-западного угла одного квадрата объекта 1. Все координаты в интервале 0..9.
Формат выходных данных
* Строка 1: Минимальное количество шагов, которое необходимо выполнить, чтобы разделить три объекта или -1, если объекты не могут быть разделены.
Примечание
Если мы сдвинем объект 3 на 4 позиции на восток, а затем объект 2 на одну позицию на север и затем на 3 позиции на восток, то границы трех фигур разъединятся.

графыЗадачи на моделированиеОбход в ширину
—Войти и решать
Flowerpot#89839

Фермер Джон нуждается в Вашей помощи в организации поливки. Вам даны координаты N поливателей (1 <= N <= 100,000) на декартовой плоскости, где y представляет высоту поливателя. А x - его местоположение на прямой.

Каждая капля воды падает вертикально (по направлению к оси x) со скоростью 1 единица в секунду. Вы должны разместить клумбу (шириной W) с цветами так, чтобы разница во времени, когда первая капля упадет на клумбу и когда последняя капля упадет на клумбу была не менее некоторой величины D. Капля, которая попадает на границу клумбы, считается попавшей на клумбу.
Вам даны значения D, а также местоположения и высоты поливателей. Вычислите минимально возможную величину W.
PROBLEM NAME: fpot
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и D. (1 <= D <=1,000,000) * Строки 2..1+N: Строка i+1 содержит разделенные пробелом координаты (x,y) поливателя i, все величины в интервале 0...1,000,000.
Формат выходных данных
* Строка 1: Одно целое число, минимально-возможную ширину клумбы. Выведите -1, если невозможно построить клумбу, которая получала бы воду в течение не менее D единиц времени
Примечание
Клумба шириной 2 возможна, если разместить ее с x от 4 до 6. Тогда она будет получать капли с поливателей #1 и #3, втечение времени 10-3 = 7.
Бинарный поиск по ответуСортировка событий
—Войти и решать
Cows in a Skyscraper#89836

Коровы любят соревноваться в беге по лестницам небоскребов. А вниз потом едут на лифте.
Лифт имеет максимальную вместимость W (1 <= W <= 100,000,000) фунтов, а корова номер i весит Ci (1 <= Ci <= W) фунтов.
Помогите Бесси определить минимальное количество спусков лифта, чтобы переместить вниз все N (1 <= N <= 18) коров.
Сумма весов коров в каждом спуске не должна превышать W.
PROBLEM NAME: skyscraper
Формат входных данных
* Строка 1: N W разделенные одним пробелом
* Строки 2..1+N: Строка i+1 содержит целое число Ci, вес коровы i.
Формат выходных данных
* Строка 1: Минимальное целое, R, указывающее количество требуемых спусков.
* Строки 2..1+R: Каждая строка описывает множество коров, которые были в лифте во время каждого из R спусков. Каждая строка начинается с количества коров в текущем спуске, а затем номера коров через пробел.
Примечание
Мы можем поместить в лифт корову 3 и любую из оставшихся коров. Но все другие коровы не помещаются даже по две. В решении представленном выше, в первом спуске участвуют коровы 1 и 3, Во втором - корова 2, в третьем - корова 4. Существует несколько правильных решений для данного ввода.
битмаскиДинамика по подмножествамЗадача о рюкзаке
✓ 1✗ 2—Войти и решать
Video Game#89829

Беси играет в видеоигру. В этой игре 3 буквы 'A', 'B', 'C' - все управление. Эти буквы можно нажимать в любом порядке, однако возможны только N (1<=N<=20) различных комбинаций. Комбинация I представлена строкой Si с длиной от 1 до 15 символов, содержащей только символы 'A', 'B', 'C'.
Когда Беси нажимает комбинацию букв, соответствующую какой-то из введенных строк, она получает один балл. Комбинации могут перекрываться и даже заканчиваться одновременно. Например, если N=3 и три возможные комбинации есть "ABA", "CB" и "ABACB", а Беси набрала ABACB, она получит 3 балла. Беси может получать очко за каждую комбинацию более чем один раз.
Беси конечно хочет заработать как можно больше баллов. Если она нажмет ровно K (1<=K<=1000) клавиш, какое максимальное количество баллов она может заработать?
PROBLEM NAME: combos
Формат входных данных
* Строка 1:Два разделенных пробелом целых числа: N и K.
* Строки 2..N+1: Строка i+1 содержит только одну строку Si, представляющую комбинацию i.
Формат выходных данных
* Строка 1: Одно целое число, максимальное количество баллов, которое может набрать Беси


Примечание
Оптимальная последовательность клавиш есть ABACBCB, которая дает 4 балла 1 от ABA, 1 от ABACB, и 2 от CB.

Динамическое программированиеКонечные автоматыреализация
—Войти и решать
Overplanting (Bronze)#89816
Фермер Джон купил новую машину, которая умеет садить траву в прямоугольном регионе со сторонами, параллельными осям координат. К несчастью, эта машина однажды сломалась и посадила траву не в одном, а в N (1 <= N <= 10) различных регионах, некоторые из которых могут даже перекрываться.
По заданным прямоугольным регионам, засаженным травой, помогите ФД определить общую площадь, покрытую травой.
PROBLEM NAME: planting

Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит четыре разделенных одиночными пробелами целых числа x1 y1 x2 y2 указывающих прямоугольный регион с верхним - левым углом (x1,y1) и нижним – правым углом (x2,y2). Все координаты – целые числа в диапазоне -10,000...10,000.

Формат выходных данных
* Строка 1: Общая площадь, покрытая травой.
Сжатие координатСканирующая прямая
✓ 3✗ 8—Войти и решать
Running Away From the Barn#89811

Время дойки на ферме Джона, но коровы сбежали. Ферма Джона - это множество из N (1 <= N <= 200,000) пастбищ, пронумерованных от 1 до N, и связанных N - 1 двунаправленными дорожками. Амбар расположен в пастбище 1 и любое пастбище достижимо от амбара.
Коровы бегут в сторону "от амбара" и они пробегают расстояние не больше чем L. Для каждого пастбища ФД хочет знать, в скольки различных пастбищах могут оказаться коровы, сбежавшие с этого пастбища.
Замечание: используйте 64-битные целые (int64 в Pascal, long long в C/C++ и long в Java) для хранения расстояний.
PROBLEM NAME: runaway
Формат входных данных
* Строка 1: 2 целых числа, N и L (1 <= N <= 200,000, 1 <= L <= 10^18)
* Строки 2..N: i-ая строка содержит два целых числа pi и li. pi (1 <= pi < i) - первое пастбище на кратчайшем пути между пастбищем i и амбаром li (1 <= li <= 10^12) - длина этого пути
Формат выходных данных
* Строки 1..N: По одному числу в строке. Число в строке i - количество пастбищ, которые могут быть достигнуты из пастбища i, выбирая дороги, строго удаляясь от амбара (пастбище 1) с суммарной длиной не превышающей L.
Примечание
Корова из пастбища 1 может добежать до пастбищ 1, 2, 4. Корова из пастбища 2 может добежать до пастбищ 2, 3. Пастбища 3 и 4 - конечные, оттуда некуда бежать, можно только остаться в них.
Дерево отрезков, RSQ, RMQДеревья
✓ 0✗ 1—Войти и решать
First!#89809

Беси опять играет со строками. Она обнаружила, что изменяя порядок алфавита она може добиться, чтобы некоторая строка стала лексикографически раньше всех.
Например, среди строк
"omm", "moo", "mom", "ommnom"
она может сделать первой строку "mom", используя стандартный алфавит. и она может сделать первой строку "omm" используя алфавит "abcdefghijklonmpqrstuvwxyz". Однако Беси не знает как сделать первым слово "moo" или "ommnom"
Помогите Беси вычислить строки из ввода, которые можно сделать первыми изменив порядок букв в алфавите.
Чтобы определить, что строка X лексикографически раньше cтроки Y найдите индекс первого символа в котором они различаются j. Если такого индекса нет, тогда X лексикографически меньше чем Y, если X короче чем Y, иначе, X лексикографически раньше чем Y, если X[j] находится в алфавите раньше чем Y[j].

PROBLEM NAME: first
Формат входных данных
* Строка 1: целое N (1 <= N <= 30,000),количество строк, с которыми играет Беси
* Строки 2..1+N: Каждая строка содержит не пустую строку символов. Общее количество символов во всех строках не превысит 300,000. Все символы на вводе - маленькие латинские буквы от 'a' до 'z'. Во вводе нет повторяющихся строк.

Формат выходных данных
* Строка 1: одно число K, количество строк, которые могут быть лексикографически первыми.
* Строки 2..1+K: (1+i)-ая строка должна содержать i-ую строку, которая может быть лексикографически первой. Строки нужны выводить в том же порядке, в котором они следовали на вводе.
Примечание
Только "omm" и "mom" могут стать первыми.

БорграфыТопологическая сортировка
✓ 1✗ 1—Войти и решать
Moo Sick#89799

Problem 3: Moo Sick [Rob Seay]
Каждый знает, что коровы любят слушать музыку. Великий композитор Мууцарт однажды открыл, некоторые последовательности нот действуют на коров угнетающе. Поэтому их нужно избегать во всех композициях для коров.
Фермер Джон, не знакомый с этим фактом, решил проигрывать свою любимую песню через громкоговорители в амбаре. Ваша задача – определить все угнетающие последовательности нот в его песне, чтобы оценить, насколько она вредна для коров.
Песня, которую озвучивает ФД, представляет собой последовательность из N нот, каждая в диапазоне от 1 до 88. Угнетающая последовательность состоит из С (1<=C<=10) различных нот, также целых чисел от 1 до 88. Однако, если ноты транспонированы (увеличены или уменьшены на одну и ту же величину), или переупорядочены, то эта последовательность нот все равно остается угнетающей. Например, если «4 6 7» - угнетающая последовательность нот, то последовательности «3 5 6» (транспонирована на -1), «6 8 9» (транспонирована на +2), «6 4 7» (переупорядочена), «5 3 6» (транспонирована и переупорядочена) , также являются угнетающими.
Таким образом, угнетающей последовательностью нот являются C подряд идущих нот, удовлетворяющих вышеописанному критерию. Поэтому она однозначно определяется своим стартовым положением в песне. Определите стартовое положение всех угнетающих последовательностей.
PROBLEM NAME: moosick
Формат входных данных
* Строка 1: Одно целое число: N.
* Строки 2..1+N: N нот в песне ФД, по одной ноте на строке.
* Строка 2+N: Одно целое число: C.
* Строки 3+N..2+N+C: C нот определяющих угнетающую последовательность. Все транспозиции и переупорядочивания также угнетающие последовательности.


Формат выходных данных
* Строка 1: Количество, K, угнетающих последовательностей, которые есть в песне ФД. Заметим, что различные экземпляры угнетающих последовтельностей могут перекрываться друг с другом.
* Строки 2..1+K: Каждая строка указывает начальную позицию угнетающей последовательности (1 – первая нота в песне ФД, N - последняя). Эти начальные позиции должны указываться в порядке возрастания.
Примечание
Две угнетающих последовательности встретились в песне ФД и они перекрываются в одной ноте. Первая – 8,5,7 (транспонирована на 1 и переупорядочена), начинается с позиции 2, а вторая 7,9,10 (транспонирована на 3) , начинается с позиции 4.

Использование сортировкиПоиск подстроки в строке
—Войти и решать
Поделиться
Класснуть