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

e-maxx algorithm original: C/C++ #algorithm #combinatorics #emaxx #math

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

Static

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

it is required find количество способов расставить K слонов на доске размером NxN.

Thuật toán

Решать задачу будем с помощью динамического программирования. Пусть D[i][j] - количество способов расставить j слонов на диагоналях до i-ой включительно, причём только тех диагоналях, которые того же цвета, что и i-ая диагональ. Тогда i = 1..2N-1, j = 0..K. Диагонали занумеруем следующим образом (Ví dụ для доски 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 _

Т.е. нечётные номера соответствуют чёрным диагоналям, чётные - белым; диагонали нумеруем в порядке увеличения количества elementов в них. При такой нумерации мы можем вычислить каждое D[i][], основываясь только на D[i-2][] (двойка вычитается, чтобы мы рассматривали диагональ того же цвета). Итак, пусть текущий element динамики - 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-ой диагонали. НаVí dụ, 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. Наконец, вычислив динамику, find собственно ответ к задаче несложно. Перебираем количество i=0..K слонов, стоящих на чёрных диагоналях (номер последней чёрной диагонали - 2N-1), соответственно K-i слонов ставим на белые диагонали (номер последней белой диагонали - 2N-2), т.е. к ответу прибавляем величину D[2N-1][i] * D[2N-2][K-i].

Cài đặt

int n, k; // Đầu vàoные данные

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# lời giải

bản nháp tự động, xem lại trước khi gửi

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++ lời giải

đã khớp/gố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 lời giải

bản nháp tự động, xem lại trước khi gửi

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;
}

Материал разбит как Thuật toánическая Bài toán: изучить постановку, понять асимптотику и реализовать Thuật toán на выбранном языке.

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.