fork(1) download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. #define cr(a, b, x, y) case a: return CellCoord{b, x, y}
  7. #define SIDENUM 3 //количество сторон куба которые хранятся
  8. #define MAX_L 51 //максимальное значение L
  9.  
  10. #define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
  11. #define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики
  12.  
  13. struct LongNum {
  14.     //реализация длинной арифметики на векторах со сложением и выводом
  15.     vector<int> v;
  16.     LongNum() {} //стандартный конструктор
  17.     LongNum(int s) { //конструктор из int
  18.         v.push_back(s);
  19.     }
  20.     void print() { //вывод числа
  21.         cout <<(v.empty() ? 0 : v.back());
  22.         for (int i = (int)v.size() - 2; i>=0; i--)
  23.             cout <<setfill('0') <<setw(DNUM) <<v[i];
  24.     }
  25.     void add(LongNum term) { //прибавление длинного числа
  26.         auto b = term.v;
  27.         int carry = 0;
  28.         for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
  29.             if (i == v.size())
  30.                 v.push_back(0);
  31.             v[i] += carry + (i < b.size() ? b[i] : 0);
  32.             carry = v[i] >= BASE;
  33.             if (carry)  v[i] -= BASE;
  34.         }
  35.     }
  36. };
  37.  
  38. struct CellCoord {
  39.     //хранит данные о положении клетки
  40.     short side;
  41.     short x, y;
  42. };
  43.  
  44. struct CellNeighbors {
  45.     //хранит данные о положении всех(4) соседей определённой клетки
  46.     CellCoord n[4];
  47. };
  48.  
  49. CellCoord FixNeighbor(short l, short side, short x, short y) {
  50.     //исправляет данные о положении клетки, если она выходит за края грани
  51.     if(x == -1) { //если сосед находится левее грани
  52.         switch(side) {
  53.         //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
  54.         //обнуляя y, а в x записывает старый y 
  55.         cr(0, 1, y,     0); //и так далее
  56.         cr(1, 1, l-1,   y);
  57.         cr(2, 1, l-y-1, l-1);
  58.         }
  59.     } else if(x == l) {//правее
  60.         switch(side) {
  61.         cr(0, 1, l-y-1, 0);
  62.         cr(1, 1, 0,     y);
  63.         cr(2, 1, y,     l-1);
  64.         }
  65.     } else if(y == -1) {//выше
  66.         switch(side) {
  67.         cr(0, 1, l-x-1, 0);
  68.         cr(1, 0, x,     l-1);
  69.         cr(2, 1, x,     l-1);
  70.         }
  71.     } else if(y == l) {//ниже
  72.         switch(side) {
  73.         cr(0, 1, x,     0);
  74.         cr(1, 2, x,     0);
  75.         cr(2, 1, l-x-1, l-1);
  76.         }
  77.     } else {
  78.         // если координаты не вышли за границы грани просто возвращаем неизменённые координаты
  79.         return CellCoord{side, x, y};
  80.     }
  81. }
  82.  
  83. CellNeighbors GetNeighbors(short l, short side, short x, short y) {
  84.     //возвращает исправленные координаты всех(4) соседних клеток
  85.     return CellNeighbors{{
  86.         FixNeighbor(l, side, x-1, y),
  87.         FixNeighbor(l, side, x+1, y),
  88.         FixNeighbor(l, side, x, y-1),
  89.         FixNeighbor(l, side, x, y+1)
  90.     }};
  91. }
  92.  
  93. int main() {
  94.     short l, m;
  95.     bool flag = false;
  96.     cin >>l >>m;
  97.     LongNum cubes[2][SIDENUM][MAX_L][MAX_L];
  98.  
  99.     cubes[0][0][l/2][l/2] = LongNum(1);
  100.     //за 0 ходов можно дойти 1 путём в изначальную точку
  101.  
  102.     CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
  103.     //массив координат соседей
  104.  
  105.     for(short side=0; side<SIDENUM; side++) {
  106.         for(short xi=0; xi<l; xi++) {
  107.             for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
  108.                 nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
  109.                 //кэш координат соседних клеток
  110.             }
  111.         }
  112.     }
  113.  
  114.     for(short i=0; i<m; i++) {
  115.         for(short side=0; side<SIDENUM; side++) {
  116.             for(short xi=0; xi<l; xi++) {
  117.                 for(short yi=0; yi<l; yi++) { //перебор всех клеток
  118.                     LongNum neighbor_sum;
  119.                     for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
  120.                         neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
  121.                         //сложение количества путей ко всем соседям на предыдущем шаге
  122.                     }
  123.                     cubes[!flag][side][xi][yi] = neighbor_sum;
  124.                     //запись получившейся суммы в клетку
  125.                 }
  126.             }
  127.         }
  128.         flag = !flag; //замена местами массива для предыдущего шага и нынешнего
  129.     }
  130.     cubes[flag][1][l/2][l/2].print();
  131.     //вывод количества путей к центру соседней грани на m-ом шаге
  132. }
Success #stdin #stdout 0s 5016KB
comments (?)
stdin
copy 
3 5
stdout
copy 
25
https://ideone.com/sDkN7D
Решение задачи "Шашка на кубе" на e-olymp
(https://w...content-available-to-author-only...p.com/ru/problems/7213)
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!