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

Why Did the Cow Cross the Road II#90424

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

Кк известно, коровы - существа привычки, и они пересекают дорогу одним и тем же способом каждый день. Каждая корова входит на поле в точке, отличной от той, в которой она выходит с поля и все эти точки отличаются друг от друга. У ФД ровно 26 коров, которые лениво названы от A до Z и поэтому на поле имеется ровно 52 точки. ФД записал эти точки по часовой стрелке, записав букву - имя коровы, для которой эта точка. В результате ФД получил строку из 52 символов, в которой каждая буква алфавита встречается ровно дважды. Он не записывал, какая точка для входа, какая - для выхода.

Разглядывая свою карту точек, ФД заинтересовался, сколько раз могут пересечься пути различных пар коров. Он называет пару коров \((a,b)\) "пересекающейся" парой, если путь коровы \(a\) от входа к выходу должен пересечь путь коровы '\(b\)' от входа к выходу. Помогите ФД посчитать общее количество пересекающихся пар.

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

Ввод состоит из одной строки, содержащей 52 больших латинских символа. Каждая буква алфавита появится ровно 2 раза.

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

Общее количество пересекающихся пар.

Комбинаторика

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

Hoof, Paper, Scissors#90392

Возможно Вы слышали об игре "Камень, Бумага, Ножницы". Коровы любят играть в похожую игру "Копыто, Бумага, Ножницы"

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

Фермер Джон наблюдает как две коровы играют серию из \(N\) игр (\(1 \leq N \leq 100\)). К несчастью, ФД видя три различных жеста, не понимает, какой из них означает копыто, какой бумагу, какой ножницы.

ФД назначил жестам цифры 1 2 3. Помогите ФД определить максимально возможное количество игр, в которых выиграет первая корова, при подходящем назначении цифр жестам.

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

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

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

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

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

Комбинаторика

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

Exercise#90114

Фермер Джон проводит утреннюю зарядку с коровами.

\(N\) коров (\(1\le N\le 10^4\)) стоят в ряд. \(i\)-ая корова слева имеет метку \(i\) для каждого \(1\le i\le N\). ФД говорит коровам повторять следующие действия до тех пор, пока коровы не вернуться к тому же порядку, с которого начинали:

По заданной перестановке \(A\) длины \(N\), коровы изменяют их порядок так, что \(i\)-ая корова слева до изменения становится \(A_i\) коровой слева после изменения

Например, если \(A=(1,2,3,4,5)\) тогда коровы выполнят один шаг. Если \(A=(2,3,1,5,4)\), тогда коровы выполнят 6 шагов. Порядок коров слева направо после каждого из шагов будет таким:

0 шаг: \((1,2,3,4,5)\)
1 шаг: \((3,1,2,5,4)\)
2 шаг: \((2,3,1,4,5)\)
3 шаг: \((1,2,3,5,4)\)
4 шаг: \((3,1,2,4,5)\)
5 шаг: \((2,3,1,5,4)\)
6 шаг: \((1,2,3,4,5)\)

Определите сумму всех положительных целых чисел \(K\) таких, что существует перестановка длины \(N\), которая требует от коров выполнить ровно \(K\) шагов.

Поскольку это число может быть очень большим, выведите ответ по модулю \(M\) (\(10^8\le M\le 10^9+7\), \(M\) - простое).

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

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

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

Одно целое число

дп Комбинаторика теория чисел

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

Cow Poetry#90063

Беси хочет написать собственную поэму.

Беси знает \(N\) (\(1 \leq N \leq 5000\)) слов и хочет организовать их в поэму. Она определила длину в слогах каждого слова, кроме того она распределила их в "классы рифм". Каждое слово рифмуется только с другими словами из этого же класса рифм.

Каждая из поэм Беси включает \(M\) строк (\(1 \leq M \leq 10^5\)) и каждая строка должна состоять из \(K\) (\(1 \leq K \leq 5000\)) слогов. Более того, поэм Беси должна соответствовать специфической схеме рифм.

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

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

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

Каждая из следующих \(N\) строк содержит два числа \(s_i\) (\(1 \leq s_i \leq K\)) и \(c_i\) (\(1 \leq c_i \leq N\)). Они обозначают, что Беси знает слово с длиной (в слогах) \(s_i\) и класса рифмы \(c_i\).

