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

Stamp Painting#90017

У Беси есть полоса холста длиной \(N\) единиц(\(1 \leq N \leq 10^6\)), которую она собирается раскрасить. У неё есть \(M\) резиновых штампов различных цветов (\(1 \leq M \leq 10^6\)), каждый штамп имеет \(K\) в ширину (\(1 \leq K \leq 10^6\)). Она хочет точно узнать, сколько различных рисунков она может создать, используя свои штампы в некотором порядке.

Чтобы использовать штамп, он должен занять ровно \(K\) соседних единиц холста. Штамп не может выходить за концы холста, и не может покрывать часть единицы. Однажды размещённый, штамп закрашивает \(K\) покрытых единиц своим цветом. Любой штамп может быть использован множество раз, один раз или даже не использован ни разу. Но к моменту завершения работы Беси, каждая единица холста должна быть закрашена как минимум один раз.

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

Как минимум в 75% тестов, \(N,K \leq 10^3\).

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

Первая строка ввода содержит три целых числа \(N\), \(M\), \(K\). Гарантируется, что \(K \leq N\).

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

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

дп

—Войти и решать

Balance Beam#89994

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

Количество заработанных денег зависит от того, где она спрыгнет с бревна. Бревно имеет позиции, помеченные \(0, 1, \ldots, N+1\) слева направо. Если Беси достигнет точки \(0\) или \(N+1\), она упадёт с бревна и не получит деньги.

Если Беси находится в позиции \(k\), она может сделать что-то из следующего:

1. Бросить монету. Если она увидит хвост("орёл"), она идёт в позицию \(k-1\), а если она увидит голову("решка"), она идёт в позицию \(k + 1\) (т.е с вероятностью \(\frac{1}{2}\) в обоих случаях).

2. Спрыгнуть с бревна и получить плату \(f(k)\) \((0 \leq f(k) \leq 10^9)\).

Беси поняла, что она не может гарантировать конкретный доход, поскольку её движение управляется случайным выбрасыванием монеты. Однако, основываясь на позиции, где она начинает, она хочет определить какой будет её ожидаемая выплата, если она сделает оптимальную последовательность решений ("оптимальную" означает, что решения приведут к наибольшей возможной ожидаемой выплате.) Например, её стратегия заработать выплату \(10\) с вероятностью \(1/2\), \(8\) с вероятностью \(1/4\), или \(0\) с вероятностью \(1/4\) приведёт к тому что её ожидаемая выплата будет взвешенной средней величиной \(10(1/2) + 8(1/4) + 0(1/4) = 7\).

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

Первая строка ввода содержит \(N\) (\(2 \leq N \leq 10^5\)). Каждая из оставшихся \(N\) строк содержит \(f(1) \ldots f(N)\).

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

Выведите \(N\) строк. В строке \(i\), выведите \(10^5\) умножить на ожидаемую оплату если Беси стартует в позиции \(i\) и будет играть оптимально, округлённую до ближайшего целого числа.

дп

—Войти и решать

Palindromic Paths (Bronze)#89954

Ферма Джона представлена решёткой из \(N \times N\) полей(\(2 \le N \le 18\)), каждое из которых помечено буквой алфавита. Например,


ABCD

BXZX

CDXB

WCBA

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

Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

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

Первая строка ввода содержит \(N\), а последующие \(N\) строк содержат \(N\) описание поля. Каждая строка содержит по \(N\) символов в диапазоне A..Z.

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

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

дп

—Войти и решать

Fair Photography#89948

