Задача 2. Хакер Артем
Ім’я вхідного файлу: input.txt
Ім’я вихідного файлу: output.txt
Ліміт часу: 1с.
Того дня йшов дощ. Молодий програміст Артем сидів один у маленькій кімнаті і писав новий комп’ютерний
вірус, який обов'язково зробить його відомим… Артем не дуже добре розбирається в математиці, але щоб
писати таке програмне забезпечення потрібно мати справу з числами і цифрами. Вірус повинен з легкістю
пограбувати декілька великих банків, якщо він зможе визначати кiлькість n-цифрових чисел, для кожного з
яких сума всiх цифр дорiвнює m.
Вхідні дані. Один рядок стандартного вхідного потоку містить два натуральнi числа n i m (n ≤ 128, m ≤ 1024).
Вихідні дані. Єдиний рядок стандартного потоку виводу має містити шукану кiлькість n-цифрових чисел, для
кожного з яких сума всiх цифр дорiвнює m.
Приклад.
Input.txt: 4 4
Output.txt: 2
Ответы на вопрос
Для розв'язання цієї задачі можна використовувати динамічне програмування. Спробуюмо побудувати таблицю динамічного програмування, де dp[i][j] представляє кількість n-цифрових чисел, для кожного з яких сума всіх цифр дорівнює j.
#include <iostream>
#include <vector>
int countNumbers(int n, int m) {
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
// Ініціалізація базових випадків
for (int i = 1; i <= 9; i++) {
if (i <= m) {
dp[1][i] = 1;
}
}
// Заповнення таблиці динамічного програмування
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= 9; k++) {
if (j - k >= 0) {
dp[i][j] += dp[i - 1][j - k];
}
}
}
}
return dp[n][m];
}
int main() {
int n, m;
std::cin >> n >> m;
int result = countNumbers(n, m);
std::cout << result << std::endl;
return 0;
}
Ця програма обчислює кількість n-цифрових чисел, для кожного з яких сума всіх цифр дорівнює m. Зауважте, що вона працює для обмежень n ≤ 128 та m ≤ 1024. У вас має бути файл input.txt з вхідними даними та файл output.txt, де буде записана шукана кількість n-цифрових чисел.