Constructorii angajaţi de faraonul Keops au terminat construirea piramidei în trepte mult visată. Măreaţa piramidă are n camere identice de formă cubică, numerotate de la 1 la n, dispuse pe m niveluri astfel:

• camera din vârful piramidei formează nivelul 1 şi are numărul 1;
• nivelul 2 al piramidei este format din următoarele 4 camere care în secţiune cu un plan paralel cu baza au aspectul unei matrice cu 2 linii şi 2 coloane; camerele de pe nivelul 2 sunt numerotate de la 2 la 5 în ordinea crescătoare a liniilor matricei, iar pe aceeaşi linie în ordinea crescătoare a coloanelor matricei;
  

  Exemplu

  suma5.in

  147 8 4 5 5 8 4 2 7 7 8 3 1 6

  suma5.out

  3 131 3 8

  Explicație

  Piramida conţine 14 camere dispuse pe m=3 trei niveluri. Nivelurile conţin valorile:

  

  Suma minimă s a tuturor costurilor aferente finisării şi decorării camerelor de un drum ce trece prin toate cele 3 niveluri ale piramidei este 13. Există mai multe drumuri pentru care se poate obţine suma minimă: [1,3,8], [1,4,13], [1,5,13]. Din punct de vedere lexicografic, cel mai mic drum dintre aceste drumuri este: [1,3,8].

  #include <bits/stdc++.h>
  
  using namespace std;
  
  ifstream cin("suma5.in");
  ofstream cout("suma5.out");
  
  int n , m[62][62][62] , sum , aux[62][62][62] , cnt , mini , x , y;
  
  int main()
  {
      cin >> n;
      while(sum < n) cnt++ , sum += cnt * cnt;
      cout <<  cnt << " ";
      int i = 1 , j = 1 , k = 1 , p;
      for(int x = 1 ; x <= n ; x++)
      {
          cin >> p;
          m[i][j][k] = p;
          aux[i][j][k] = x;
          if(i == j && i == k) i++ , j = 1 , k = 1;
          else if(k == i) j++ , k = 1;
          else k++;
      }
      for(int i = cnt - 1 ; i >= 1 ; i--)
          for(int j = 1 ; j <= i ; j++)
              for(int k = 1 ; k <= i ; k++)
                  m[i][j][k] = m[i][j][k] + min(m[i + 1][j][k] , min(m[i + 1][j + 1][k] , min(m[i + 1][j][k + 1] , m[i + 1][j + 1][k + 1])));
  
      cout << m[1][1][1] << endl;
      j = 1 , k = 1;
      for(int i = 1 ; i <= cnt ; i++)
      {
          cout << aux[i][j][k] << " ";
          int ok = 0;
          x = j , y = k , mini = m[i + 1][j][k];
          if(m[i + 1][j][k + 1] < mini) mini = m[i + 1][j][k + 1] , ok = 1;
          if(m[i + 1][j + 1][k] < mini) mini = m[i + 1][j + 1][k] , ok = 2;
          if(m[i + 1][j + 1][k + 1] < mini) mini = m[i + 1][j + 1][k + 1] , ok = 3;
          if(ok == 1) y = k + 1;
          if(ok == 2) x = j + 1;
          if(ok == 3) y = k + 1 , x = j + 1;
          j = x , k = y;
      }
  
  }

  Comentarii