0514 0515

0514 Quality Checking

三つの部品を組み合わせたときに、それが正常に動作しない場合どれか少なくとも一つが壊れているとする。逆に言えば部品の組み合わせが正しく動くならばその部品はすべて正常である。さまざまな組み合わせとその結果が与えられたとき、各パーツが正常に動くかどうかを出力せよ。

方針

少なくとも正常動作するパーツは確定するので、配列をうまく利用して分類する。

コード

#include <cstdio>
#include <vector>
using namespace std;
#define PB push_back
int main() {
	int a,b,c;
	while(scanf("%d %d %d",&a,&b,&c)) {
		if (a==0&&b==0&&c==0) break;
		vector<int> part(a+b+c,2);
		vector<vector<int> > set;
		int N; scanf("%d",&N);
		int i,j,k,l;
		for (int cnt=0; cnt<N; cnt++) {
			scanf("%d %d %d %d",&i,&j,&k,&l);
			if (l==1) {
				part[i-1]=part[j-1]=part[k-1]=1;
			} else {
				vector<int> tmp(3);
				tmp[0]=i-1; tmp[1]=j-1; tmp[2]=k-1;
				set.PB(tmp);
			}
		}
		for (int cnt=0; cnt<set.size(); cnt++) {
			int n=part[set[cnt][0]], m=part[set[cnt][1]], p=part[set[cnt][2]];
			if (n==1&&m==1) part[set[cnt][2]]=0;
			if (n==1&&p==1) part[set[cnt][1]]=0;
			if (p==1&&m==1) part[set[cnt][0]]=0;
		}
		for (int cnt=0; cnt<a+b+c; cnt++) printf("%d\n",part[cnt]);
	}
}

0515 SchoolRoad

(1,1)にある人の家がある。そして(n,m)に学校がある。そして道は格子状に並んでいて、交差点が格子点になることを保証する。このとき、工事で通れない交差点を与えられたら、そこを通らずに学校に行く道は何通りあるか？ただし、すべて最短経路を通るものとする。

方針

なんとなくコンビネーションつかって解けそうな気がしますが、今回の場合はそれぞれの座標への行き方を二次配列で管理して求めることが出来ます。あえて漸化式を書くとすれば次のようになります。

map[0][0]=1
map[i][j]=map[i-1][j]+map[i][j-1](i-1≧0∧j-1≧0)
map[i][j]=map[i-1][j](i-1≧0)
map[i][j]=map[i][j-1](j-1≧0)

でもまぁこれは漸化式たてるものでもないですね(^_^;)

コード

#include <cstdio>
using namespace std;
int main() {
	int a,b,n,x,y;
	while (scanf("%d %d",&a,&b)) {
		if (a==0&&b==0) break;
		scanf("%d",&n);
		int map[a][b];
		for (int i=0; i<a; i++) for (int j=0; j<b; j++) map[i][j]=-1;
		for (int i=0; i<n; i++) {
			scanf("%d %d",&x,&y);
			map[x-1][y-1]=0;
		}
		for (int i=0; i<a; i++) {
			for (int j=0; j<b; j++) {
				if (i==0&&j==0) {
					map[i][j]=1;
				} else if (map[i][j]==-1) {
					map[i][j]=0;
					if (i-1>=0) map[i][j]+=map[i-1][j];
					if (j-1>=0) map[i][j]+=map[i][j-1];
				}
			}
		}
		printf("%d\n",map[a-1][b-1]);
	}
}