October 2015 – Live with passion

710

Asif NaeemOctober 26, 2015

This is quite an easy problem. But it took me long time to realize that to determine the number of total game segments is nothing but counting the direction changes to reach the destination.

#include <iostream>
#include <cstdio>
#include <climits>
#include <queue>
#include <cstring>
#include <string>

using namespace std;

int w,h;
int SEGMENT;
int gr[80][80];
int visit[80][80];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int bfs(int stx,int sty,int edx,int edy)
{
	int x,y,stp;
	int direction=0,tmpDirection;
	int tmpx,tmpy;
	queue<int> q;
	memset(visit,0,sizeof(visit));
	int step=0;
	q.push(stx);
	q.push(sty);
	q.push(step);
	q.push(direction);

	while(!q.empty())
	{
		x = q.front();q.pop();
		y = q.front();q.pop();
		stp = q.front();q.pop();
		direction = q.front();q.pop();
		visit[x][y]=1;

		for(int i=0;i<4;i++)
		{
			if(x+dx[i]==edx && y+dy[i]==edy)
			{
				if(dx[i]==0)
					tmpDirection=1;//horizontal direction
				else if(dy[i]==0)
					tmpDirection=2;//vertical direction
				if(tmpDirection!=direction)
					return stp+1;
				return stp;
			}
			if(x+dx[i]>=0 && x+dx[i]<=(h+1) && y+dy[i]>=0 && y+dy[i]<=(w+1) && visit[x+dx[i]][y+dy[i]]==0 && gr[x+dx[i]][y+dy[i]]==0)
			{
				tmpx = x+dx[i];
				tmpy = y+dy[i];
				q.push(x+dx[i]);
				q.push(y+dy[i]);
				if(dx[i]==0)
					tmpDirection=1;//horizontal direction
				else if(dy[i]==0)
					tmpDirection=2;//vertical direction
				if(tmpDirection!=direction)
					q.push(stp+1);
				else if(tmpDirection==direction)
					q.push(stp);
				q.push(tmpDirection);
			}
		}
	}
	return -1;
}


