E134. Расстановка слонов на шахматной доске

e-maxx algorithm оригинал: C/C++ #algorithm #combinatorics #emaxx #math

Static

Источник: e-maxx.ru/algo, страница PDF 430.

Требуется найти количество способов расставить K слонов на доске размером NxN.

Алгоритм

Решать задачу будем с помощью динамического программирования. Пусть D[i][j] - количество способов расставить j слонов на диагоналях до i-ой включительно, причём только тех диагоналях, которые того же цвета, что и i-ая диагональ. Тогда i = 1..2N-1, j = 0..K. Диагонали занумеруем следующим образом (пример для доски 5x5): черные: белые:

1 _ 5 _ 9 _ 2 _ 6 _

_ 5 _ 9 _ 2 _ 6 _ 8

5 _ 9 _ 7 _ 6 _ 8 _

_ 9 _ 7 _ 6 _ 8 _ 4

9 _ 7 _ 3 _ 8 _ 4 _

Т.е. нечётные номера соответствуют чёрным диагоналям, чётные - белым; диагонали нумеруем в порядке увеличения количества элементов в них. При такой нумерации мы можем вычислить каждое D[i][], основываясь только на D[i-2][] (двойка вычитается, чтобы мы рассматривали диагональ того же цвета). Итак, пусть текущий элемент динамики - D[i][j]. Имеем два перехода. Первый - D[i-2][j], т.е. ставим всех j слонов на предыдущие диагонали. Второй переход - если мы ставим одного слона на текущую диагональ, а остальных j-1 слонов - на предыдущие; заметим, что количество способов поставить слона на текущую диагональ равно количеству клеток в ней минус j-1, т.к. слоны, стоящие на предыдущих диагоналях, будут перекрывать часть направлений. Таким образом, имеем:

D[i][j] = D[i-2][j] + D[i-2][j-1] (cells(i) - j + 1)

где cells(i) - количество клеток, лежащих на i-ой диагонали. Например, cells можно вычислять так:

int cells (int i) {

if (i & 1)

return i / 4 * 2 + 1;

else

return (i - 1) / 4 * 2 + 2;

} Осталось определить базу динамики, тут никаких сложностей нет: D[i][0] = 1, D[1][1] = 1. Наконец, вычислив динамику, найти собственно ответ к задаче несложно. Перебираем количество i=0..K слонов, стоящих на чёрных диагоналях (номер последней чёрной диагонали - 2N-1), соответственно K-i слонов ставим на белые диагонали (номер последней белой диагонали - 2N-2), т.е. к ответу прибавляем величину D[2N-1][i] * D[2N-2][K-i].

Реализация

int n, k; // входные данные

if (k > 2*n-1) {

cout << 0;

return 0;

}

vector < vector<int> > d (n*2, vector<int> (k+2));

for (int i=0; i<n*2; ++i)

d[i][0] = 1;

d[1][1] = 1;

for (int i=2; i<n*2; ++i)

for (int j=1; j<=k; ++j)

d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);

int ans = 0;

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

ans += d[n2-1][i] d[n*2-2][k-i];

cout << ans;

C# решение

auto-draft, проверить перед отправкой

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    черные:     белые:
    1 _ 5 _ 9   _ 2 _ 6 _
    _ 5 _ 9 _   2 _ 6 _ 8
    5 _ 9 _ 7   _ 6 _ 8 _
    _ 9 _ 7 _   6 _ 8 _ 4
    9 _ 7 _ 3   _ 8 _ 4 _
    D[i][j] = D[i-2][j] + D[i-2][j-1] (cells(i) - j + 1)
    int cells (int i) {
            if (i & 1)
                    return i / 4 * 2 + 1;
            else
                    return (i - 1) / 4 * 2 + 2;
    }
    int n, k; // входные данные
    if (k > 2*n-1) {
            Console.WriteLine( 0;
            return 0;
    }
    vector < List<int> > d (n*2, List<int> (k+2));
    for (int i=0; i<n*2; ++i)
            d[i][0] = 1;
    d[1][1] = 1;
    for (int i=2; i<n*2; ++i)
            for (int j=1; j<=k; ++j)
                    d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);
    int ans = 0;
    for (int i=0; i<=k; ++i)
            ans += d[n*2-1][i] * d[n*2-2][k-i];
    Console.WriteLine( ans;
}

C++ решение

сопоставлено/оригинал

черные:     белые:
1 _ 5 _ 9   _ 2 _ 6 _
_ 5 _ 9 _   2 _ 6 _ 8
5 _ 9 _ 7   _ 6 _ 8 _
_ 9 _ 7 _   6 _ 8 _ 4
9 _ 7 _ 3   _ 8 _ 4 _
D[i][j] = D[i-2][j] + D[i-2][j-1] (cells(i) - j + 1)
int cells (int i) {
        if (i & 1)
                return i / 4 * 2 + 1;
        else
                return (i - 1) / 4 * 2 + 2;
}
int n, k; // входные данные
if (k > 2*n-1) {
        cout << 0;
        return 0;
}
vector < vector<int> > d (n*2, vector<int> (k+2));
for (int i=0; i<n*2; ++i)
        d[i][0] = 1;
d[1][1] = 1;
for (int i=2; i<n*2; ++i)
        for (int j=1; j<=k; ++j)
                d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);
int ans = 0;
for (int i=0; i<=k; ++i)
        ans += d[n*2-1][i] * d[n*2-2][k-i];
cout << ans;

Java решение

auto-draft, проверить перед отправкой

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    черные:     белые:
    1 _ 5 _ 9   _ 2 _ 6 _
    _ 5 _ 9 _   2 _ 6 _ 8
    5 _ 9 _ 7   _ 6 _ 8 _
    _ 9 _ 7 _   6 _ 8 _ 4
    9 _ 7 _ 3   _ 8 _ 4 _
    D[i][j] = D[i-2][j] + D[i-2][j-1] (cells(i) - j + 1)
    int cells (int i) {
            if (i & 1)
                    return i / 4 * 2 + 1;
            else
                    return (i - 1) / 4 * 2 + 2;
    }
    int n, k; // входные данные
    if (k > 2*n-1) {
            System.out.println( 0;
            return 0;
    }
    vector < ArrayList<Integer> > d (n*2, ArrayList<Integer> (k+2));
    for (int i=0; i<n*2; ++i)
            d[i][0] = 1;
    d[1][1] = 1;
    for (int i=2; i<n*2; ++i)
            for (int j=1; j<=k; ++j)
                    d[i][j] = d[i-2][j] + d[i-2][j-1] * (cells(i) - j + 1);
    int ans = 0;
    for (int i=0; i<=k; ++i)
            ans += d[n*2-1][i] * d[n*2-2][k-i];
    System.out.println( ans;
}

Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.