N (1 <= N <= 100,000) коров Фермера Джона стоят в различных позициях вдоль длинной изгороди. I-ая корова находится на позиции x_i (целое число в интервале 0...1,000,000,000) и имеет породу b_i (целое число в интервале 1..8). Никакие две коровы не занимают одну и ту же позицию.
ФД хочет сделать фотографию непрерывного интервала коров, но так чтобы все породы коровы были представлены одинаковым количеством коров. Например, фото из 27 коров породы 1 и 27 коров породы 3 – подходит, фото из 27 коров породы 1 и 27 коров породы 3 – подходит и 27 коров породы 4 тоже подходит, а 9 породы 1 и 10 породы 3 не подходит. ФД также хочет чтобs по крайнеq мере K (K>=2) пород из 8 имеющихся были представлены на фото. Помогите ФД определить фот максимального размера, которое удовлетворяет требованиям ФД. Размер фото – это разница между максимальной и минимальной позициями коров на фото.
Если не существует фото, удовлетворяющего всем ограничениям, выведите -1.
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: N и K разделённые одним пробелом
* Строки 2..N+1: Каждая строка содержит описание одной коровы двумя целыми числами, разделёнными одним пробелом: x_i и ID-породы

Примечание
ID пород: 1 2 3 - 1 1 2 3 1 - ... - 1 Местоположения: 1 2 3 4 5 6 7 8 9 10 ... 99 100
Формат вывода:
* Строка 1: Одно целое число, указывающее максимальный размер подходящего фото. Если таких фото нет, выведите -1.

Примечание
В интервале от x = 2 до x = 8 имеется по 2 коровы каждой из пород 1, 2,3. В интервале от 9 до 100 есть 2 коровы породы 1, но поскольку K=2, этот интервал не подходит.

дп

—Войти и решать

Secret Code#89924

Problem 3: Secret Code [Brian Dean and Lewin Gan]
У Фермера Джона есть секретное сообщение, которое он хочет зашифровать от своих коров. Сообщение – это строка, которая содержит не менее двух символов A..Z.
Чтобы зашифровать его, ФД применяет последовательность «операций» к нему. Операция, применённая к строке S, сначала сокращает S, удалив из неё некоторое количество символов сначала (но не все) или некоторое количество символов с конца (но не все), после чего добавляет исходную строку в начало или конец. Например, одна операция, применённая к строке ABC может дать 8 возможных строк:
AABC ABABC BCABC CABC ABCA ABCAB ABCBC ABCC
По заданной зашифрованной строке подсчитайте количество возможных способов создать такую строку применив одну или более операций к некоторой исходной строке. Операции считаются различными, даже если результат их выполнения одна и та же строка. Например, имеются 4 различных способа получить строку AAA из строки AA, соответствующих 4 возможным операциям, описанным выше.
Выведите ответ по модулю 2014.
PROBLEM NAME: scode
Формат входных данных
* Строка 1: строка с длиной не более 100.
Формат выходных данных
* Line 1: Количество различных способов, которыми ФД может получить эту строку, применяя одну или более последовательных операций к строке с длиной не менее 2, выведенное по модулю 2014. Если не существует таких способов, выводите 0.
Примечание
Имеется 8 способов получить строку ABABA: 1. Начиная с ABA -> AB+ABA 2. Начиная с ABA -> ABA+BA 3. Начиная с AB -> AB+A -> AB+ABA 4. Начиная с AB -> AB+A -> ABA+AB 5. Начиная с BA -> A+BA -> AB+ABA 6. Начиная с BA -> A+BA -> ABA+AB 7. Начиная с ABAB -> ABAB+A 8. Начиная с BABA -> A+BABA

дп

—Войти и решать

Secret Code#89918

Problem 3: Secret Code [Brian Dean and Lewin Gan]
У Фермера Джона есть секретное сообщение, которое он хочет зашифровать от своих коров. Сообщение – это строка, которая содержит не менее двух символов A..Z.
Чтобы зашифровать его, ФД применяет последовательность «операций» к нему. Операция, применённая к строке S, сначала сокращает S, удалив её первый символ или её последний символ, после чего добавляет исходную строку в начало или конец. Например, одна операция, применённая к строке ABCD может дать 4 возможных строки:
BCDABCD ABCABCD ABCDABC ABCDBCD
По заданной зашифрованной строке подсчитайте количество возможных способов создать такую строку применив одну или более операций к некоторой исходной строке. Операции считаются различными, даже если результат их выполнения одна и та же строка. Например, имеются 4 различных способа получить строку AAA из строки AA, соответствующих 4 возможным операциям, описанным выше.
PROBLEM NAME: scode
Формат входных данных
* Строка 1: строка с длиной не более 100.
Формат выходных данных
* Line 1: Количество различных способов, которыми ФД может получить эту строку, применяя одну или более последовательных операций к строке с длиной не менее 2. Если не существует таких способов, выводите 0.
Примечание
Имеется 6 способов получить строку ABABA: 1. Начиная с ABA -> AB+ABA 2. Начиная с ABA -> ABA+BA 3. Начиная с AB -> AB+A -> AB+ABA 4. Начиная с AB -> AB+A -> ABA+AB 5. Начиная с BA -> A+BA -> AB+ABA 6. Начиная с BA -> A+BA -> ABA+AB

