#include const int inf = 1000000000; struct Q { int a[4]; int& operator[](int x) { return a[x]; } const int& operator[](int x) const { return a[x]; } }; void printQ(const Q &x) { printf("%d %d %d %d\n", x[0], x[1], x[2], x[3]); } Q getElem(); inline Q primitive() { Q result; result[0] = inf; result[1] = 0; result[2] = 0; result[3] = 0; return result; } inline Q infQ() { Q result; for (int i = 0; i < 4; ++i) result[i] = inf; return result; } inline int nonZero(int x) { //printf("nonZero(%d)\n", x); if (x == 0) return 0; else return 1; } int _inCost[4] = {0, 1, 1, 2}; inline int inCost(int x) { return _inCost[x]; } inline Q series(int n) { Q result = getElem(); for (int i = 1; i < n; ++i) { Q next = getElem(); Q newResult = infQ(); for (int last = 0; last < 4; ++last) { for (int cur = 0; cur < 4; ++cur) { int newConfig = (last & 1) + (cur & 2); int connection = nonZero((last & 2) + (cur & 1)); //printf("%d %d: %d %d :%d\n", last, cur, last & 2, cur & 1, connection); int cost = result[last] + next[cur] + connection; if (cost < newResult[newConfig]) newResult[newConfig] = cost; } } result = newResult; } return result; } inline Q parallel(int n) { Q pseudoResult = getElem(); for (int i = 0; i < 4; ++i) pseudoResult[i] += inCost(i); for (int i = 1; i < n; ++i) { Q next = getElem(); Q newPseudoResult = infQ(); for (int last = 0; last < 4; ++last) { for (int cur = 0; cur < 4; ++cur) { int newConfig = last | cur; int connection = inCost(cur); int cost = pseudoResult[last] + next[cur] + connection; //printf("%d %d: %d %d %d\n", last, cur, newConfig, connection, cost); if (cost < newPseudoResult[newConfig]) newPseudoResult[newConfig] = cost; } } pseudoResult = newPseudoResult; } Q result; for (int i = 0; i < 4; ++i) { result[i] = pseudoResult[i ^ 3]; } return result; } inline Q getElem() { char tmp[2]; scanf("%s", tmp); if (tmp[0] == 'X') return primitive(); else { int n; scanf("%d", &n); if (tmp[0] == 'R') return parallel(n); else return series(n); } } int main() { Q result = getElem(); //printQ(result); int best = inf; for (int i = 0; i < 4; ++i) { int need = inCost(i); int cost = result[i] + need; //printf("%d: %d\n", i, cost); if (cost < best) best = cost; } printf("%d\n", best); }