Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Комбинаторика

Условие задачи  
ID 38499
Раскраска кеглей
Темы: Циклы    Комбинаторика   

В ряд ставятся N кеглей. Громозека красит каждую из них в один из K цветов из своих банок с краской. Из эстетических соображений любые две соседних кегли должны быть окрашены в разные цвета. Найдите количество возможных способов раскрасить кегли.

Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\)\(2<=K<=1000\)).

Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).
 

 

Примеры
Входные данные Выходные данные
1 2 2 2
1 1 10 10

 

ID 38588
Март
Темы: Комбинаторика   

Есть N человек. Имя i-го человека - Si . Мы хотим выбрать трех человек, чтобы выполнялись следующие условия:
- имя каждого выбранного человека начинается с M, А, R, С или Н
- среди выбранных людей нет людей, имена которых начинаются с одной буквы.
Сколько существует таких способов выбрать трех человек, не обращая внимания на порядок?

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

Выходные данные
Выведите ответ на задачу. Обратите внимание, что ответ может не соответствовать 32-битному целочисленному типу.
 

 

Примеры
Входные данные Выходные данные Пояснение
1 5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
2 Трех людей можно выбрать такими способами:

- MASHIKE, RUMOI, HABORO
MASHIKE, RUMOI, HOROKANAI

Ответ: 2

2 4
ZZ
ZZZ
Z
ZZZZZZZZZZ
0  
3 5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO
7  

ID 38634
Числовые печеньки - 2
Темы: Комбинаторика    Динамическое программирование   

У Громозеки N печенек. На i-й (1<=i<=N) печеньке написано целое число xi. Он выбирает одну или несколько из этих N печенек, так что среднее значение целых чисел, записанных на выбранных печеньках, равно А.
Какими способами он может сделать свой выбор?

Входные данные
В первой строке вводятся два целых числа N (1<=N<=50) и A (1<=A<=50). Во второй строке N целых чисел - xi (1<=xi<=50).

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

 

Примеры
Входные данные Выходные данные Примечение
1 4 8
7 9 8 9
5 Ниже приведены 5 способов выбрать печеньки так, чтобы в среднем было 8.
1) Выберите 3-ю карту.
2) Выберите 1-ю и 2-ю карты.
3) Выберите 1-ю и 4-ю карты.
4) Выберите 1-ю, 2-ю и 3-ю карты.
5) Выберите 1-ю, 3-ю и 4-ю карты.
2 3 8
6 6 9
0  
3 8 5
3 6 2 8 7 6 5 9
19  
4 33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
8589934591 Ответ может не соответствовать 32-битному целому числу.

 

ID 38656
Карты на троих
Темы: Комбинаторика   

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

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

Выходные данные
Выведите количество победных для Пилюлькина шаблонов по модулю 1000000007 (= 109 +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