Последние \(M\) строк описывают желаемую схему рифмы Беси и каждая содержит одну большую букву \(e_i\). Все строки соответствующие \(e_i\) должны заканчиваться словами одного и того же кдасса рифм. Строки с различными значениями \(e_i\) не обязательно заканчиваются словами с различными классами рифм.

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

Выведите количество поэм, которые может Беси написать, удовлетворяющих все заданным ограничениям. Поскольку это число может быть очень велико, выводите ответ по модулю 1,000,000,007.

дп жадные алгоритмы Комбинаторика

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

Cow Gymnasts#90006

Соскучившись от жизни на ферме, коровы ушли в бродячий цирк. И с ними готовится новое шоу.

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

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

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

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

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

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

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

Вывод формулы Комбинаторика теория чисел

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

Odometer#89951

Коровы Фермера Джона путешествуют. Одометр в их автомобиле показывает целое значение преодолённого расстояния в милях, начиная с X (100 <= X <= 10^18) миль в начале путешествия и Y (X <= Y <= 10^18) миль в конце путешествия. Когда одометр показывает «интересное» число, коровы мычат. Число является интересным, если у него все цифры одинаковые, кроме одной (ведущие нули не рассматриваются в качестве цифр). Например, числа 33323 и 110 – «интересные», а числа 9779 и 55555 – нет.
Помогите ФД посчитать, сколько раз коровы промычат во время путешествия,
Help FJ count how many times the cows will moo during the trip.
PROBLEM NAME: odometer
Формат ввода:
* Строка 1: Первая строка содержит два целых числа, X и Y, разделённых пробелом.
Примечание
В начале путешествия на одометре 110, а в конце – 133.
Формат вывода:
* Строка 1: Одно целое число – сколько раз промычат коровы во время путешествия.

Примечание Коровы промычат, когда на одометре будут следующие числа: 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131, 133.

Комбинаторика

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

Farmer John has no Large Brown Cow#89898

Фермер Джон любит коллекционировать как можно больше типов коров, кроме нескольких типов, которые перечислены в специальном списке из N строк (1 <= N <= 100). Этот список выглядит так:
Farmer John has no large brown noisy cow. Farmer John has no small white silent cow. Farmer John has no large spotted noisy cow.
Каждый элемент списка описывает недопустимый тип в виде короткого списка прилагательных, и содержит одно и то же количество прилагательных (3, в данном примере). Количество прилагательных в строке содержится в диапазоне от 2 до 30.
У ФД имеется корова подходящая под каждую возможную комбинацию прилагательных, не имеющуюся в этом списке. В данном примере первое прилагательное имеет два значения (large, small); второе – три (brown, white, spotted), а третье – два (noisy, silent). Это даёт 2*3*2 = 12 различных комбинаций и у ФД есть корова для каждой из них, кроме тех, которые указаны в списке. Например large, white, noisy – одна из его 9 коров. У ФД не более 1,000,000,000 коров.
Если ФД упорядочит описания своих коров по алфавиту – какая корова будет K-ая по списку?
Частичное оценивание: Из 10 тестов на задачу в тестах 1..4 будет не более двух прилагательных в строке списка. В тестах 1..6 каждое из прилагательных будет иметь ровно 2 различных значения (во всех других тестах каждое прилагательное может иметь от 1 до N различных значений).
PROBLEM NAME: nocow
Формат входных данных
* Строка 1: Два целых числа, N и K.
* Строки 2..1+N: Каждая строка содержит предложение вида "Farmer John has no large spotted noisy cow.". Каждое прилагательное в этом списке – строка не более 10 маленьких латинских букв Конец предложения определяется символами "cow."
Формат выходных данных
* Строка 1: Описание K-ой коровы на ферме.
Примечание
Вот список имеющихся коров в алфавитном порядке
large brown silent large spotted silent large white noisy large white silent small brown noisy small brown silent small spotted noisy small spotted silent small white noisy
7-ая корова в этом списке - "small spotted noisy".

Комбинаторика

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

Клад#55691

Однажды Юрик оказался в лесу у костра, где собрались \(n\) человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от \(1\) до \(n\). Обозначим как \(d_i\) количество людей, сидящих у костра, с которыми знаком \(i\)-й человек. Неожиданно оказалось, что два человека с номерами \(i\) и \(j\) (\(i \ne j\)) знакомы друг с другом тогда и только тогда, когда \(d_i = d_j\).

Вернувшись домой, Юрик задумался, какое минимальное количество пар людей могли быть знакомы, чтобы выполнялось это условие?

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

