| Условие задачи | | Прогресс |
|
Темы:
Циклы
Комбинаторика
В ряд ставятся 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, С или Н;
- среди выбранных людей нет людей, имена которых начинаются с одной буквы.
Сколько существует таких способов выбрать трех человек, не обращая внимания на порядок?
Входные данные
В первой строке записано целое число N (\(1<=N<=10^5\)) В следующих N строках записаны имена Si - строка, состоящая только из английских заглавных букв, длина строки не более 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 |
|
| |
![]()
|
|
Темы:
Комбинаторика
Динамическое программирование
У Громозеки N печенек. На i-й (1<=i<=N) печеньке написано целое число xi. Он выбирает одну или несколько из этих печенек, так чтобы среднее значение целых чисел, записанных на выбранных печеньках, было равно А.
Какими способами он может сделать свой выбор?
Входные данные
В первой строке вводятся два целых числа 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-битному целому числу. |
| |
![]()
|
|
Темы:
Комбинаторика
Молчун, Ворчун и Пилюлькин играют в карточную игру на троих. Правила игры следующие.
Сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт.
В колоде Пилюлькина 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 |
|
| |
![]()
|
|
Темы:
Циклы
Комбинаторика
Снежик Сугробович положил в ряд N ёлочных шаров, для того чтобы их покрасить. Он решил, что каждый шар будет одним из K цветов. При этом Снежик Сугробович хочет, чтобы любые два соседних ёлочных шара были окрашены в разные цвета. Найдите количество возможных способов раскрасить ёлочные шары.
Входные данные
Входная строка содержит два целых числа N и K (\(1<=N<=1000\), \(2<=K<=1000\)).
Выходные данные
Выведите на экран ответ на задачу. Гарантируется, что верный ответ не превышает \(2^{31}-1\).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 2 |
2 |
| 1 |
1 10 |
10 |
| |
![]()
|