дп

—Войти и решать

Figure Eight#89910

Коровы ФД недавно нашли огромный кусок мрамора, в котором есть некоторое количество несовершенств. Для их описания мы представим кусок мрамора квадратной решеткой N*N (5<=N<=300), где символ '*' указывает несовершенство, а символ '.' указывает совершенный фрагмент мрамора.
Коровы хотят выгравировать число 8 на этом куске мрамора. И им нужна помощь в оптимальном расположении гравировки, которая должна удовлетворять следующим условиям (указывающим корректность рисунка цифры 8):
* Цифра 8 состоит из двух прямоугольников, верхнего и нижнего. * Внутри каждого прямоугольника должна быть хотя бы она ячейка. * Нижняя сторона верхнего прямоугольника - подмножество верхней стороны нижнего прямоугольника * Цифру 8 можно гравировать только на совершенных фрагментах мрамора.
Эстетический счет рисунка цифры 8 равен произведению областей, окруженных обоими прямоугольниками. Коровы хотят максимизировать это число.
Пусть, например, дан такой кусок мрамора:
............... ............... ...*******..... .*....*.......* .*......*....*. ....*.......... ...*...****.... ............... ..**.*..*..*... ...*...**.*.... *..*...*....... ............... .....*..*...... .........*..... ...............
Оптимальная гравировка цифры 8 такова:
..88888888888.. ..8.........8.. ..8*******..8.. .*8...*.....8.* .*8.....*...8*. ..8.*.......8.. ..8*...****.8.. .88888888888888 .8**.*..*..*..8 .8.*...**.*...8 *8.*...*......8 .8............8 .8...*..*.....8 .8.......*....8 .88888888888888
Верхний прямоугольник имеет область 6x9=54, а нижний 12x6=72. Итого эстетический счет 54*72 = 3888.

PROBLEM NAME: eight
Формат входных данных
* Строка 1: Одно целое число N, указывающее длину стороны куска мрамора
* Строки 2..N+1: Каждая строка описывает строку куска мрамора, и содержит N символов, каждый из которых либо '*' (несовершенство) или '.' (безупречная секция).
Формат выходных данных
* Строка 1: Максимальный эстетический счет, который может быть получен не используя для гравировки никакие несовершенные квадраты мрамора. Если невозможно выгравировать 8 при таких ограничениях, выведите -1.

дп

—Войти и решать

Haywire#89908

N коров (4 <= N <= 12, N четное), построили примитивную систему для проводной коммуникации пар дружественных коров
Каждая корова имеет ровно 3 друзей в амбаре и коровы должны занять один ряд в амбаре из N стойл. Провод длины L требуется, чтобы соединить друзей в стойлах на расстоянии L. Например, если друзья находятся в стойлах 4 и 7, то требуется провод длины 3, чтобы их соединить.
Каждая пара коров должна быть соединена отдельным проводом. Определите минимальную длину провода, требуемую для организации такой сети наилучшим образом.
PROBLEM NAME: haywire
Формат входных данных
* Строка 1: Цело число N. Коровы пронумерованы 1..N.
* Строки 2..1+N: Каждая строка содержит три разделенных пробелом целых числа в диапазоне от 1 до N. Строка i+1 содержит числовые идентификаторы трех друзей коровы i. Если корова i дружит с коровой j, то и корова j дружит с коровой i.
Формат выходных данных
* Строка 1: Минимальная суммарная длина провода, чтобы соединить все пары дружественных коров.
Примечание
Лучшее упорядочивание коров есть 6, 5, 1, 4, 2, 3, и оно требует только 17 единиц длины провода.