Формат выходных данных
Выведите одно целое число — минимальное количество пар знакомых людей.

Рассмотрим первый пример из условия. Возможны следующие варианты:

Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).
Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

Динамическое программирование на графах Комбинаторика

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

Загадка у костра#52269

Формат входных данных
Единственная строка содержит одно целое число \(n\) (\(1 \le n \le 5\,000\)) — количество людей.

Формат выходных данных
Выведите одно целое число — минимальное количество пар знакомых людей.

Замечание
Рассмотрим первый пример из условия. Возможны следующие варианты:

Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно \(\frac{4 \cdot 3}{2} = 6\).
Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно \(3\).

Алгоритмы на графах Динамическое программирование Комбинаторика

✓ 3✗ 7—Войти и решать

Чебаркульские спортсмены#43136

Алексей Юрьевич и Михаил Леонидович — тренера чебаркульской сборной по американскому футболу. Сегодня им нужно заполнить очень важную анкету на чемпионат мира, в которой необходимо указать всех членов команды в порядке возрастания их силы.
Для решения этой непростой задачи были собраны все игроки сборной, и каждый из спортсменов сказал несколько (возможно ноль) фраз вида: «Я сильнее, чем игрок k» (k может отличаться от высказывания к высказыванию, ни один спортсмен не говорил одинаковых фраз). Когда опрос был окончен, тренера поняли, что теперь могут однозначно упорядочить спортсменов по силе, соответствуя всем высказываниям.
Сразу после того, как Алексей Юрьевич и Михаил Леонидович написали ответ организаторам олимпиады, они задумались, а что было бы, если бы футболисты отвечали иначе? Ведь далеко не во всех случаях можно восстановить единственно возможный порядок игроков.
Теперь им интересно, сколько наборов ответов спортсменов однозначно задают их порядок? Так как это число может быть слишком большим, они просят найти лишь его остаток от деления на 10⁹+7.
Входные данные
Во входных данных записано единственное число n — количество спортсменов в сборной (1 <= n <= 10⁵) .
Выходные данные
Выведите единственное число — количество наборов ответов спортсменов, однозначно позволяющих упорядочить их по силе.

Примеры

№	Входные данные	Выходные данные
1	2	2

Замечание
В данном тесте вариантов ответов всего 2: первый сказал, что сильнее второго, второй не сказал ничего, или первый не сказал ничего и второй сказал, что он сильнее первого.

Вывод формулы Комбинаторика

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

Карты на троих#38656

Молчун, Ворчун и Пилюлькин играют в карточную игру на троих. Правила игры следующие.
Сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт.
В колоде Пилюлькина N карт, в колоде Молчуна M карт, а в колоде Ворчуна K карт. На каждой карточке написана буква p, m или v. Порядок карт в колодах не может быть изменен. Игроки ходят по очереди. Пилюлькин ходит первым.
Если в колоде текущего игрока есть хотя бы одна карта, сбросьте верхнюю карту в колоде.
Затем следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте.Например, если на карте написано «p», следующий ход переходит Пилюлькину.
Если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Есть 3^{N + M + K} возможных вариантов раскладки начальных колод трех игроков.
Сколько из этих шаблонов приведет к победе Пилюлькина? Поскольку ответ может быть большим, выведите его по модулю 1000000007 (= 10⁹ +7).

Входные данные
На вход подается три целых числа N, M и K (2<=N, M, K <=3*10⁵).

Выходные данные
Выведите количество победных для Пилюлькина шаблонов по модулю 1000000007 (= 10⁹ +7).

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 1 1	17	Если карта Пилюлькина - p, то Пилюлькин выиграет независимо от карты Молчуна и Ворчуна. Таких вариантов 3 × 3 = 9. Если карта Пилюлькина - m, Пилюлькин выиграет только тогда, когда карта Молчуна - p, или когда карта Молчуна - v, а карта Ворчуна - p. Всего таких шаблоно 3 + 1 = 4. Если карта Пилюлькина - v, Пилюлькин выиграет только тогда, когда карта Ворчуна - p, или когда карта Ворчуна - m, а карта Ворчуна - p. Всего таких шаблонов 3 + 1 = 4. Таким образом, всего 9 + 4 + 4 = 17 шаблонов, которые приведут к победе Пилюлькина.
2	4 2 2	1227
3	1000 1000 1000	261790852

Комбинаторика

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