ural 1155. Troubleduons

1155. Troubleduons

Time limit: 0.5 second
Memory limit: 64 MB

Archangel of the Science is reporting:
“O, Lord! Those physicists on the Earth have discovered a new elementary particle!”
“No problem, we’ll add another parameter to the General Equation of the Universe.”

As physics develops and moves on, scientists find more and more strange elementary particles, whose properties are more than unknown. You may have heard about muons, gluons and other strange particles. Recently scientists have found new elementary particles called troubleduons. These particles are called this way because scientists can create or annihilate them only in couples. Besides, troubleduons cause trouble to scientists, and that’s why the latter want to get rid of them. You should help scientists get rid of troubleduons.

Experimental set consists of eight cameras, situated in the vertices of a cube. Cameras are named as A, B, C, …, H. It is possible to generate or annihilate two troubleduons in neighbouring cameras. You should automate the process of removing troubleduons.

Input

The only line contain eight integers ranging from 0 to 100, representing number of troubleduons in each camera of experimental set.

Output

Output sequence of actions leading to annihilating all troubleduons or “IMPOSSIBLE”, if you cannot do it. Actions should be described one after another, each in a separate line, in the following way: name of the first camera, name of the second camera (it should be a neighborough to the first one), “+” if you create troubleduons, “-” if you destroy them. Number of actions in the sequence should not exceed 1000.

Samples

input	output
1 0 1 0 3 1 0 0	EF- EA- AD+ AE- DC-
0 1 0 1 2 3 2 2	IMPOSSIBLE

Problem Source: Ural Collegiate Programming Contest, April 2001, Perm, English Round

Tags: none ( hide tags for unsolved problems )

Difficulty: 468

题意：一个正方体，八个顶点各有一些颗粒在上面，每次相邻的两个点可以同时增加或消去一个颗粒，问让你给出一个操作序列把全部颗粒消去。

分析：显然，肯定先消去相邻的，知道不能消去为止。

按照这个思路，最后是要把点先增加再消去

我们发现互不相邻的点上的颗粒可以通过先增加，再消去的操作移动

比如a,0,c -> a+c, c, c -> a, 0, 0

就是这样。。。。

然后题目并没有要求最短操作序列。。。

所以我们把颗粒全都移到相邻的两个点上再消去就好。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <iostream>
  9 #include <algorithm>
 10 #include <map>
 11 #include <set>
 12 #include <ctime>
 13 using namespace std;
 14 typedef long long LL;
 15 typedef double DB;
 16 #define For(i, s, t) for(int i = (s); i <= (t); i++)
 17 #define Ford(i, s, t) for(int i = (s); i >= (t); i--)
 18 #define Rep(i, t) for(int i = (0); i < (t); i++)
 19 #define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
 20 #define rep(i, x, t) for(int i = (x); i < (t); i++)
 21 #define MIT (2147483647)
 22 #define INF (1000000001)
 23 #define MLL (1000000000000000001LL)
 24 #define sz(x) ((int) (x).size())
 25 #define clr(x, y) memset(x, y, sizeof(x))
 26 #define puf push_front
 27 #define pub push_back
 28 #define pof pop_front
 29 #define pob pop_back
 30 #define ft first
 31 #define sd second
 32 #define mk make_pair
 33 inline void SetIO(string Name) {
 34     string Input = Name+".in",
 35     Output = Name+".out";
 36     freopen(Input.c_str(), "r", stdin),
 37     freopen(Output.c_str(), "w", stdout);
 38 }
 39 
 40 inline int Getint() {
 41     int Ret = 0;
 42     char Ch = ' ';
 43     while(!(Ch >= '0' && Ch <= '9')) Ch = getchar();
 44     while(Ch >= '0' && Ch <= '9') {
 45         Ret = Ret*10+Ch-'0';
 46         Ch = getchar();
 47     }
 48     return Ret;
 49 }
 50 
 51 const int N = 8, Left[4] = {0, 2, 5, 7}, Right[4] = {1, 3, 4, 6};
 52 int Arr[N];
 53 
 54 inline void Input() {
 55     Rep(i, 8) scanf("%d", Arr+i);
 56 }
 57 
 58 inline void Create(int x, int y) {
 59     Arr[x]++, Arr[y]++;
 60     printf("%c%c+\n", 'A'+x, 'A'+y);
 61 }
 62 
 63 inline void Destroy(int x, int y) {
 64     Arr[x]--, Arr[y]--;
 65     printf("%c%c-\n", 'A'+x, 'A'+y);
 66 }
 67 
 68 inline void Move(int St, int Ed) {
 69     int Tmp;
 70     if(!Ed && St < 4) Tmp = 1;
 71     else if(!Ed) Tmp = 4;
 72     else if(St > 3) Tmp = 5;
 73     else Tmp = 0;
 74     while(Arr[St]) {
 75         if(!Arr[Tmp]) Create(Tmp, Ed);
 76         Destroy(Tmp, St);
 77     }
 78 }
 79 
 80 inline void Solve() {
 81     int a = 0, b = 0;
 82     Rep(i, 4) a += Arr[Left[i]], b += Arr[Right[i]];
 83     if(a != b) puts("IMPOSSIBLE");
 84     else {
 85         Rep(i, 4)
 86             if(Left[i]) Move(Left[i], 0);
 87         Rep(i, 4)
 88             if(Right[i] != 4) Move(Right[i], 4);
 89         while(Arr[0]) Destroy(0, 4);
 90     }
 91 }
 92 
 93 int main() {
 94     #ifndef ONLINE_JUDGE 
 95     SetIO("F");
 96     #endif 
 97     Input();
 98     Solve();
 99     return 0;
100 }