битмаски дп Перебор

—Войти и решать

No Change#89902

Фермер Джон на рынке. У него в кармане K монет (1<=K<=16), каждая в диапазоне 1..100,000,000. ФД хочет сделать серию из N покупок (1 <= N <= 100,000), причём i-ая покупка имеет стоимость c(i) (1 <= c(i) <= 10,000). Во время выполнения последовательности покупок, ФД может периодически останавливаться и платить за все покупки выполненные с момента последней оплаты (конечно монета должна быть достаточно большой для этого). Покупки всегда делаются одной монетой, но у продавцов нет сдачи. Поэтому, если монета больше, чем количество денег, которое он должен заплатить, то разница теряется.
Определите максимальное количество денег, с которым ФД может закончить покупку всех N покупок в заданной последовательности. Выведите -1, если ФД не может сделать все покупки.
PROBLEM NAME: nochange
Формат входных данных
* Строка 1: Два целых числа, K и N.
* Строки 2..1+K: Каждая строка содержит количество денег на соответствующей монете ФД
* Строки 2+K..1+N+K: Эти N строк содержат стоимости покупок ФД

Формат выходных данных
* Строка 1: Максимальное количество денег, которое окажется у фермера в окнце покупок, или -1 если ФД не сможет выполнить все покупки.
Примечание
ФД потратит монету с ценностью 10 на первые две покупки, и затем монету с ценностью 15 на оставшиеся покупки. У него останется монета с ценностью12.

дп

—Войти и решать

Route Design#89874

Беси открыла агентство путешествий вдоль реки Амазонка. Имеется несколько туристических мест на обоих сторонах реки, для каждого некоторое целое число задает насколько это место интересно туристам.
Туристические места соединены маршрутами через реку. Иными словами, нет маршрутов, соединяющих туристические места по одной стороне реки.
Беси хочет найти такую последовательность посещения туристических мест чтобы максимизировать сумму значений ассоциированных с каждым посещенным местом и чтобы никакие два маршрута в этой последовательности не пересекались.
Два маршрута (a <-> x) и (b <-> y) пересекаются тогда и только тогда, когда (a < b и y < x) или ((b < a и x < y) или (a = b and x = y).
Помогите Беси найти такой маршрут. Беси может начинать и заканчивать маршрут в любом месте и на любой стороне реки.

PROBLEM NAME: route
Формат входных данных
* Строка 1: Три разделенных пробелом целых числа N (1 <= N <= 40,000), M (1 <=M <= 40,000), и R (0 <= R <= 100,000) указывающих соответственно количество мест на левой стороне реки, количество мест на правой стороне реки и количество маршрутов.
* Строки 2..N+1: (i+1)-ая строка содержит одно целое число, L_i (0 <= L_i <= 40,000), указывающее число i-го места на левой стороне реки
* Строки N+2..N+M+1: (i+N+1)-ая строка содержит одно целое число, R_i (0 <= R_i <= 40,000), указывающее число i-го места на правой стороне реки
* Строки N+M+2..N+M+R+1: Каждая строка содержит два целых числа разделенных пробелом I (1 <= I <= N) и J (1 <= J <= M) указывающих двунаправленный маршрут между местом I на левой стороне реки и местом J на правой стороне реки.

Формат выходных данных
* Строка 1: Одно целое число, указывающее максимальную сумму значений включенных в тур.

Примечание
Оптимальный тур начинается в месте 1 на левой стороне, затем в место 1 на правой стороне и затем сайт 3 слева. Соответсвующие значения 1 2 5 дают сумму 8.

дп

—Войти и решать

Balanced Cow Breeds#89848

Фермер Джон обычно помечает своих коров круглой меткой, но сейчас его пометочная машина сломалась, и он решил помечать коров отметкой в форме скобок. У него есть две породы коров Holsteins и Guernseys. Каждую породу он помечает меткой в виде скобки. В зависимости от того, В какую сторону корова смотрит, скобка может выглядеть как левая или как правая.
N коров фермера Джона стоят в ряд, каждая смотрит в произвольном направлении, поэтому мы получаем строку скобок длиной N. Глядя на нее, ФД обнаружил, что если смотреть слева направо, то только для коров Holsteins (в порядке, в котором они появились в последовательности), Получится сбалансированная последовательность скобок, однако то же самое верно и для Guernseys! Чтобы выяснить, насколько это редкое событие, Помогите ФД вычислить количество различных способов, которыми можно назначить породы этим N коровам, чтобы выполнялось такое свойство.
Есть несколько способов определить сбалансированную строку. Один из них такой: Строка должна иметь одинаковое количество левых и правых скобок. И для любого префикса строки количество левых скобок должно быть не меньше, чем количество правых скобок.
Например, следующие последовательности скобок сбалансированные:
() (()) ()(()())
А эти - нет.
)( ())( ((())))
PROBLEM NAME: bbreeds
Формат входных данных
* Строка 1: Строка скобок длины N (1 <= N <= 1000).
Формат выходных данных
* Строка 1: Одно целое число - количество способов назначить породы так, чтобы Holsteins формировали сбалансированную последовательность скобок и аналогично Guernseys. Поскольку ответ может быть очень большим, выведите остаток от его деления на 2012. Корректным считается использование только одного типа породы.
Примечание Вот корректные назначения пород (()) HHHH
(()) GGGG
(()) HGGH
(()) GHHG
(()) HGHG
(()) GHGH

