11080 - Place the Guards

Problem G

Place the Guards
Input: Standard Input

Output: Standard Output

In the country of Ajabdesh there are some streets and junctions. Each street connects 2 junctions. The king of Ajabdesh wants to place some guards in some junctions so that all the junctions and streets can be guarded by them. A guard in a junction can guard all the junctions and streets adjacent to it. But the guards themselves are not gentle. If a street is guarded by multiple guards then they start fighting. So the king does not want the scenario where a street may be guarded by two guards. Given the information about the streets and junctions of Ajabdesh, help the king to find the minimum number of guards needed to guard all the junctions and streets of his country.

           

Input:

The first line of the input contains a single integer T (T<80 2="2" begins="begins" case="case" cases.="cases." class="GramE" each="each" indicating="indicating" nbsp="nbsp" number="number" of="of" span="span" test="test" the="the" with="with">integers

 v (1 ≤ v ≤ 200) and e (0 ≤ e ≤ 10000.). v is the number of junctions and e is the number of streets. Each of the next e line contains 2 integer f and t denoting that there is a street between f and t. All the junctions are numbered from 0 to v-1.

Output:

For each test case output in a single line an integer m denoting the minimum number of guards needed to guard all the junctions and streets. Set the value of m as -1 if it is impossible to place the guards without fighting.

Sample Input                             Output for Sample Input

2 4 2 0 1 2 3 5 5 0 1 1 2 2 3 0 4 3 4

2 -1

---

Problemsetter: Abdullah-al-Mahmud

Special Thanks: Md. Kamruzzaman

Graph, Bipartite checking

#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,E,color[200],cn;
vector<int>egs[200];
bool trav[200];
bool mark(int u,int cr,int &len){
    int b;
    if(DBG)printf("mark %d %d\n",u,cr);
    trav[u]=1,color[u]=cr;
    if(cr==1)cn++;
    int nc=(cr==1?2:1);
    rep(i,egs[u].size()){
        b=egs[u][i];
        if(color[b]&&color[b]!=nc)return 0;         //traverse and wrong color
        if(!trav[b])len++,mark(b,nc,len);             
    }
    return 1;
}
void ans(){
    int tot=0,len,c;
    bool fail=0;
    memset(color,0,sizeof(color));
    memset(trav,0,sizeof(trav));
    rep(i,N){
        if(!trav[i]){
            cn=0,len=1;
            if(mark(i,1,len)){
                if(DBG)printf("len cn %d %d\n",len,cn);
                c=min(cn,len-cn);
                if(c==0)c=1;
                tot+=c;
            }
            else {fail=1;break;}
        }
    }
    if(!fail)printf("%d\n",tot);
    else printf("-1\n");
}
int main(){
    int n,m,a,b;
    scanf("%d",&n);
    rep(i,n){
        rep(i,200)egs[i].clear();
        E=0;
        scanf("%d%d",&N,&m);
        rep(i,m)scanf("%d%d",&a,&b),egs[a].push_back(b),egs[b].push_back(a),E++;
        ans();
    }
}

uva 11060 - Beverages

Problem E - Beverages

Time Limit: 1 second

Dilbert has just finished college and decided to go out with friends. Dilbert has some strange habits and thus he decided to celebrate this important moment of his life drinking a lot. He will start drinking beverages with low alcohol content, like beer, and then will move to a beverage that contains more alcohol, like wine, until there are no more available beverages. Once Dilbert starts to drink wine he will not drink beer again, so the alcohol content of the beverages never decreases with the time.
You should help Dilbert by indicating an order in which he can drink the beverages in the way he wishes.

Input

Each test case starts with 1 ≤ N ≤ 100, the number of available beverages. Then will follow N lines, informing the name of each beverage, a name has less than 51 characters and has no white spaces. Then there is another line with an integer 0 ≤ M ≤ 200 and M lines in the form B₁ B₂ will follow, indicating that beverage B₂ has more alcohol that beverage B₁, so Dilbert should drink beverage B₁ before he starts drinking beverage B₂. Be sure that this relation is transitive, so if there is also a relation B₂ B₃ you should drink B₁ before you can drink B₃. There is a blank line after each test case. In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input. The input is terminated by end of file (EOF).

Output

For each test case you must print the message: Case #C: Dilbert should drink beverages in this order: B₁ B₂ ... B_N., where C is the number of the test case, starting from 1, and B₁ B₂ ... B_N is a list of the beverages such that the alcohol content of beverage B_i+1 is not less than the alcohol content of beverage B_i-1. After each test case you must print a blank line.

Sample Input

3
vodka
wine
beer
2
wine vodka
beer wine

5
wine
beer
rum
apple-juice
cachaca
6
beer cachaca
apple-juice beer
apple-juice rum
beer rum
beer wine
wine cachaca

10
cachaca
rum
apple-juice
tequila
whiskey
wine
vodka
beer
martini
gin
11
beer whiskey
apple-juice gin
rum cachaca
vodka tequila
apple-juice martini
rum gin
wine whiskey
apple-juice beer
beer rum
wine vodka
beer tequila

Sample Output

Case #1: Dilbert should drink beverages in this order: beer wine vodka.

Case #2: Dilbert should drink beverages in this order: apple-juice beer wine rum cachaca.

Case #3: Dilbert should drink beverages in this order: apple-juice wine vodka beer rum cachaca tequila whiskey martini gin.

---

Problem setter: Sérgio Queiroz de Medeiros
Topological sort + priority queue

#include<stdio.h>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,cnt[100],cases=1;
vector<int>egs[100];
map<string,int>mp;
vector<string>name;
void ans(){
    vector<int>res;
    int top=-1,cur,b;
    priority_queue<pair<int,int> >q;
    rep(i,N){
        if(!cnt[i]){
            if(DBG)printf("cnt[%d]=0\n",i);
            q.push(make_pair(-1*i,i));
        }
    }
    rep(i,N){
        cur=q.top().second,q.pop();
        if(DBG)printf("cur %d\n",cur+1);
        res.push_back(cur);
        rep(j,egs[cur].size()){
            b=egs[cur][j];
            cnt[b]--;
            if(!cnt[b])q.push(make_pair(-1*b,b));
        }
    }
    bool ll=0;
    printf("Case #%d: Dilbert should drink beverages in this order: ",cases++);
    rep(i,res.size()){if(ll)printf(" ");ll=1;printf("%s",name[res[i]].c_str());}
    printf(".\n\n");
}
int main(){
    char chs[100],chs2[100];
    int m,a,b,num;
    while(scanf("%d",&N)==1){
        num=0,name.clear(),mp.clear(),memset(cnt,0,sizeof(cnt));
        rep(i,100)egs[i].clear();
        rep(i,N)scanf("%s",chs),mp[chs]=num++,name.push_back(chs);
        scanf("%d",&m);
        rep(i,m)scanf("%s%s",chs,chs2),a=mp[chs],b=mp[chs2],egs[a].push_back(b),cnt[b]++;
        ans();
    }
}

uva 872 - Ordering

Ordering

Background
   Order is an important concept in mathematics and in computer science. For example, Zorns Lemma states: a partially ordered set in which every chain has an upper bound contains a maximal element. Order is also important in reasoning about the fix-point semantics of programs.
    This problem involves neither Zorns Lemma nor fix-point semantics, but does involve order.
Problem
   Given a list of variable constraints of the form A < B, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the contraints A < B and A < C there are two orderings of the variables A, B and C that are consistent with these constraints: ABC and ACB.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

   The input consists of two lines: a list of variables on one line, followed by a list of constraints of the form A < B on the next line. Variables and contraints are separated by single spaces.
   All variables are single character, upper-case letters. There will be at least two variables, and no more than 20 variables. There will be at least one constraint, and no more than 50 constraints. There will be no more than 300 orderings consistent with the contraints in a specification.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

   All orderings consistent with the constraints should be printed. Orderings are printed in alphabetical order, one per line. Characters on a line are separated by a space. If no ordering is possible, the output is a single line with the word NO.

Sample Input

1

A B F G
A<B B<F

Sample Output

A B F G
A B G F
A G B F
G A B F

---

Gabriel David, CPUP'2000 Round 2
Concurso de Programa��o da Universidade do Porto

Topological sort

#include<stdio.h>
#include<sstream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,cnt[26];
bool trav[26];
vector<int>sym;
vector<int>egs[26];
vector<string>res;
void topo(string s){
    if(s.size()==N){if(DBG)printf("s %s\n",s.c_str());res.push_back(s);return;}
    int b,cnt2[26];
    rep(i,N){
        if(!trav[sym[i]]&&!cnt[sym[i]]){
            trav[sym[i]]=1;
            memcpy(cnt2,cnt,sizeof(cnt));
            rep(j,egs[sym[i]].size()){
                b=egs[sym[i]][j];
                cnt[b]--;
            }
            topo(s+char('A'+sym[i]));
            memcpy(cnt,cnt2,sizeof(cnt));
            trav[sym[i]]=0;
        }
    }
}
void ans(){
    res.clear();
    topo("");
    sort(res.begin(),res.end());
    bool ll;
    if(res.size())
        rep(i,res.size()){
            ll=0;
            rep(j,res[i].size()){if(ll)printf(" ");ll=1;printf("%c",res[i][j]);}
            printf("\n");
        }
    else printf("NO\n");
}
void getO(string s){
    if(DBG)printf("%c<%c\n",s[0],s[2]);
    egs[s[0]-'A'].push_back(s[2]-'A');
    cnt[s[2]-'A']++;
}
int main(){
    char chs[200];
    stringstream buf;
    int n;
    bool ll=0;
    string s;
    scanf("%d",&n);
    rep(i,n){
        sym.clear();rep(i,20)egs[i].clear();
        memset(cnt,0,sizeof(cnt));
        scanf(" ");
        fgets(chs,200,stdin);if(chs[strlen(chs)-1]=='\n')chs[strlen(chs)-1]='\0';
        buf.clear(),buf.str(chs);
        while(!buf.eof())buf>>s,sym.push_back(s[0]-'A');
        if(DBG){printf("sym: ");rep(i,sym.size())printf("%c ",sym[i]+'A');printf("\n");}
        fgets(chs,200,stdin);if(chs[strlen(chs)-1]=='\n')chs[strlen(chs)-1]='\0';
        buf.clear(),buf.str(chs);
        while(!buf.eof())buf>>s,getO(s);
        N=sym.size();
        sort(sym.begin(),sym.end());
        if(ll)printf("\n");ll=1;
        ans();
    }
}

uva 11902 - Dominator

D

Dominator

In graph theory, a node X dominates a node Y if every path from the predefined start node to Y must go through X. If Y is not reachable from the start node then node Y does not have any dominator. By definition, every node reachable from the start node dominates itself. In this problem, you will be given a directed graph and you have to find the dominators of every node where the 0^th node is the start node.

As an example, for the graph shown right, 3 dominates 4 since all the paths from 0 to 4 must pass through 3. 1 doesn't dominate 3 since there is a path 0-2-3 that doesn't include 1.

Input

The first line of input will contain T (≤ 100) denoting the number of cases.

Each case starts with an integer N (0 < N < 100) that represents the number of nodes in the graph. The next N lines contain N integers each. If the j^th(0 based) integer of i^th(0 based) line is 1, it means that there is an edge from node i to node j and similarly a 0 means there is no edge.

Output

For each case, output the case number first. Then output 2N+1 lines that summarizes the dominator relationship between every pair of nodes. If node A dominates node B, output 'Y' in cell (A, B), otherwise output 'N'. Cell (A, B) means cell atA^th row and B^th column. Surround the output with |, + and – to make it more legible. Look at the samples for exact format.

Sample Input	Output for Sample Input
2 5 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1	Case 1: +---------+ |Y|Y|Y|Y|Y| +---------+ |N|Y|N|N|N| +---------+ |N|N|Y|N|N| +---------+ |N|N|N|Y|Y| +---------+ |N|N|N|N|Y| +---------+ Case 2: +-+ |Y| +-+

---

Problem Setter: Sohel Hafiz, Special Thanks: Kazi Rakibul Hossain, Jane Alam Jan

Graph Traversal, graph theory(reference)

#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int R,cases=1;
vector<int>egs[100],node;
bool trav[100],dom[100][100],rec[100];
void DT(int cur,int nop){
    int b;
    if(DBG)printf("cur %d ",cur);
    trav[cur]=1;
    rep(i,egs[cur].size()){
        b=egs[cur][i];
        if(b==nop)continue;
        if(!trav[b])DT(b,nop);
    }
}
void DFS(int cur){
    int b;
    trav[cur]=1;
    node.push_back(cur);
    rep(i,egs[cur].size()){
        b=egs[cur][i];
        if(!trav[b])DFS(b);
    }
}
void print(){
    printf("child(%d): ",node.size());
    rep(i,node.size())printf("%d ",node[i]);
}
void ans(){
    int b;
    node.clear();
    memset(trav,0,sizeof(trav));
    memset(dom,0,sizeof(dom));
    DFS(0);if(DBG)print();
    memcpy(rec,trav,sizeof(trav));
    rep(i,R)if(trav[i])dom[0][i]=1;
    REP(i,1,node.size()){
        b=node[i],memset(trav,0,sizeof(trav));
        DT(0,b);
        rep(j,R)if(rec[j]&&!trav[j])dom[b][j]=1;
    }       
    printf("Case %d:\n",cases++);
    printf("+");rep(i,R)if(i==0)printf("-");else printf("--");printf("+\n");
    rep(i,R){
        printf("|");
        rep(j,R){if(dom[i][j])printf("Y");else printf("N");printf("|");}
        printf("\n");
        printf("+");rep(i,R)if(i==0)printf("-");else printf("--");printf("+\n");
    }
}
int main(){
    int n,a;
    scanf("%d",&n);
    rep(i,n){
        scanf("%d",&R);
        rep(i,100)egs[i].clear();
        rep(i,R)rep(j,R){scanf("%d",&a);if(a)egs[i].push_back(j);}
        ans();
    }
}

uva 168 - Theseus and the Minotaur

Theseus and the Minotaur

Those of you with a classical education may remember the legend of Theseus and the Minotaur. This is an unlikely tale involving a bull headed monster, an underground maze full of twisty little passages all alike, love-lorn damsels and balls of silk. In line with the educational nature of this contest, we will now reveal the true story.

The maze was actually a series of caverns connected by reasonably straight passages, some of which could only be traversed in one direction. In order to trap the Minotaur, Theseus smuggled a large supply of candles into the Labyrinth, as he had discovered that the Minotaur was afraid of light. Theseus wandered around somewhat aimlessly until he heard the Minotaur approaching along a tunnel. At this point he lit a candle and set off in pursuit. The Minotaur retreated into the cavern it had just left and fled by another passage. Theseus followed, slowly gaining, until he reached the k'th cavern since lighting the candle. Here he had enough time to place the lighted candle in the middle of the cavern, light another one from it, and continue the chase. As the chase progressed, a candle was left in each k'th cavern passed through, thereby limiting the movement of the Minotaur. Whenever the Minotaur entered a cavern, it would check the exits in a particular order, fleeing down the first that did not lead directly to a lit cavern. (Remember that as Theseus was carrying a lit candle, the Minotaur never exited a cavern by the tunnel used to enter it.) Eventually the Minotaur became trapped, enabling Theseus to defeat it.

Consider the following Labyrinth as an example, where in this case the Minotaur checks the exits from a cavern in alphabetical order:



Assume that Theseus is in cavern C when he hears the Minotaur approaching from A, and that for this scenario, the value of k is 3. He lights a candle and gives chase, pursuing it through A, B, D (leaves a candle), G, E, F (another candle), H, E, G (another), H, E (trapped).

Write a program that will simulate Theseus's pursuit of the Minotaur. The description of a labyrinth will identify each cavern by an upper case character and will list the caverns reachable from that cavern in the order that the Minotaur will attempt them, followed by the identifiers for the caverns which the Minotaur and Theseus were in when contact was first made, followed by the value of k. If a cavern has no exit it may or may not be in the input.

Input

Input will consist of a series of lines. Each line will describe a scenario in the format shown below (which describes the above example). No line will contain more than 255 characters. The file will be terminated by a line consisting of a single #.

Output

Output will consist of one line for each Labyrinth. Each line will identify the lit caverns, in the order in which the candles were left, and the cavern in which the Minotaur was trapped, following the format shown in the example below.

Sample input

A:BCD;B:AD;D:BG;F:H;G:DEH;E:FGH;H:EG;C:AD. A C 3
#

Sample output

D F G /E

Graph Traversal

#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int A,B,L,K;
vector<int>egs[26],lc;
bool lit[26];
void DFS(int from,int cur,int len){
    if(DBG)printf("DFS cur len %c %d\n",cur+'A',len);
    bool final=1;
    if(len==K)lit[cur]=1,lc.push_back(cur),len=0;            //only lit when not trapped
    int a;
    rep(i,egs[cur].size()){
        a=egs[cur][i];
        if(!lit[a]&&a!=from){DFS(cur,a,len+1),final=0;break;}
    }
    if(final){                      //only lit when not trapped
        L=cur;
        if(lc.size()&&lc.back()==cur)lc.pop_back();
    }
}
void ans(){
    memset(lit,0,sizeof(lit));
    lc.clear();
    int c;
    bool ll=0;
    DFS(B,A,1);
    rep(i,lc.size()){if(ll)printf(" ");ll=1,printf("%c",'A'+lc[i]);}
    if(lc.size())printf(" /%c\n",L+'A');
    else printf("/%c\n",L+'A');
}
int getE(string s){
    int cur=0,next=0,cc,end;
    string a;
    rep(i,26)egs[i].clear();
    while(1){
        next=s.find(";",cur);
        if(next==string::npos)break;
        a=s.substr(cur,next-cur);
        if(DBG)printf("a: %s\n",a.c_str());
        cc=a[0]-'A';
        rep(i,a.size()-2)egs[cc].push_back(a[2+i]-'A');
        cur=next+1;
    }
    cc=s[cur]-'A';
    if(DBG)printf("s: %s\n",s.substr(cur,s.find(".",0)-cur).c_str());
    end=s.find(".",0);
    REP(i,cur+2,end)egs[cc].push_back(s[i]-'A');
    if(DBG)rep(i,26){
        if(egs[i].size()){printf("%c: ",char(i+'A'));rep(j,egs[i].size())printf("%c",egs[i][j]+'A');}
        printf("\n");
    }
    return end;
}
int main(){
    int a;
    char chs[280];
    while(fgets(chs,280,stdin)){
        if(chs[0]=='#')break;
        if(chs[strlen(chs)-1]=='\n')chs[strlen(chs)-1]='\0';
        a=getE(chs);
        A=chs[a+2]-'A',B=chs[a+4]-'A',K=atoi(&chs[a+6]);
        if(DBG)printf("from to k %c %c %d\n",A+'A',B+'A',K);
        ans();
    }
}

uva 10422 - Knights in FEN

Problem D

Knights in FEN

Input: standard input

Output: standard output

Time Limit: 10 seconds

There are black and white knights on a 5 by 5 chessboard. There are twelve of each color, and there is one square that is empty. At any time, a knight can move into an empty square as long as it moves like a knight in normal chess (what else did you expect?).

Given an initial position of the board, the question is: what is the minimum number of moves in which we can reach the final position which is:

Input

First line of the input file contains an integer N (N<14 are="are" below:="below:" description="description" each="each" given="given" how="how" indicates="indicates" inputs="inputs" is="is" many="many" of="of" p="p" set="set" sets="sets" that="that" the="the" there.="there.">

Each set consists of five lines; each line represents one row of a chessboard. The positions occupied by white knights are marked by 0 and the positions occupied by black knights are marked by 1. The space corresponds to the empty square on board.

There is no blank line between the two sets of input.

The first set of the sample input below corresponds to this configuration:

Output

For each set your task is to find the minimum number of moves leading from the starting input configuration to the final one. If that number is bigger than 10, then output one line stating

Unsolvable in less than 11 move(s).

otherwise output one line stating

Solvable in n move(s).

where n <= 10.

The output for each set is produced in a single line as shown in the sample output.

Sample Input

2

01011

110 1

01110

01010

00100

10110

01 11

10111

01001

00000

Sample Output

Unsolvable in less than 11 move(s).

Solvable in 7 move(s).

---

(Problem Setter: Piotr Rudnicki, University of Alberta, Canada)

“A man is as great as his dreams.”

 DFS+ bitmask + backtracking

#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

struct Node{
    Node(){}
    Node(int a,int b,int c):val(a),row(b),col(c){}
    int val,row,col;
    bool operator <(Node b)const{return val<b.val||row<b.row||col<b.col;}
};
int T,bnum=13;
set<Node>st;
int bottom[]= {5,10,11,12,15,16,17,18,20,21,22,23,24};
char chess[5][10],dir[8][2];
void init(){
    rep(i,5)T<<=1,T+=1;
    T<<=1;
    rep(i,4)T<<=1,T+=1;
    rep(i,3)T<<=1; rep(i,2)T<<=1,T+=1;
    rep(i,4)T<<=1;T<<=1,T+=1;
    rep(i,5)T<<=1;
    dir[0][0]=-2,dir[0][1]=-1,
    dir[1][0]=-2,dir[1][1]=1,
    dir[2][0]=-1,dir[2][1]=-2,
    dir[3][0]=-1,dir[3][1]=2,
    dir[4][0]=1,dir[4][1]=-2,
    dir[5][0]=1,dir[5][1]=2,
    dir[6][0]=2,dir[6][1]=-1,
    dir[7][0]=2,dir[7][1]=1;
}
void getHole(int &a,int &b){
    rep(i,5)rep(j,5)if(chess[i][j]==' ')a=i,b=j;
}
bool getH(int a,int b){
    return (a>>24-b)%2;
}
int setH(int a,int pos,int b){
    if(b)a|=1<<(24-pos);
    else a-=(a & (1<<(24-pos)) );
    return a;
}
int count(int c){
    int a=0;
    rep(i,bnum){if(getH(c,bottom[i]))a++;}
    if(DBG)printf("cnt: %d\n",a);
    return a;
}
int getC(){
    int c=0;
    rep(i,5)rep(j,5){
        if(chess[i][j]=='1')c<<=1,c+=1;
        else c<<=1;
    }
    return c;
}
int move(int v,int cr,int cc,int nr,int nc){
    int from=cr*5+cc,to=nr*5+nc;
    int h=getH(v,from);
    v=setH(v,from,0);
    v=setH(v,to,h);         //move
    return v;
}
bool valid(int a,int b){return a>=0&&a<5&&b>=0&&b<5;}
void print(int a){
    rep(i,5){
        rep(j,5)printf("%d",getH(a,i*5+j));
        printf("\n");
    }
}
void ans(){
    int cur,dis,next,cr,cc,nr,nc;
    bool h;
    Node nd;
    int res=11;
    st.clear();
    getHole(cr,cc);
    queue<pair<Node,int> >q;
    nd=Node(getC(),cr,cc);
    st.insert(nd);
    q.push(make_pair(nd,0));
    while(q.size()){
        cur=q.front().first.val,dis=q.front().second,
        cr=q.front().first.row,cc=q.front().first.col;
        if(DBG){printf("cur\n");print(cur);printf("cur cr cc dis %d %d %d %d\n",cur,cr,cc,dis);}
        q.pop();
        if(dis>10)break;
        if(count(cur)>10-dis)continue;
        if(cur==T&&cr==2&&cc==2){res=dis;break;}
        rep(i,8){
            nr=cr+dir[i][0],nc=cc+dir[i][1];
            if(valid(nr,nc)){
                if(DBG)printf("new hole %d %d\n",nr,nc);
                next=move(cur,nr,nc,cr,cc);
                nd=Node(next,nr,nc);
                if(!st.count(nd))
                    st.insert(nd),q.push(make_pair(Node(next,nr,nc),dis+1));
            }
        }
    }
    if(res>10)printf("Unsolvable in less than 11 move(s).\n");
    else printf("Solvable in %d move(s).\n",res);
}
int main(){
    int n;
    scanf("%d ",&n);
    init();
    rep(i,n){
        rep(i,5)fgets(chess[i],10,stdin);
        ans();
    }
}

uva 10400 - Game Show Math

Problem H
Game Show Math
Input: standard input
Output: standard output
Time Limit: 15 seconds

A game show in Britain has a segment where it gives its contestants a sequence of positive numbers and a target number. The contestant must make a mathematical expression using all of the numbers in the sequence and only the operators: +, -,*, and, /. Each number in the sequence must be used exactly once, but each operator may be used zero to many times. The expression should be read from left to right, without regard for order of operations, to calculate the target number. It is possible that no expression can generate the target number. It is possible that many expressions can generate the target number.

There are three restrictions on the composition of the mathematical expression:

o  the numbers in the expression must appear in the same order as they appear in the input file

o  since the target will always be an integer value (a positive number), you are only allowed to use / in the expression when the result will give a remainder of zero.

o  you are only allowed to use an operator in the expression, if its result after applying that operator is an integer from (-32000 .. +32000).

Input

The input file describes multiple test cases. The first line contains the number of test cases n.

Each subsequent line contains the number of positive numbers in the sequence p, followed by p positive numbers, followed by the target number. Note that 0 < p £ 100. There may be duplicate numbers in the sequence. But all the numbers are less than 32000.

Output

The output file should contain an expression, including all k numbers and (k-1) operators plus the equals sign and the target. Do not include spaces in your expression. Remember that order of operations does not apply here. If there is no expression possible output "NO EXPRESSION" (without the quotes). If more than one expression is possible, any one of them will do.

Sample Input

3
3 5 7 4 3
2 1 1 2000
5 12 2 5 1 2 4

Sample Output
5+7/4=3
NO EXPRESSION
12-2/5*1*2=4

---

(Problem-setter: Sandy Graham, CS Dept, University of Waterloo)

DFS + backtracking

#include<stdio.h>
#include<cstring>
#include<string>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,T,data[100];
bool trav[100][64001];
string res;
bool valid(int a){return a>=-32000&&a<=32000;}
bool DFS(int ind,int num,string s){
    if(DBG)printf("dfs ind num %d %d\n",ind ,num);
    if(ind==N){
        if(num==T){res=s;return 1;}
        return 0;
    }
    if(trav[ind][num+32000])return 0;
    trav[ind][num+32000]=1;
    if(valid(num+data[ind])&&DFS(ind+1,num+data[ind],s+'+'))return 1;
    if(valid(num-data[ind])&&DFS(ind+1,num-data[ind],s+'-'))return 1;
    if(valid(num*data[ind])&&DFS(ind+1,num*data[ind],s+'*'))return 1;
    if(data[ind]!=0&&num%data[ind]==0&&valid(num*data[ind])&&DFS(ind+1,num/data[ind],s+'/'))return 1;
    return 0;
}
void print(){
    printf("%d",data[0]);
    rep(i,res.size()){
        printf("%c%d",res[i],data[i+1]);
    }
    printf("=%d\n",T);
}
void ans(){
    int tot=0;
    memset(trav,0,sizeof(trav));
    if(DFS(1,data[0],""))print();
    else printf("NO EXPRESSION\n");
}
int main(){
    int n;
    scanf("%d",&n);
    rep(i,n){
        scanf("%d",&N);
        rep(i,N)scanf("%d",&data[i]);scanf("%d",&T);
        if(DBG)printf("T %d\n",T);
        ans();
    }
}