В кинотеатре есть N разных фильмов для показа. Требуется составить расписание для показа…
- User
В кинотеатре есть N разных фильмов для показа. Требуется составить расписание для показа M
фильмов (не обязательно разных). Но если показывать одни и те же фильмы все время, посетители кинотеатра заскучают и уйдут домой. Поэтому нужно составить хорошее расписание.
Будем называть расписание хорошим, если в нем каждый фильм показывается хотя бы один раз. Также, в хорошем расписании фильм можно показать повторно только в том случае, если между повтором были показаны K
других фильмов.
По количеству фильмов N , общему числу сеансов M и величине K найдите количество хороших расписаний. Поскольку ответ может быть очень большим, выведите его по модулю числа 1000000007. C++ код
- Assistant
#include using namespace std;
const int MOD = 1000000007;
int countSchedules(int N, int M, int K) { // инициализация массива для хранения количества хороших расписаний int dp[M + 1]; dp[0] = 1; dp[1] = N;
// заполнение массива dp for (int i = 2; i <= M; i++) { dp[i] = (dp[i - 1] + dp[i - 2]) % MOD; if (i > K) { dp[i] = (dp[i] - dp[i - K - 1] + MOD) % MOD; } dp[i] = (dp[i] * (N - 1)) % MOD; } return dp[M];}
int main() { int N, M, K; cin >> N >> M >> K;
int result = countSchedules(N, M, K); cout << result << endl; return 0;}
- User
В кинотеатре есть N разных фильмов для показа. Требуется составить расписание для показа M
фильмов (не обязательно разных). Но если показывать одни и те же фильмы все время, посетители кинотеатра заскучают и уйдут домой. Поэтому нужно составить хорошее расписание.
Будем называть расписание хорошим, если в нем каждый фильм показывается хотя бы один раз. Также, в хорошем расписании фильм можно показать повторно только в том случае, если между повтором были показаны K
других фильмов.
По количеству фильмов N , общему числу сеансов M и величине K найдите количество хороших расписаний. Поскольку ответ может быть очень большим, выведите его по модулю числа 1000000007. C++ код например пользователь вводит числа 3 3 1 программа выводит ему 6
- Assistant
#include using namespace std;
const long long MOD = 1000000007;
long long countSchedules(int N, int M, int K) { // инициализация массива для хранения количества хороших расписаний long long dp[M + 1]; dp[0] = 1; dp[1] = N;
// заполнение массива dp for (int i = 2; i <= M; i++) { dp[i] = (dp[i - 1] + (dp[i - 2] * (N - 1)) % MOD) % MOD; if (i > K) { dp[i] = (dp[i] - dp[i - K - 1] + MOD) % MOD; } } return dp[M];}
int main() { int N, M, K; cin >> N >> M >> K;
long long result = countSchedules(N, M, K); cout << result << endl; return 0;}
- User
В кинотеатре есть N разных фильмов для показа. Требуется составить расписание для показа M
фильмов (не обязательно разных). Но если показывать одни и те же фильмы все время, посетители кинотеатра заскучают и уйдут домой. Поэтому нужно составить хорошее расписание.
Будем называть расписание хорошим, если в нем каждый фильм показывается хотя бы один раз. Также, в хорошем расписании фильм можно показать повторно только в том случае, если между повтором были показаны K
других фильмов.
По количеству фильмов N , общему числу сеансов M и величине K найдите количество хороших расписаний. Поскольку ответ может быть очень большим, выведите его по модулю числа 1000000007. C++ код например пользователь вводит числа 3 3 1 программа выводит ему должно вывести число 6
- Assistant
#include <iostream> using namespace std; const int MOD = 1000000007; int countSchedules(int N, int M, int K) { // инициализация массива для хранения количества хороших расписаний int dp[M + 1]; dp[0] = 1; dp[1] = N; // заполнение массива dp for (int i = 2; i <= M; i++) { dp[i] = dp[i - 1] + (dp[i - 2] * (N - 1)) % MOD; if (i > K) { dp[i] = (dp[i] - dp[i - K - 1] + MOD) % MOD; } } return dp[M]; } int main() { int N, M, K; cin >> N >> M >> K; int result = countSchedules(N, M, K); cout << result << endl; return 0; } - User
В торговом центре проходит ярмарка. Вся ярмарка состоит из N
киосков с уникальными товарами. Сережа хочет посетить все киоски и купить по одному товару в каждом. В киосках есть проходы в другие киоски, по этим проходам можно перемещаться в обе стороны.
Найдите наименьшее количество переходов, которые придется сделать Сереже, чтобы побывать в каждом из N
киосков. Один киоск можно посещать любое количество раз, один переход между парой киосков можно использовать любое количество раз. Начинать и заканчивать свой путь Сережа может в любых киосках, не обязательно в одном и том же.
Гарантируется, что ответ всегда существует и Сережа может пройти от любого киоска к любому другому через некоторое количество переходов. Входные данные
В первой строке входного потока дано одно целое число N (1≤N≤12) – количество киосков на ярмарке. В следующих N строках идет описание переходов из каждого киоска. В сроке с номером i первым идет число M (1≤M≤N) – количество доступных переходов из киоска с номером i, далее в этой же строке идет список из M чисел Ai,j (1≤Ai,j≤N) – номера киосков, в которые ведут переходы из киоска с номером i
. Выходные данные
Выведите одно число – наименьшее количество переходов, которые придется сделать Сереже, чтобы побывать в каждом киоске. C++
- Assistant
Для решения этой задачи можно использовать алгоритм обхода графа в ширину (BFS).
Начинаем с любого киоска и помечаем его как посещенный. Затем добавляем этот киоск в очередь. Продолжаем до тех пор, пока очередь не станет пустой.
На каждой итерации алгоритма извлекаем из очереди следующий киоск, и проверяем каждый его соседний киоск. Если какой-то из соседних киосков не был посещен, помечаем его как посещенный, и добавляем его в очередь.
После окончания алгоритма, проверяем, все ли киоски были посещены. Если да, то выводим количество переходов, которые Сереже придется сделать. Если нет, значит, ярмарка не связанная и не может быть достигнута из каждого киоска.
#include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; int findMinimumTransitions(int N, vector<vector<int>>& transitions) { vector<bool> visited(N + 1, false); queue<int> q; int startNode = 1; // выбираем любой киоск для старта int transitionsCount = 0; visited[startNode] = true; q.push(startNode); while (!q.empty()) { int currentNode = q.front(); q.pop(); for (int i = 0; i < transitions[currentNode].size(); i++) { int nextNode = transitions[currentNode][i]; if (!visited[nextNode]) { visited[nextNode] = true; q.push(nextNode); transitionsCount++; } } } if (transitionsCount == N - 1) { return N - 1; // считаем переходы, исключая стартовый киоск, так как он может посещаться на каждом переходе } else { return -1; // ярмарка не связанная } } int main() { int N; cin >> N; vector<vector<int>> transitions(N + 1); for (int i = 1; i <= N; i++) { int M; cin >> M; for (int j = 0; j < M; j++) { int kiosk; cin >> kiosk; transitions[i].push_back(kiosk); } } int result = findMinimumTransitions(N, transitions); cout << result << endl; return 0; }
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.