дп

—Войти и решать

Balanced Cow Breeds#89845

дп

—Войти и решать

Bale Share#89830

Фермер Джон только что получил N (1 <= N <= 20) упаковок сена, упаковка I имеет размер S_i (1 <= S_i <= 100). Он хочет разделить упаковки между тремя амбарами как можно более справедливо.
Под справедливостью он понимает минимальную разницу между максимальными значениями. То есть, если B₁, B₂, B₃ - суммарные размеры всех упаковок, в амбарах 1 2 и 3 соответственно (где B₁>=B₂>=B₃), то ФД хочет чтобы B₁ был самым минимальным из всех возможных.
Например пусть есть 8 упаковок с размерами:
2 4 5 8 9 14 15 20
Справедливое решение есть:
Амбар 1: 2 9 15 B₁ = 26 Амбар 2: 4 8 14 B₂ = 26 Амбар 3: 5 20 B₃ = 25
Пожалуйста, помогите ФД определить B₁ справедливого распределения.
PROBLEM NAME: baleshare
Формат входных данных
* Строка 1: Количество упаковок, N.
* Строки 2..1+N: Строка i+1 содержит S_i, размер i-ой упаковки.
Формат выходных данных
* Строка 1: Выведите значение B₁ справедливого распределения упаковок

дп

—Войти и решать

Cow Run#89828

