Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Płytki drukowane

By: a guest on Feb 27th, 2013  |  syntax: C++  |  size: 3.05 KB  |  views: 20  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <cstdio>
  2.  
  3. const int inf = 1000000000;
  4.  
  5. struct Q
  6. {
  7.     int a[4];
  8.    
  9.     int& operator[](int x)
  10.     {
  11.         return a[x];
  12.     }
  13.    
  14.     const int& operator[](int x) const
  15.     {
  16.         return a[x];
  17.     }
  18. };
  19.  
  20. void printQ(const Q &x)
  21. {
  22.     printf("%d %d %d %d\n", x[0], x[1], x[2], x[3]);
  23. }
  24.  
  25. Q getElem();
  26.  
  27. inline Q primitive()
  28. {
  29.     Q result;
  30.     result[0] = inf;
  31.     result[1] = 0;
  32.     result[2] = 0;
  33.     result[3] = 0;
  34.     return result;
  35. }
  36.  
  37. inline Q infQ()
  38. {
  39.     Q result;
  40.     for (int i = 0; i < 4; ++i)
  41.         result[i] = inf;
  42.     return result;
  43. }
  44.  
  45. inline int nonZero(int x)
  46. {
  47.     //printf("nonZero(%d)\n", x);
  48.     if (x == 0)
  49.         return 0;
  50.     else
  51.         return 1;
  52. }
  53.  
  54. int _inCost[4] = {0, 1, 1, 2};
  55.  
  56. inline int inCost(int x)
  57. {
  58.     return _inCost[x];
  59. }
  60.  
  61. inline Q series(int n)
  62. {
  63.     Q result = getElem();
  64.     for (int i = 1; i < n; ++i)
  65.     {
  66.         Q next = getElem();
  67.         Q newResult = infQ();
  68.         for (int last = 0; last < 4; ++last)
  69.         {
  70.             for (int cur = 0; cur < 4; ++cur)
  71.             {
  72.                 int newConfig = (last & 1) + (cur & 2);
  73.                 int connection = nonZero((last & 2) + (cur & 1));
  74.                 //printf("%d %d: %d %d :%d\n", last, cur, last & 2, cur & 1, connection);
  75.                 int cost = result[last] + next[cur] + connection;
  76.                 if (cost < newResult[newConfig])
  77.                     newResult[newConfig] = cost;
  78.             }
  79.         }
  80.         result = newResult;
  81.     }
  82.     return result;
  83. }
  84.  
  85. inline Q parallel(int n)
  86. {
  87.     Q pseudoResult = getElem();
  88.     for (int i = 0; i < 4; ++i)
  89.         pseudoResult[i] += inCost(i);
  90.     for (int i = 1; i < n; ++i)
  91.     {
  92.         Q next = getElem();
  93.         Q newPseudoResult = infQ();
  94.         for (int last = 0; last < 4; ++last)
  95.         {
  96.             for (int cur = 0; cur < 4; ++cur)
  97.             {
  98.                 int newConfig = last | cur;
  99.                 int connection = inCost(cur);
  100.                 int cost = pseudoResult[last] + next[cur] + connection;
  101.                 //printf("%d %d: %d %d %d\n", last, cur, newConfig, connection, cost);
  102.                 if (cost < newPseudoResult[newConfig])
  103.                     newPseudoResult[newConfig] = cost;
  104.             }
  105.         }
  106.         pseudoResult = newPseudoResult;
  107.     }
  108.     Q result;
  109.     for (int i = 0; i < 4; ++i)
  110.     {
  111.         result[i] = pseudoResult[i ^ 3];
  112.     }
  113.     return result;
  114. }
  115.  
  116. inline Q getElem()
  117. {
  118.     char tmp[2];
  119.     scanf("%s", tmp);
  120.     if (tmp[0] == 'X')
  121.         return primitive();
  122.     else
  123.     {
  124.         int n;
  125.         scanf("%d", &n);
  126.         if (tmp[0] == 'R')
  127.             return parallel(n);
  128.         else
  129.             return series(n);
  130.     }
  131. }
  132.  
  133. int main()
  134. {
  135.     Q result = getElem();
  136.     //printQ(result);
  137.     int best = inf;
  138.     for (int i = 0; i < 4; ++i)
  139.     {
  140.         int need = inCost(i);
  141.         int cost = result[i] + need;
  142.         //printf("%d: %d\n", i, cost);
  143.         if (cost < best)
  144.             best = cost;
  145.     }
  146.     printf("%d\n", best);
  147. }