Задача
Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.
Входные данные
В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$
Выходные данные
Количество разных чисел.
Тесты
| Входные данные | Выходные данные |
| $5$ $3$ $13$ $85$ $45$ |
$4$ |
| $11$ $2$ $1$ $111$ |
$1$ |
| $11$ $3$ $11$ $8$ $11$ |
$0$ |
| $71$ $8$ $4018916609$ $7495223237$ $3405637482$ $3166003637$ $8998228133$ $1141886496$ $9124347310$ $7736090711$ |
$584$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <cmath> #include <algorithm> using namespace std; long long nums[9]; long long k; long long d; long long quantity = 0; long long was[40320]; bool Was(long long h) { long long c = 0; for (int i = 0; i < quantity; i++) { if (was[i] == h) c++; } if (c == 0) { was[quantity] = h; return true; } else return false; } void Swap(long long a,long long b) { long long t = nums[a]; nums[a] = nums[b]; nums[b] = t; } void Generate(long long n) { if (n==k) { long long sum = 0; long long p = 1; long long h = 0; long long hash = 1; for (long long i = k - 1; i >= 0; i--) { long long subs = nums[i]; sum += nums[i]%d*p; p *= pow(10, long(log10(nums[i]))+1); p = p%d; while (subs!= 0) { h += subs%10*hash; hash *= 101; subs /= 10; } } if (sum%d == 0 && Was(h) == true) { quantity++; } } else { for(long long j = n; j < k;j++) { Swap(n,j); Generate(n+1); Swap(n,j); } } } int main() { cin >> d >> k; for(long long i = 0; i < k; i++) { cin >> nums[i]; } Generate(0); cout << quantity; return 0; } |
Решение задачи
Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.
Ссылки
Условие задачи на e-olymp
Код решения