int main()
{
	char ch;
	int kase=1;
	string str;
	vector<int> path;
	int x1,x2,y1,y2;
	while(scanf("%d%c%d%c",&w,&ch,&h,&ch),w,h)
	{
		memset(gr,0,sizeof(gr));
		for(int i=1;i<=h;i++)
		{
			getline(cin,str);
			for(int j=0;j<w;j++)
			{
				if(str[j]=='X')
				gr[i][j+1]=1;
				else if(str[j]==' ')
				gr[i][j+1]=0;
			}
		}
		bool flag=0;
		int ccase=1;
		int res;
		while(scanf("%d%c%d%c%d%c%d%c",&x1,&ch,&y1,&ch,&x2,&ch,&y2,&ch))
		{
			if(x1+y1+x2+y2==0)
			break;
			res = bfs(y1,x1,y2,x2);
			if(flag==0)
				printf("Board #%d:\n",kase++);
			flag = 1;
			if(res==-1)
			printf("Pair %d: impossible.\n",ccase++);
			else
			printf("Pair %d: %d segments.\n",ccase++,res);
		}
		printf("\n");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include <iostream>

#include <cstdio>

#include <climits>

#include <queue>

#include <cstring>

#include <string>

using namespace std;

int w,h;

int SEGMENT;

int gr[80][80];

int visit[80][80];

int dx[4]={0,0,1,-1};

int dy[4]={1,-1,0,0};

int bfs(int stx,int sty,int edx,int edy)

{

int x,y,stp;

int direction=0,tmpDirection;

int tmpx,tmpy;

queue<int> q;

memset(visit,0,sizeof(visit));

int step=0;

q.push(stx);

q.push(sty);

q.push(step);

q.push(direction);

while(!q.empty())

{

x = q.front();q.pop();

y = q.front();q.pop();

stp = q.front();q.pop();

direction = q.front();q.pop();

visit[x][y]=1;

for(int i=0;i<4;i++)

{

if(x+dx[i]==edx && y+dy[i]==edy)

{

if(dx[i]==0)

tmpDirection=1;//horizontal direction

else if(dy[i]==0)

tmpDirection=2;//vertical direction

if(tmpDirection!=direction)

return stp+1;

return stp;

}

if(x+dx[i]>=0 && x+dx[i]<=(h+1) && y+dy[i]>=0 && y+dy[i]<=(w+1) && visit[x+dx[i]][y+dy[i]]==0 && gr[x+dx[i]][y+dy[i]]==0)

{

tmpx = x+dx[i];

tmpy = y+dy[i];

q.push(x+dx[i]);

q.push(y+dy[i]);

if(dx[i]==0)

tmpDirection=1;//horizontal direction

else if(dy[i]==0)

tmpDirection=2;//vertical direction

if(tmpDirection!=direction)

q.push(stp+1);

else if(tmpDirection==direction)

q.push(stp);

q.push(tmpDirection);

}

return -1;

}

int main()

{

char ch;

int kase=1;

string str;

vector<int> path;

int x1,x2,y1,y2;

while(scanf("%d%c%d%c",&w,&ch,&h,&ch),w,h)

{

memset(gr,0,sizeof(gr));

for(int i=1;i<=h;i++)

{

getline(cin,str);

for(int j=0;j<w;j++)

{

if(str[j]=='X')

gr[i][j+1]=1;

else if(str[j]==' ')

gr[i][j+1]=0;

}

bool flag=0;

int ccase=1;

int res;

while(scanf("%d%c%d%c%d%c%d%c",&x1,&ch,&y1,&ch,&x2,&ch,&y2,&ch))

{

if(x1+y1+x2+y2==0)

break;

res = bfs(y1,x1,y2,x2);

if(flag==0)

printf("Board #%d:\n",kase++);

flag = 1;

if(res==-1)

printf("Pair %d: impossible.\n",ccase++);

else

printf("Pair %d: %d segments.\n",ccase++,res);

}

printf("\n");

}

return 0;

}

677

Asif NaeemOctober 25, 2015

#include <iostream>
#include <climits>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>

using namespace std;

int gr[15][15];
bool found = false;
vector<int> vb;
int node,length;

int backtrack(int st,int len,bool visit[])
{
	if(len==length)
	{
		found=1;
		printf("(");
		for(int i=0;i<vb.size();i++)
		{
			printf("%d%s",vb[i]+1,i==vb.size()-1?")\n":",");
		}
		return 0;
	}
	for(int i=0;i<node;i++)
	{
		if(gr[st][i]==1 && visit[i]==0)
		{
			visit[i]=1;
			vb.push_back(i);
			backtrack(i,len+1,visit);
			visit[i]=0;
			vb.pop_back();
		}
	}
	return 1;
}

int main()
{
	int trash;
	int parent[15];
	bool visit[15];
	bool flag=false;
	do
	{
		scanf("%d",&node);
		scanf("%d",&length);
		memset(gr,0,sizeof(gr));
		for(int i=0;i<node;i++)
		{
			for(int j=0;j<node;j++)
			{
				scanf("%d",&gr[i][j]);
			}
		}
		int len=0;
		int st=0;
		vb.clear();
		for(int i=0;i<node;i++)
		{
			visit[i]=false;
			parent[i]=-1;
		}
		visit[st]=1;
		vb.push_back(st);
		if(flag)
		printf("\n");
		flag=1;
		found=0;
		backtrack(st,len,visit);//from 1st node
		if(!found)
		printf("no walk of length %d\n",length);
	}while(scanf("%d",&trash)==1);
	return 0;
}

#include <iostream>

#include <climits>

#include <cstdio>

#include <cstring>

#include <vector>

#include <string>

using namespace std;

int gr[15][15];

bool found = false;

vector<int> vb;

int node,length;

int backtrack(int st,int len,bool visit[])

{

if(len==length)

{

found=1;

printf("(");

for(int i=0;i<vb.size();i++)

{

printf("%d%s",vb[i]+1,i==vb.size()-1?")\n":",");

}

return 0;

}

for(int i=0;i<node;i++)

{

if(gr[st][i]==1 && visit[i]==0)

{

visit[i]=1;

vb.push_back(i);

backtrack(i,len+1,visit);

visit[i]=0;

vb.pop_back();

}

return 1;

}

int main()

{

int trash;

int parent[15];

bool visit[15];

bool flag=false;

{

scanf("%d",&node);

scanf("%d",&length);

memset(gr,0,sizeof(gr));

for(int i=0;i<node;i++)

{

for(int j=0;j<node;j++)

{

scanf("%d",&gr[i][j]);

}

int len=0;

int st=0;

vb.clear();

for(int i=0;i<node;i++)

{

visit[i]=false;

parent[i]=-1;

}

visit[st]=1;

vb.push_back(st);

if(flag)

printf("\n");

flag=1;

found=0;

backtrack(st,len,visit);//from 1st node

if(!found)

printf("no walk of length %d\n",length);

}while(scanf("%d",&trash)==1);

return 0;

}

633

Asif NaeemOctober 24, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>

using namespace std;

int stx,sty,edx,edy;
int gr[405][405];
int dirx[8]={-2,-2,2,2,1,1,-1,-1};
int diry[8]={1,-1,1,-1,2,-2,2,-2};
int dx[4]={2,2,-2,-2};
int dy[4]={-2,2,2,-2};
int n;

int bfs()
{
	queue<int> q;
	int x,y;
	//int visit[405][405];
	//memset(visit,0,sizeof(visit));
	int moveTyp=0,move;
	int step=0,stepCount;
	q.push(stx);q.push(sty);q.push(moveTyp);q.push(step);
	if(gr[stx][sty]==1)
	return -1;
	else if(gr[edx][edy]==1)
	return -1;

	while(!q.empty())
	{
		x = q.front();q.pop();
		y = q.front();q.pop();
		moveTyp = q.front();q.pop();
		stepCount = q.front();q.pop();
		gr[x][y]=1;
		if(x==edx && y==edy)
		{
			return stepCount;
		}
		if(moveTyp==0)
		{
			//move=1;//regular move
			for(int i=0;i<8;i++)
			{
				if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)
				{
					q.push(x+dirx[i]);
					q.push(y+diry[i]);
					q.push(1);
					q.push(stepCount+1);
				}
			}
			//move=2//bishop
			for(int i=0;i<4;i++)
			{
				if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)
				{
					q.push(x+dx[i]);
					q.push(y+dy[i]);
					q.push(2);
					q.push(stepCount+1);
				}
			}
			//move=3//teleportation
			if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)
			{
				q.push(2*n-x+1);
				q.push(y);
				q.push(3);
				q.push(stepCount+1);
			}
			if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)
			{
				q.push(x);
				q.push(2*n-y+1);
				q.push(3);
				q.push(stepCount+1);
			}
		}
		else if(moveTyp==1)
		{
			//move=2//bishop
			for(int i=0;i<4;i++)
			{
				if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)
				{
					q.push(x+dx[i]);
					q.push(y+dy[i]);
					q.push(2);
					q.push(stepCount+1);
				}
			}
			//move=3//teleportation
			if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)
			{
				q.push(2*n-x+1);
				q.push(y);
				q.push(3);
				q.push(stepCount+1);
			}
			if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)
			{
				q.push(x);
				q.push(2*n-y+1);
				q.push(3);
				q.push(stepCount+1);
			}
		}
		else if(moveTyp==2)
		{
			//move=3//teleportation
			if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)
			{
				q.push(2*n-x+1);
				q.push(y);
				q.push(3);
				q.push(stepCount+1);
			}
			if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)
			{
				q.push(x);
				q.push(2*n-y+1);
				q.push(3);
				q.push(stepCount+1);
			}
			//move=1;//regular move
			for(int i=0;i<8;i++)
			{
				if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)
				{
					q.push(x+dirx[i]);
					q.push(y+diry[i]);
					q.push(1);
					q.push(stepCount+1);
				}
			}
		}
		else if(moveTyp==3)
		{
			//move=1;//regular move
			for(int i=0;i<8;i++)
			{
				if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)
				{
					q.push(x+dirx[i]);
					q.push(y+diry[i]);
					q.push(1);
					q.push(stepCount+1);
				}
			}
			//move=2//bishop
			for(int i=0;i<4;i++)
			{
				if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)
				{
					q.push(x+dx[i]);
					q.push(y+dy[i]);
					q.push(2);
					q.push(stepCount+1);
				}
			}
		}
	}
	return -1;
}
int main()
{
	int a,b;
	while(scanf("%d",&n),n)
	{
		scanf("%d%d",&stx,&sty);
		scanf("%d%d",&edx,&edy);
		memset(gr,0,sizeof(gr));
		while(scanf("%d%d",&a,&b),a,b)
		{
			gr[a][b]=1;
		}
		int ret = bfs();
		if(ret==-1)
		{
			printf("Solution doesn't exist\n");
		}
		else
		printf("Result : %d\n",ret);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <queue>

using namespace std;

int stx,sty,edx,edy;

int gr[405][405];

int dirx[8]={-2,-2,2,2,1,1,-1,-1};

int diry[8]={1,-1,1,-1,2,-2,2,-2};

int dx[4]={2,2,-2,-2};

int dy[4]={-2,2,2,-2};

int n;

int bfs()

{

queue<int> q;

int x,y;

//int visit[405][405];

//memset(visit,0,sizeof(visit));

int moveTyp=0,move;

int step=0,stepCount;

q.push(stx);q.push(sty);q.push(moveTyp);q.push(step);

if(gr[stx][sty]==1)

return -1;

else if(gr[edx][edy]==1)

return -1;

while(!q.empty())

{

x = q.front();q.pop();

y = q.front();q.pop();

moveTyp = q.front();q.pop();

stepCount = q.front();q.pop();

gr[x][y]=1;

if(x==edx && y==edy)

{

return stepCount;

}

if(moveTyp==0)

{

//move=1;//regular move

for(int i=0;i<8;i++)

{

if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)

{

q.push(x+dirx[i]);

q.push(y+diry[i]);

q.push(1);

q.push(stepCount+1);

}

//move=2//bishop

for(int i=0;i<4;i++)

{

if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)

{

q.push(x+dx[i]);

q.push(y+dy[i]);

q.push(2);

q.push(stepCount+1);

}

//move=3//teleportation

if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)

{

q.push(2*n-x+1);

q.push(y);

q.push(3);

q.push(stepCount+1);

}

if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)

{

q.push(x);

q.push(2*n-y+1);

q.push(3);

q.push(stepCount+1);

}

else if(moveTyp==1)

{

//move=2//bishop

for(int i=0;i<4;i++)

{

if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)

{

q.push(x+dx[i]);

q.push(y+dy[i]);

q.push(2);

q.push(stepCount+1);

}

//move=3//teleportation

if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)

{

q.push(2*n-x+1);

q.push(y);

q.push(3);

q.push(stepCount+1);

}

if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)

{

q.push(x);

q.push(2*n-y+1);

q.push(3);

q.push(stepCount+1);

}

else if(moveTyp==2)

{

//move=3//teleportation

if(2*n-x+1>=1 && 2*n-x+1<=2*n && gr[2*n-x+1][y]==0)

{

q.push(2*n-x+1);

q.push(y);

q.push(3);

q.push(stepCount+1);

}

if(2*n-y+1>=1 && 2*n-y+1<=2*n && gr[x][2*n-y+1]==0)

{

q.push(x);

q.push(2*n-y+1);

q.push(3);

q.push(stepCount+1);

}

//move=1;//regular move

for(int i=0;i<8;i++)

{

if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)

{

q.push(x+dirx[i]);

q.push(y+diry[i]);

q.push(1);

q.push(stepCount+1);

}

else if(moveTyp==3)

{

//move=1;//regular move

for(int i=0;i<8;i++)

{

if(x+dirx[i]>=1 && x+dirx[i]<=2*n && y+diry[i]>=1 && y+diry[i]<=2*n && gr[x+dirx[i]][y+diry[i]]==0)

{

q.push(x+dirx[i]);

q.push(y+diry[i]);

q.push(1);

q.push(stepCount+1);

}

//move=2//bishop

for(int i=0;i<4;i++)

{

if(x+dx[i]>=1 && x+dx[i]<=2*n && y+dy[i]>=1 && y+dy[i]<=2*n && gr[x+dx[i]][y+dy[i]]==0)

{

q.push(x+dx[i]);

q.push(y+dy[i]);

q.push(2);

q.push(stepCount+1);

}

return -1;

}

int main()

{

int a,b;

while(scanf("%d",&n),n)

{

scanf("%d%d",&stx,&sty);

scanf("%d%d",&edx,&edy);

memset(gr,0,sizeof(gr));

while(scanf("%d%d",&a,&b),a,b)

{

gr[a][b]=1;

}

int ret = bfs();

if(ret==-1)

{

printf("Solution doesn't exist\n");

}

else

printf("Result : %d\n",ret);

}

return 0;

}

627

Asif NaeemOctober 24, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

vector<int> vb[305];
vector<int> par;

bool bfs(int path[],int st,int ed)
{
	int visit[400];
	for(int i=0;i<400;i++)
	visit[i]=0;
	queue<int> q;
	q.push(st);
	visit[st]=1;
	int a,b;
	if(st==ed)
		return 1;
	while(!q.empty())
	{
		a = q.front();q.pop();
		if(a==ed)
		return 1;
		for(int i=0;i<vb[a].size();i++)
		{
			b =  vb[a][i];
			if(visit[b]==0)
			{
				visit[b]=1;
				q.push(b);
				path[b]=a;
			}
		}
	}
	return 0;
}

int main()
{
	int router,qry;
	int fr,to,st,ed,i;
	string str;
	while(scanf("%d",&router)!=EOF)
	{
		getchar();
		for(int II=0;II<305;II++)
		vb[II].clear();
		for(int II=0;II<router;II++)
		{
			getline(cin,str);
			i=0;
			fr=0;
			while(str[i]!='-')
			{
				fr *= 10;fr += (str[i++]-'0');
			}
			i+=1;
			to=0;
			while(i<str.size())
			{
				if(str[i]==',')
				{
					vb[fr].push_back(to);
					to=0;
					i+=1;
				}
				else
				{
					to *= 10;
					to += (str[i++]-'0');
				}
			}
			vb[fr].push_back(to);
		}
		scanf("%d",&qry);
		for(int II=0;II<qry;II++)
		{
			scanf("%d%d",&st,&ed);
			int *path = new int[router+5];
			for(int JJ=0;JJ<router+5;JJ++)
			path[JJ]=JJ;
			bool f = bfs(path,st,ed);
			if(II==0)
				printf("-----\n");
			if(!f)
			printf("connection impossible\n");
			else
			{
				//cout<<"path = "<<path[5]<<"\n";
				int cc = ed;
				par.clear();
				while(path[cc]!=cc)
				{
					par.push_back(cc);
					cc=path[cc];
				}
				par.push_back(cc);
				for(int LL=par.size()-1;LL>=0;LL--)
				printf("%d%s",par[LL],LL==0?"\n":" ");
			}
			delete path;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <cstdio>

#include <sstream>

#include <vector>

#include <string>

#include <cstring>

#include <queue>

using namespace std;

vector<int> vb[305];

vector<int> par;

bool bfs(int path[],int st,int ed)

{

int visit[400];

for(int i=0;i<400;i++)

visit[i]=0;

queue<int> q;

q.push(st);

visit[st]=1;

int a,b;

if(st==ed)

return 1;

while(!q.empty())

{

a = q.front();q.pop();

if(a==ed)

return 1;

for(int i=0;i<vb[a].size();i++)

{

b = vb[a][i];

if(visit[b]==0)

{

visit[b]=1;

q.push(b);

path[b]=a;

}

return 0;

}

int main()

{

int router,qry;

int fr,to,st,ed,i;

string str;

while(scanf("%d",&router)!=EOF)

{

getchar();

for(int II=0;II<305;II++)

vb[II].clear();

for(int II=0;II<router;II++)

{

getline(cin,str);

i=0;

fr=0;

while(str[i]!='-')

{

fr *= 10;fr += (str[i++]-'0');

}

i+=1;

to=0;

while(i<str.size())

{

if(str[i]==',')

{

vb[fr].push_back(to);

to=0;

i+=1;

}

else

{

to *= 10;

to += (str[i++]-'0');

}

vb[fr].push_back(to);

}

scanf("%d",&qry);

for(int II=0;II<qry;II++)

{

scanf("%d%d",&st,&ed);

int *path = new int[router+5];

for(int JJ=0;JJ<router+5;JJ++)

path[JJ]=JJ;

bool f = bfs(path,st,ed);

if(II==0)

printf("-----\n");

if(!f)

printf("connection impossible\n");

else

{

//cout<<"path = "<<path[5]<<"\n";

int cc = ed;

par.clear();

while(path[cc]!=cc)

{

par.push_back(cc);

cc=path[cc];

}

par.push_back(cc);

for(int LL=par.size()-1;LL>=0;LL--)

printf("%d%s",par[LL],LL==0?"\n":" ");

}

delete path;

}

return 0;

}

There is another solution using Linked List in case Router ID is not limited from 1 to 300. But for this problem this solution gets TLE.

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

struct Node{
	int number;
	Node *next;
};
struct Edge{
	int from,to;
	Edge *next;
	Edge(int f,int t);
};

Node *nodeList=0;
Edge *edgeList=0;
int IndexOfId[400];
vector<int> vb[400];
vector<int> par;

int GetNodeIndex(int num)
{
	Node *p=nodeList;
	int idx=0;
	while(p->next)
	{
		p=p->next;
		if(p->number==num)
		return idx;
		idx+=1;
	}
	p->next=new Node();
	p=p->next;
	p->number=num;
	p->next=0;
	IndexOfId[idx]=num;
	return idx;
}

Edge::Edge(int f,int t)
{
	from = f;
	to = t;
}

void init()
{
	Node *p=nodeList,*q;
	memset(IndexOfId,0,sizeof(IndexOfId));
	while(p)
	{
		q = p;
		p = p->next;
		delete q;
	}
	nodeList = new Node();
	nodeList->next=0;
	nodeList->number=-100;

	Edge *pp=edgeList,*tmp;
	while(pp)
	{
		tmp=pp;
		pp=pp->next;
		delete tmp;
	}
}

int CountNode()
{
	Node *p=nodeList->next;
	int cnt=0;
	while(p)
	{
		cnt+=1;
		p=p->next;
	}
	return cnt;
}

bool bfs(int path[],int st,int ed)
{
	int visit[400];
	for(int i=0;i<400;i++)
	visit[i]=0;
	queue<int> q;
	q.push(st);
	visit[st]=1;
	int a,b;
	if(st==ed)
		return 1;
	while(!q.empty())
	{
		a = q.front();q.pop();
		if(a==ed)
		return 1;
		for(int i=0;i<vb[a].size();i++)
		{
			b =  vb[a][i];
			if(visit[b]==0)
			{
				visit[b]=1;
				q.push(b);
				path[b]=a;
			}
		}
	}
	return 0;
}
int main()
{
	int n,m,fr,to,i;
	int a,b;
	string str;
	while(scanf("%d",&n)!=EOF)
	{
		getchar();
		init();
		for(int II=0;II<n;II++)
		{
			getline(cin,str);
			i=0;
			fr=0;
			while(str[i]!='-')
			{
				fr *= 10;fr += (str[i++]-'0');
			}
			fr = GetNodeIndex(fr);
			to=0;
			i+=1;
			while(i<str.size())
			{
				if(str[i]==',')
				{
					to = GetNodeIndex(to);
					Edge *e=new Edge(fr,to);
					e->next = edgeList;
					edgeList = e;
					to=0;
					i+=1;
				}
				else
				{
					to *= 10; to += (str[i++]-'0');
				}
			}
			to = GetNodeIndex(to);
			Edge *e=new Edge(fr,to);
			e->next = edgeList;
			edgeList = e;

		}
		int nodeCount = CountNode();
		for(int II=0;II<400;II++)
			vb[II].clear();
		Edge *tmpEdge=edgeList;
		while(tmpEdge)
		{
			a = tmpEdge->from;
			b = tmpEdge->to;
			vb[a].push_back(b);
			tmpEdge=tmpEdge->next;
		}
		scanf("%d",&m);
		for(int II=0;II<m;II++)
		{
			int st,ed;
			scanf("%d%d",&st,&ed);
			st=GetNodeIndex(st);
			ed=GetNodeIndex(ed);
			int *path = new int[nodeCount];
			for(int KK=0;KK<nodeCount;KK++)
			path[KK]=KK;
			bool f = bfs(path,st,ed);
			if(II==0)
				printf("-----\n");
			if(!f)
			printf("connection impossible\n");
			else
			{
				int cc = ed;
				par.clear();
				while(path[cc]!=cc)
				{
					par.push_back(cc);
					cc=path[cc];
				}
				par.push_back(cc);
				for(int LL=par.size()-1;LL>=0;LL--)
				printf("%d%s",IndexOfId[par[LL]],LL==0?"\n":" ");
			}
			delete path;
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

#include <iostream>

#include <cstdio>

#include <sstream>

#include <vector>

#include <string>

#include <cstring>

#include <queue>

using namespace std;

struct Node{

int number;

Node *next;

};

struct Edge{

int from,to;

Edge *next;

Edge(int f,int t);

};

Node *nodeList=0;

Edge *edgeList=0;

int IndexOfId[400];

vector<int> vb[400];

vector<int> par;

int GetNodeIndex(int num)

{

Node *p=nodeList;

int idx=0;

while(p->next)

{

p=p->next;

if(p->number==num)

return idx;

idx+=1;

}

p->next=new Node();

p=p->next;

p->number=num;

p->next=0;

IndexOfId[idx]=num;

return idx;

}

Edge::Edge(int f,int t)

{

from = f;

to = t;

}

void init()

{

Node *p=nodeList,*q;

memset(IndexOfId,0,sizeof(IndexOfId));

while(p)

{

q = p;

p = p->next;

delete q;

}

nodeList = new Node();

nodeList->next=0;

nodeList->number=-100;

Edge *pp=edgeList,*tmp;

while(pp)

{

tmp=pp;

pp=pp->next;

delete tmp;

}

int CountNode()

{

Node *p=nodeList->next;

int cnt=0;

while(p)

{

cnt+=1;

p=p->next;

}

return cnt;

}

bool bfs(int path[],int st,int ed)

{

int visit[400];

for(int i=0;i<400;i++)

visit[i]=0;

queue<int> q;

q.push(st);

visit[st]=1;

int a,b;

if(st==ed)

return 1;

while(!q.empty())

{

a = q.front();q.pop();

if(a==ed)

return 1;

for(int i=0;i<vb[a].size();i++)

{

b = vb[a][i];

if(visit[b]==0)

{

visit[b]=1;

q.push(b);

path[b]=a;

}

return 0;

}

int main()

{

int n,m,fr,to,i;

int a,b;

string str;

while(scanf("%d",&n)!=EOF)

{

getchar();

init();

for(int II=0;II<n;II++)

{

getline(cin,str);

i=0;

fr=0;

while(str[i]!='-')

{

fr *= 10;fr += (str[i++]-'0');

}

fr = GetNodeIndex(fr);

to=0;

i+=1;

while(i<str.size())

{

if(str[i]==',')

{

to = GetNodeIndex(to);

Edge *e=new Edge(fr,to);

e->next = edgeList;

edgeList = e;

to=0;

i+=1;

}

else

{

to *= 10; to += (str[i++]-'0');

}

to = GetNodeIndex(to);

Edge *e=new Edge(fr,to);

e->next = edgeList;

edgeList = e;

}

int nodeCount = CountNode();

for(int II=0;II<400;II++)

vb[II].clear();

Edge *tmpEdge=edgeList;

while(tmpEdge)

{

a = tmpEdge->from;

b = tmpEdge->to;

vb[a].push_back(b);

tmpEdge=tmpEdge->next;

}

scanf("%d",&m);

for(int II=0;II<m;II++)

{

int st,ed;

scanf("%d%d",&st,&ed);

st=GetNodeIndex(st);

ed=GetNodeIndex(ed);

int *path = new int[nodeCount];

for(int KK=0;KK<nodeCount;KK++)

path[KK]=KK;

bool f = bfs(path,st,ed);

if(II==0)

printf("-----\n");

if(!f)

printf("connection impossible\n");

else

{

int cc = ed;

par.clear();

while(path[cc]!=cc)

{

par.push_back(cc);

cc=path[cc];

}

par.push_back(cc);

for(int LL=par.size()-1;LL>=0;LL--)

printf("%d%s",IndexOfId[par[LL]],LL==0?"\n":" ");

}

delete path;

}

return 0;

}

The problem is to finding a tree from a given graph.The main challenge is that the value of the node is not provided. So adjacency matrix can not be used to solve the problem. To define a tree for a directed graph : total edges = total vertices -1;root can not be more than one,

Continue Reading “615” →

599

Asif NaeemOctober 22, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>

using namespace std;
int parent[26];
int countNodes[26];

int getparent(int n)
{
	if(parent[n]==n)
	return n;
	else
	return parent[n]=getparent(parent[n]);
}

void unite(int a,int b)
{
	parent[getparent(a)]=getparent(b);
}
int main()
{
	int t;
	string str;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		str="";
		for(int i=0;i<26;i++)
		{
			parent[i]=i;
			countNodes[i]=0;
		}
		while(getline(cin,str),str[0]!='*')
		{
			unite(str[1]-'A',str[3]-'A');
		}
		getline(cin,str);
		for(int i=0;i<str.size();i++)
		{
			if(str[i]!=',')
			countNodes[getparent(str[i]-'A')]+=1;
		}
		int tree=0,acron=0;
		for(int i=0;i<26;i++)
		{
			if(countNodes[i]>1)
			tree+=1;
			else if(countNodes[i]==1)
			acron+=1;
		}
		printf("There are %d tree(s) and %d acorn(s).\n",tree,acron);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;

int parent[26];

int countNodes[26];

int getparent(int n)

{

if(parent[n]==n)

return n;

else

return parent[n]=getparent(parent[n]);

}

void unite(int a,int b)

{

parent[getparent(a)]=getparent(b);

}

int main()

{

int t;

string str;

scanf("%d",&t);

getchar();

while(t--)

{

str="";

for(int i=0;i<26;i++)

{

parent[i]=i;

countNodes[i]=0;

}

while(getline(cin,str),str[0]!='*')

{

unite(str[1]-'A',str[3]-'A');

}

getline(cin,str);

for(int i=0;i<str.size();i++)

{

if(str[i]!=',')

countNodes[getparent(str[i]-'A')]+=1;

}

int tree=0,acron=0;

for(int i=0;i<26;i++)

{

if(countNodes[i]>1)

tree+=1;

else if(countNodes[i]==1)

acron+=1;

}

printf("There are %d tree(s) and %d acorn(s).\n",tree,acron);

}

return 0;

}

590

Asif NaeemOctober 21, 2015

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <cstdlib>

#define INF 1000000000
#define ll long long

using namespace std;
int n,k;
int flight_schedule_cost[11][11][40];//flight_schedule_cost[city][tocity][dayno]=cost of that day frm ct1 to cty 2
int periodOfCity[11][11];
ll dp[1010][15];//ll dp[day][citypath];

int kase=1;

int costFromTheCity(int day,int startCity,int destination_city)
{
	int schedulePeriod = periodOfCity[startCity][destination_city];
	int dayOfschedule = day%(schedulePeriod);
	if(dayOfschedule==0)
		dayOfschedule=schedulePeriod;
	return flight_schedule_cost[startCity][destination_city][dayOfschedule];
}
ll DP(int day,int city)
{
	ll d;
	int cost;
	dp[1][1]=0;
	for(int i=1;i<=n;i++)
		dp[2][i]= (flight_schedule_cost[1][i][1]==0?INF : flight_schedule_cost[1][i][1]);
	for(int i=3;i<=(k+1);i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int kk=1;kk<=n;kk++)
			{
				if(j==kk)
					continue;
				if(dp[i-1][kk]==INF)
					continue;
				cost = costFromTheCity(i-1,kk,j);
				if(cost==0)
					continue;
				dp[i][j] = (dp[i-1][kk]+cost < dp[i][j] ? dp[i-1][kk]+cost : dp[i][j]);
			}
		}
	}
	return dp[k+1][n];
}
int main()
{
	int dailyCost;

	while(scanf("%d%d",&n,&k),n+k)
	{
		memset(flight_schedule_cost,0,sizeof(flight_schedule_cost));
		memset(periodOfCity,0,sizeof(periodOfCity));
		memset(dp,INF,sizeof(dp));
		for(int i=0;i<1010;i++)
			for(int j=0;j<15;j++)
				dp[i][j]=INF;
		for(int start_city=1;start_city<=n;start_city++)
		{
			for(int destination_city=1;destination_city<=n;destination_city++)
			{
				if(destination_city==start_city)
				continue;
				scanf("%d",&periodOfCity[start_city][destination_city]);
				for(int dayNo=1;dayNo<=periodOfCity[start_city][destination_city];dayNo++)
				{
					scanf("%d",&dailyCost);
					flight_schedule_cost[start_city][destination_city][dayNo]=dailyCost;
				}
			}
		}
		ll tmp = DP(k+1,n);
		if(tmp!=INF)
		{
			printf("Scenario #%d\n",kase++);
			printf("The best flight costs %lld.\n\n",tmp);
		}
		else
		{
			printf("Scenario #%d\n",kase++);
			printf("No flight possible.\n\n");
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <queue>

#include <cstdlib>

#define INF 1000000000

#define ll long long

using namespace std;

int n,k;

int flight_schedule_cost[11][11][40];//flight_schedule_cost[city][tocity][dayno]=cost of that day frm ct1 to cty 2

int periodOfCity[11][11];

ll dp[1010][15];//ll dp[day][citypath];

int kase=1;

int costFromTheCity(int day,int startCity,int destination_city)

{

int schedulePeriod = periodOfCity[startCity][destination_city];

int dayOfschedule = day%(schedulePeriod);

if(dayOfschedule==0)

dayOfschedule=schedulePeriod;

return flight_schedule_cost[startCity][destination_city][dayOfschedule];

}

ll DP(int day,int city)

{

ll d;

int cost;

dp[1][1]=0;

for(int i=1;i<=n;i++)

dp[2][i]= (flight_schedule_cost[1][i][1]==0?INF : flight_schedule_cost[1][i][1]);

for(int i=3;i<=(k+1);i++)

{

for(int j=1;j<=n;j++)

{

for(int kk=1;kk<=n;kk++)

{

if(j==kk)

continue;

if(dp[i-1][kk]==INF)

continue;

cost = costFromTheCity(i-1,kk,j);

if(cost==0)

continue;

dp[i][j] = (dp[i-1][kk]+cost < dp[i][j] ? dp[i-1][kk]+cost : dp[i][j]);

}

return dp[k+1][n];

}

int main()

{

int dailyCost;

while(scanf("%d%d",&n,&k),n+k)

{

memset(flight_schedule_cost,0,sizeof(flight_schedule_cost));

memset(periodOfCity,0,sizeof(periodOfCity));

memset(dp,INF,sizeof(dp));

for(int i=0;i<1010;i++)

for(int j=0;j<15;j++)

dp[i][j]=INF;

for(int start_city=1;start_city<=n;start_city++)

{

for(int destination_city=1;destination_city<=n;destination_city++)

{

if(destination_city==start_city)

continue;

scanf("%d",&periodOfCity[start_city][destination_city]);

for(int dayNo=1;dayNo<=periodOfCity[start_city][destination_city];dayNo++)

{

scanf("%d",&dailyCost);

flight_schedule_cost[start_city][destination_city][dayNo]=dailyCost;

}

ll tmp = DP(k+1,n);

if(tmp!=INF)

{

printf("Scenario #%d\n",kase++);

printf("The best flight costs %lld.\n\n",tmp);

}

else

{

printf("Scenario #%d\n",kase++);

printf("No flight possible.\n\n");

}

return 0;

}

11734

Asif NaeemOctober 20, 2015

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
	int t,kase=1;
	string org,ans,tmp1,tmp2;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		getline(cin,ans);
		getline(cin,org);
		if(org.size()==ans.size())
		{
			bool f=0;
			for(int i=0;i<org.size();i++)
			{
				if(org[i]!=ans[i])
				{
					f=1;break;
				}
			}
			if(f)
				printf("Case %d: Wrong Answer\n",kase++);
			else
				printf("Case %d: Yes\n",kase++);
		}
		else
		{
			tmp1="";tmp2="";
			for(int i=0;i<org.size();i++)
			{
				if(org[i]!=' ')
					tmp1.append(1u,org[i]);
			}
			for(int i=0;i<ans.size();i++)
			{
				if(ans[i]!=' ')
					tmp2.append(1u,ans[i]);
			}
			if(tmp1.size()!=tmp2.size())
			{
				printf("Case %d: Wrong Answer\n",kase++);
			}
			else
			{
				bool fl=0;
				for(int i=0;i<tmp1.size();i++)
				{
					if(tmp1[i]!=tmp2[i])
					{
						fl=1;break;
					}
				}
				if(fl)
					printf("Case %d: Wrong Answer\n",kase++);
				else
					printf("Case %d: Output Format Error\n",kase++);
			}
		}
	}
	return 0;
}

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

int t,kase=1;

string org,ans,tmp1,tmp2;

scanf("%d",&t);

getchar();

while(t--)

{

getline(cin,ans);

getline(cin,org);

if(org.size()==ans.size())

{

bool f=0;

for(int i=0;i<org.size();i++)

{

if(org[i]!=ans[i])

{

f=1;break;

}

if(f)

printf("Case %d: Wrong Answer\n",kase++);

else

printf("Case %d: Yes\n",kase++);

}

else

{

tmp1="";tmp2="";

for(int i=0;i<org.size();i++)

{

if(org[i]!=' ')

tmp1.append(1u,org[i]);

}

for(int i=0;i<ans.size();i++)

{

if(ans[i]!=' ')

tmp2.append(1u,ans[i]);

}

if(tmp1.size()!=tmp2.size())

{

printf("Case %d: Wrong Answer\n",kase++);

}

else

{

bool fl=0;

for(int i=0;i<tmp1.size();i++)

{

if(tmp1[i]!=tmp2[i])

{

fl=1;break;

}

if(fl)

printf("Case %d: Wrong Answer\n",kase++);

else

printf("Case %d: Output Format Error\n",kase++);

}

return 0;

}

11934

Asif NaeemOctober 19, 2015

Have some idea about Remainder Theorem, not necessary to solve the problem but it is good to revise some theorem.

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

#define ll long long
using namespace std;


int main()
{
	int a,b,c,d,L;

	while(scanf("%d%d%d%d%d",&a,&b,&c,&d,&L))
	{
		if(a==0 && b==0 && c==0 && d==0 && L==0)
		break;
		if(a==0 && b==0 && c==0)
		{
			printf("%d\n",L);
			continue;
		}
		else if(a==0 && b==0 && c!=0)
		{
			if(c%d==0)
			printf("%d\n",L+1);
			else
			printf("%d\n",0);
			continue;
		}
		else if(a==0 && b!=0 && c!=0)
		{
			if(b%d==0 && c%d==0)
			{
				printf("%d\n",L+1);
			}
			else if(b%d==0 && c%d!=0)
			printf("%d\n",0);
			continue;
		}
		else if(b==0 && a!=0 && c!=0)
		{
			if(a%d==0 && c%d==0)
			{
				printf("%d\n",L+1);
			}
			else if(a%d==0 && c%d!=0)
			printf("%d\n",0);
			continue;
		}
		ll res;
		ll cnt=0;
		for(int i=0;i<=L;i++)
		{
			res = a*i*i+b*i+c;
			if(res%d==0)
			cnt+=1;
		}
		printf("%lld\n",cnt);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

#define ll long long

using namespace std;

int main()

{

int a,b,c,d,L;

while(scanf("%d%d%d%d%d",&a,&b,&c,&d,&L))

{

if(a==0 && b==0 && c==0 && d==0 && L==0)

break;

if(a==0 && b==0 && c==0)

{

printf("%d\n",L);

continue;

}

else if(a==0 && b==0 && c!=0)

{

if(c%d==0)

printf("%d\n",L+1);

else

printf("%d\n",0);

continue;

}

else if(a==0 && b!=0 && c!=0)

{

if(b%d==0 && c%d==0)

{

printf("%d\n",L+1);

}

else if(b%d==0 && c%d!=0)

printf("%d\n",0);

continue;

}

else if(b==0 && a!=0 && c!=0)

{

if(a%d==0 && c%d==0)

{

printf("%d\n",L+1);

}

else if(a%d==0 && c%d!=0)

printf("%d\n",0);

continue;

}

ll res;

ll cnt=0;

for(int i=0;i<=L;i++)

{

res = a*i*i+b*i+c;

if(res%d==0)

cnt+=1;

}

printf("%lld\n",cnt);

}

return 0;

}

11936

Asif NaeemOctober 19, 2015

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>

using namespace std;

int main()
{
	int n,a,b,c;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d%d",&a,&b,&c);
		bool OK=1;
		if(a>=(b+c))
		OK=0;
		if(b>=(a+c))
		OK=0;
		if(c>=(a+b))
		OK=0;
		if(OK)
		printf("OK\n");
		else
		printf("Wrong!!\n");
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <sstream>

#include <string>

using namespace std;

int main()

{

int n,a,b,c;

scanf("%d",&n);

while(n--)

{

scanf("%d%d%d",&a,&b,&c);

bool OK=1;

if(a>=(b+c))

OK=0;

if(b>=(a+c))

OK=0;

if(c>=(a+b))

OK=0;

if(OK)

printf("OK\n");

else

printf("Wrong!!\n");

}

return 0;

}

Month: October 2015

710

677

633

627

615

599

590

11734

11934

11936

Archives

Categories