Задача

Василий на бумажке в виде полоски написал число, кратное $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$

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	public static int k, d, quantity = 0;
	public static long[] was = new long[40320];
	public static long[] nums = new long[9];
	public static boolean Was(long h) {
    	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;
	}
	public static void Swap(int a, int b) {
    	long t = nums[a];
    	nums[a] = nums[b];
    	nums[b] = t;
	}
	public static void Generate(int n) {
	    if (n == k) {
	        long sum = 0;
	        long p = 1;
	        long h = 0;
	        long hash = 1;
	        for (int i = k - 1; i >= 0; i--) {
	            long subs = nums[i];
	            sum += nums[i] % d * p;
	            p *= Math.pow(10, (long)Math.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(int j = n; j < k;j++) {
	            Swap(n,j);
	            Generate(n+1);
	            Swap(n,j);
	        }
	    }   
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		d = in.nextInt();
		k = in.nextInt();
    	for(int i = 0; i < k; i++) {
    		nums[i] = in.nextLong();
    	}
    	Generate(0);
    	System.out.println(quantity);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static int k, d, quantity = 0;

public static long[] was = new long[40320];

public static long[] nums = new long[9];

public static boolean Was(long h) {

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;

}

public static void Swap(int a, int b) {

long t = nums[a];

nums[a] = nums[b];

nums[b] = t;

}

public static void Generate(int n) {

if (n == k) {

long sum = 0;

long p = 1;

long h = 0;

long hash = 1;

for (int i = k - 1; i >= 0; i--) {

long subs = nums[i];

sum += nums[i] % d * p;

p *= Math.pow(10, (long)Math.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(int j = n; j < k;j++) {

Swap(n,j);

Generate(n+1);

Swap(n,j);

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

d = in.nextInt();

k = in.nextInt();

for(int i = 0; i < k; i++) {

nums[i] = in.nextLong();

}

Generate(0);

System.out.println(quantity);

}

Решение задачи

Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$ , который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$ , который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$ .
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$ , предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$ .

Ссылки

Условие задачи на e-olymp
Код решения

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: кратность

e-olymp 50. Разрезанное число