Фермер Джон и Беси придумали новую игру для коров. Коровы бегут по круглой дорожке длиной M (2 <= M <= 1 000 000 000), начиная с с одной и той же позиции. Игра проходит в N (1<=N<14) раундов с использованием колоды из 8N карт, на каждой из которых написано число X_i (0 <= X_i < M).
На каждом раунде ФД перемещает верхние 8 карт в отдельную кучку и выбирает или верхние 4 или нижние 4 для Беси. Затем Беси из них выбирает или верхние 2 или нижние 2 карты. После этого ФД называет число X_top, которое написано на верхней карте и коровы бегут расстояние R * X_top, где R - это общее расстояние, которое коровы пробежали до сих пор, затем Беси называет число X_bottom, которое было написано на нижней карте и коровы бегут расстояние X_bottom.
ФД беспокоиться, чтобы коровы не сильно устали и могли вернуться домой. Если коровы убегут больше чем на расстояние K (0<=K<=floor(M/2)) от стартовой позиции, то они не смогут вернуться домой.
Гарантируется, что если ФД играет корректно, он всегда может обеспечить чтобы коровы вернулись домой, вне зависимости от ходов, которые делает Беси. Для каждого раунда Ваша задача - определить, какую половину карт должен выбирать ФД, чтобы вне зависимости от ходов Беси, коровы всегда могли вернуться домой. Беси делает ход, описанный на вводе, а Вы должны продолжить в следующий раунд. Заметим, что несмотря на то, что ходы Беси заданы на входе, Вы должны определить ходы для ФД, которые будут работать вне зависимости от выбора Беси и эти ходы были эффективны, как если бы ФД не знал ходы Беси.
PROBLEM NAME: cowrun
Формат входных данных
* Строка 1: три разделенных пробелами целых числа N, M, K
* Строка 2: N символов. Если i-ый символ есть 'T', значит Беси выберет верхние две карты в этом раунде, иначе если i-ый символ есть 'B', это значит что Беси выберет две нижние карты на этом раунде.
* Строки 3..2+N: каждая строка содержит 8 целых чисел, представляющих 8 карт, которые будут использованы в этом раунде, сверху вниз.
Формат выходных данных
* Строка 1: Строка из N символов, где i-ый символ есть 'T' если ФД должен выбрать верхние 4 карты и 'B', если ФД должен выбрать нижние 4 карты в i-ом раунде. Если существует несколько способов, чтобы коровы вернулись домой, выберите лексикографически наименьший (строка, ему соответствующая должна быть наименьшей в алфавитном порядке).
Примечание
Коровы должны закончить точно в том месте, где начали, чтобы они могли вернуться домой. Заметим, что ФД не принимает во внимание ходы Беси, иначе он мог выбрать нижнюю половину оба раза.

дп

—Войти и решать

Umbrellas for Cows#89795

Сегодня - дождь.! N (1 <= N <= 5,000) коров Фермера Джона, пронумерованные от 1 до N не хотят мокнуть. Но они стоят в стойлах без крыш. Сойла расположены на прямой, с X_координатой от 1 до M (1 <= M <= 100,000). Корова i расположена в стойле с координатой X_i (1<=X_i<=M) . Никакие две коровы не стоят в одном стойле.
Для того, чтобы защитить коров от дождя, ФД хочет купить им зонтики. Один зонтик, который расположен от координаты X_i до координаты X_j (X_i<=X_j) имеет ширину (X_j-X_i+1). C_W (1 <= C_W <= 1,000,000) - цена зонтика шириной W. Необязательно, что более широкий зонтик стоит дороже более узкого.
Помогите ФД определить минимальную сумму, которую ФД должен потратить на покупку зонтиков, чтобы защитить от дождя всех своих коров.
PROBLEM NAME: umbrella
Формат входных данных
* Строка 1: Два разделенных пробелами целых числа: N M.
* Строки 2..N+1: Строка i+1 содержит одно целое число: X_i.
* Строки N+2..N+M+1: Строка N+j+1 содержит одно целое число: C_j.
Формат выходных данных
* Строка 1: Одно целое число - минимальная стоимость покупки зонтиков для покрытия всех коров.

Примечание
При покупке зонтиков с размерами 4, 1 и 2, можно покрыть всех коров и это будет стоить 9 (4+2+3=9)
UUUUUUUUUU U UUUU C C C C C C |--|--|--|--|--|--|--|--|--|--|--| 1 2 3 4 5 6 7 8 9 10 11 12
C представляет корову, U представляет часть зонтика.

дп

—Войти и решать

Туристический маршрут#60176

Школьники приехали на экскурсию в новый город и решили осмотреть его достопримечательности. Представим город в виде прямоугольной сетки \(n \times m\), в некоторых клетках которой могут находиться достопримечательности.

