Условие
Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).
Создайте программу, которая вычислит, сколькими различными способами шашка может попасть за $m$ ходов из клетки в центре одной грани на клетку, расположенную в центре смежной грани.
Входные данные
Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).
Выходные данные
Вывести искомое количество способов.
Тесты
| l | m | вывод |
|---|---|---|
| 3 | 3 | 1 |
| 3 | 4 | 0 |
| 3 | 5 | 25 |
| 51 | 199 | 4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360 |
| 3 | 199 | 11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399 |
Код
|
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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include <iostream> #include <iomanip> #include <vector> using namespace std; #define cr(a, b, x, y) case a: return CellCoord{b, x, y} #define SIDENUM 3 //количество сторон куба которые хранятся #define MAX_L 51 //максимальное значение L #define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики #define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики struct LongNum { //реализация длинной арифметики на векторах со сложением и выводом vector<int> v; LongNum() {} //стандартный конструктор LongNum(int s) { //конструктор из int v.push_back(s); } void print() { //вывод числа cout <<(v.empty() ? 0 : v.back()); for (int i = (int)v.size() - 2; i>=0; i--) cout <<setfill('0') <<setw(DNUM) <<v[i]; } void add(LongNum term) { //прибавление длинного числа auto b = term.v; int carry = 0; for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) { if (i == v.size()) v.push_back(0); v[i] += carry + (i < b.size() ? b[i] : 0); carry = v[i] >= BASE; if (carry) v[i] -= BASE; } } }; struct CellCoord { //хранит данные о положении клетки short side; short x, y; }; struct CellNeighbors { //хранит данные о положении всех(4) соседей определённой клетки CellCoord n[4]; }; CellCoord FixNeighbor(short l, short side, short x, short y) { //исправляет данные о положении клетки, если она выходит за края грани if(x == -1) { //если сосед находится левее грани switch(side) { //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую, //обнуляя y, а в x записывает старый y cr(0, 1, y, 0); //и так далее cr(1, 1, l-1, y); cr(2, 1, l-y-1, l-1); } } else if(x == l) {//правее switch(side) { cr(0, 1, l-y-1, 0); cr(1, 1, 0, y); cr(2, 1, y, l-1); } } else if(y == -1) {//выше switch(side) { cr(0, 1, l-x-1, 0); cr(1, 0, x, l-1); cr(2, 1, x, l-1); } } else if(y == l) {//ниже switch(side) { cr(0, 1, x, 0); cr(1, 2, x, 0); cr(2, 1, l-x-1, l-1); } } else { // если координаты не вышли за границы грани просто возвращаем неизменёные координаты return CellCoord{side, x, y}; } } CellNeighbors GetNeighbors(short l, short side, short x, short y) { //возвращает исправленные координаты всех(4) соседних клеток return CellNeighbors{{ FixNeighbor(l, side, x-1, y), FixNeighbor(l, side, x+1, y), FixNeighbor(l, side, x, y-1), FixNeighbor(l, side, x, y+1) }}; } int main() { short l, m; bool flag = false; cin >>l >>m; LongNum cubes[2][SIDENUM][MAX_L][MAX_L]; cubes[0][0][l/2][l/2] = LongNum(1); //за 0 ходов можно дойти 1 путём в изначальную точку CellNeighbors nbs[SIDENUM][MAX_L][MAX_L]; //массив координат соседей for(short side=0; side<SIDENUM; side++) { for(short xi=0; xi<l; xi++) { for(short yi=0; yi<l; yi++) { //перебор координат всех клеток nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi); //кэш координат соседних клеток } } } for(short i=0; i<m; i++) { for(short side=0; side<SIDENUM; side++) { for(short xi=0; xi<l; xi++) { for(short yi=0; yi<l; yi++) { //перебор всех клеток LongNum neighbor_sum; for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей neighbor_sum.add(cubes[flag][e.side][e.x][e.y]); //сложение количества путей ко всем соседям на предыдущем шаге } cubes[!flag][side][xi][yi] = neighbor_sum; //запись получившейся суммы в клетку } } } flag = !flag; //замена местами массива для предыдущего шага и нынешнего } cubes[flag][1][l/2][l/2].print(); //вывод количества путей к центру соседней грани на m-ом шаге } |
Решение
Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.
Раскладка шести граней куба с переходами между границами
Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.
Если посмотреть на правильный ответ к пятому примеру, становится видно, что на больших значениях ответы на тесты превышают все стандартные целочисленные типы данных, поэтому для полного решения необходимо использовать длинную арифметику. В программе она реализована в виде структуры LongNum, логика работы которой взята отсюда.
Также, посмотрев на куб, можно заметить что так как мы всегда начинаем в середине грани, то количество путей до клеток на смежных с начальной гранях идентично и нам не нужно просчитывать их всех, достаточно хранить и просчитывать одну боковую грань, как на втором рисунке.
Оптимизированный вариант хранения куба
Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.
Чуть было не зачел 🙂
— Где метки?
— Обоснуйте, почему это динамическое программирование и почему это задача на графы.
Добавил метки и расширил первый абзац в решении с обоснованием тегов.