Олимпиадная задача. Как найти количество всех возможных сумм в массивах

Рейтинг: 2Ответов: 1Опубликовано: 29.03.2023

Недавно Андрей придумал новый способ генерации случайных чисел. Способ заключается в том, что каждый из N друзей Андрея берет кубик и записывает на всех на всех гранях целые числа (не обязательно различные). После этого все друзья кидают свои кубики, а Андрей складывает выпавшие на кубиках числа. Сумма и будет сгенерированным случайным числом. Сколько различных чисел можно получить таким способом?

Входные данные: В первой строке содержится целое число N — количество друзей (3≤N≤100) В i-й из следующих N строк содержатся целые числа ai1, ai2, ai3, ai4, ai5, ai6 — числа на гранях кубика i-го друга (0≤aij≤500)

Выходные данные Количество различных чисел которые могут быть получены с помощью описанного способа генерации рандомных чисел

Входные данные

3
0 1 2 3 4 5
0 0 2 3 4 5
3 4 5 0 0 0

выходные данные

16

Я решил эту задачу для частного случая при N = 3, но не получается для других N, как можно решить? Да и перебор всех возможных вариантов выглядит не оптимально

int n = int.Parse(Console.ReadLine());
int[,] arrays = new int[n, 6];

for (int i = 0; i < n; i++)
{
    string[] input = Console.ReadLine().Split(' ');
    for (int j = 0; j < 6; j++)
    {
        arrays[i, j] = int.Parse(input[j]);
    }
}

HashSet<int> sums = new HashSet<int>(); 
for (int i1 = 0; i1 < 6; i1++)
{
    for (int i2 = 0; i2 < 6; i2++)
    {
        for (int i3 = 0; i3 < 6; i3++)
        {
            int sum = arrays[0, i1] + arrays[1, i2] + arrays[2, i3];
            sums.Add(sum);
        }
    }
}
Console.WriteLine(sums.Count);
c# олимпиада
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Динамическое программирование. Значение максимальной суммы невелико (50000), поэтому я использовал пару массивов sums, переключаясь между ними на каждом шаге. При большой максимальной сумме и редких значениях сумм можно использовать hashset, но для ограничений этой задачи - не требуется. Сложность O(maxsum*n) (ещё множитель 6, на асимптотику не влияет)

    int n = int.Parse(Console.ReadLine());
    int[,] arrays = new int[n, 6];
    int[] mx = new int[n];

    for (int i = 0; i < n; i++)
    {
        string[] input = Console.ReadLine().Split(' ');
        mx[i] = -1;
        for (int j = 0; j < 6; j++)
        {
            arrays[i, j] = int.Parse(input[j]);
            mx[i] = Math.Max(mx[i], arrays[i, j]);
        }
    }
    int mxs = mx.Sum();
    int[,] sums = new int[2, mxs + 1];
    for (int i = 1; i <= mxs; i++)
        sums[1, i] = 0;
    sums[1, 0] = 1;

    for (int i = 0; i < n; i++)
    {
        int cur = i & 1;
        int last = (i + 1) & 1;
        for (int k = 0; k <= mxs; k++)
            sums[cur, k] = 0;
        for (int ida = 0; ida < 6; ida++)
        {
            int x = arrays[i, ida];
            for (int j = 0; j <= mxs - x; j++)
                if (sums[last, j] > 0)
                    sums[cur, j + x] = 1;
        }
    }
    int t = 0;
    for (int k = 0; k <= mxs; k++)
        t += sums[(n-1)&1, k];
    Console.WriteLine(t);