Друзья начинают свой путь в клетке \((1, 1)\), они хотят дойти до клетки \((n,m)\), а затем вернуться обратно. В городе есть \(k\) достопримечательностей, они расположены в клетках \((x_1, y_1), \ldots, (x_k, y_k)\), друзья обязательно хотят посетить их все.

За одну минуту можно перейти из клетки \((a, b)\) в клетку \((c, d)\), если они являются соседними по стороне, то есть выполняется равенство \(|a - c| + |b - d| = 1\). Легко видеть, что на маршрут необходимо потратить хотя бы \(2n+2m-4\) минут, будем рассматривать только такие маршруты.

Будем называть маршрут интересным, если выполняются следующие условия:

для того, чтобы пройти маршрут, друзья потратят ровно \(2n+2m-4\) минут;
маршрут проходит через каждую клетку не более одного раза.
маршрут проходит через все клетки, которые содержат достопримечательности.

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

В первой строке указаны числа \(n\), \(m\) и \(k\) (\(3 \le n,m \le 10^6\), \(0 \le k \le 2\,000\)).

В последующих \(k\) строках указано по паре чисел \(x_i\), \(y_i\) (\(1 \le x_i \le n\), \(1 \le y_i \le m\)), гарантируется, что все пары \((x_i, y_i)\) различны. То есть для любой пары индексов \((i, j)\) (\(1 \le i < j \le n\)) верно одно из двух: \(x_i \neq x_j\) или \(y_i \neq y_j\).

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

Примечание

Ниже изображены все интересные маршруты для первого теста.

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

графы дп

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

Тройка#60135

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

<<Единый>> (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 минут>>.

дп Жадный алгоритм

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

Фонари#56311

Улицу Подводный канал освещают \(n\) фонарей, пронумерованных вдоль улицы от 1 до \(n\). Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов \(\frac{n(n+1)}{2}\). Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны.

С фонарями регулярно происходят события одного из двух типов:

в каком-то сегменте из-за скачков напряжения все лампочки одновременно перегорают;

Архиэнерго выбирает некоторый сегмент и посылает ремонтников, чтобы заменить на нем все перегоревшие лампочки на исправные.

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

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

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

В каждой из последующих \(q\) строк содержатся описания событий в виде трёх чисел \(l_i, r_i\) и \(c_i\), которые означают, что после этого события все лампочки в фонарях с номерами \(l_i, l_i+1, \ldots, r_i\):

перегорают при \(c_i = 0\),
становятся исправными при \(c_i = 1\).

В описаниях всех событий \(1 \le l_i \le r_i \le n\), а \(c_i\) принимает значение \(0\) или \(1\).

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

Дерево отрезков, RSQ, RMQ дп

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

Скобки(3)#55157

Определим правильные скобочные выражения так:

Пустое выражение - правильное.
Если выражение S правильное, то (S) и [S] также правильные.
Если выражения A и B правильные, то и выражение AB - правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.

Ограничения: исходная последовательность содержит не более 100 скобок.

Входные данные
В первой строке находятся символы (, ), [ и ] без пробелов.

Выходные данные
Выводится искомая последовательность скобок без пробелов.

Примеры

№	Входные данные	Выходные данные
1	([(]	()[()]
2	(	()

Динамическое программирование по подстрокам Динамическое программирование: один параметр дп

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

Палиндромы#55145

Непустая строка, содержащая некоторое слово, называется палиндромом, если это слово одинаково читается как слева направо, так и справа налево. Пусть дана строка, в которой записано слово S, состоящее из N прописных букв латинского алфавита. Вычёркиванием из этого слова некоторого набора символов можно получить строку, которая будет палиндромом. Требуется найти количество способов вычёркивания из данного слова некоторого (возможно, пустого) набора символов таких, что полученная в результате строка являлась палиндромом. Способы, различающиеся порядком вычёркивания символов, считаются одинаковыми.

Ограничения: 1 <= N <= 60.

Входные данные
В первой строке записано слово S.

Выходные данные
Вывести одно целое число - количество способов вычёркивания.

Динамическое программирование по подстрокам дп

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