※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ1151~1160」の編集履歴(バックアップ)一覧はこちら

AOJ1151~1160」の最新版変更点

追加された行は青色になります。

削除された行は赤色になります。

 *aoj1156 Twirling Robot
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156
 
 動的計画法で解ける簡単な問題。
 普通に解くと少し遅いので優先順位付きキューとメモ化を使って気持ち高速化して解く。
 平均的な速度とメモリ使用量で解けた。
+方向転換の命令を使った場合使わなかった場合で後はキューが勝手にコスト順でソートしながら幅優先探索するだけ。
 
 
  #include<stdio.h>
  #include<queue>
  struct point{
 	int x,y,a,cost;
 	bool operator<(const point& p)const{
 		return cost>p.cost;
 	}
  };
  bool calc(){
 	int map[31][31];
 	int arrowChange[5][4]={	{0,1,2,3},
 				{3,0,1,2},
 				{2,3,0,1},
 				{1,2,3,0},
 				{4,4,4,4}};
 	int dxs[5]={1,0,-1,0,0};
 	int dys[5]={0,-1,0,1,0};
 	int colSize,rowSize;
 	int memo[31][31][5];
 	int mymax=1000000;	
 	scanf("%d %d",&colSize,&rowSize);
 	if(rowSize==0&&colSize==0)return false;
 	for(int r=0;r<rowSize;r++){
 		for(int c=0;c<colSize;c++){
 			scanf("%d",&map[r][c]);
 			for(int k=0;k<5;k++)memo[r][c][k]=mymax;
 		}
 	}
 	int costs[4];
 	for(int i=0;i<4;i++)scanf("%d",&costs[i]);
 	memo[0][0][0]=0;
 	std::priority_queue<point> points;
 	point p,nextP;
 	p.x=p.y=p.a=p.cost=0;
 	points.push(p);
 	while(points.empty()==false){
 		p=points.top();
 		//printf("\n(%d %d %d)",p.x,p.y,p.cost);
 		if(p.y==rowSize-1&&p.x==colSize-1){
 			printf("%d\n",p.cost);
 			break;
 		}		
 		points.pop();
 		for(int i=0;i<4;i++){
 			//iは方向転換の命令
 			int nextCost=p.cost;
 			if(map[p.y][p.x]!=i){
 				nextCost+=costs[i];
 			}
 			int nextArrow=arrowChange[i][p.a];
 			nextP.y=p.y+dys[nextArrow];
 			nextP.x=p.x+dxs[nextArrow];
 			nextP.a=nextArrow;
 			nextP.cost=nextCost;
 			//printf("<%d %d %d>",nextP.x,nextP.y,nextP.cost);
 			if(nextP.x<0||nextP.x>=colSize||nextP.y<0||nextP.y>=rowSize)continue;
 			if(nextP.cost>=memo[nextP.y][nextP.x][nextP.a])continue;
 			memo[nextP.y][nextP.x][nextP.a]=nextP.cost;
 			points.push(nextP);
 		}
 	}
 	return true;
  }
  int main(){
 	while(calc()){
+	}
+ }
+
+
+
+
+
+
+
+*1159 Next Mayor
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1159
+ちょっとした小石取りゲームをシミュレートする問題。
+数式を使うのが一番賢いのだろうけど、そんな方法を思いつきそうもなかったので問題で指定されたルール通り愚直に実装。
+賢い方法?なにそれ。
+
+
+ #include<stdio.h>
+ #include<string.h>
+ void calc(int n,int p){
+	int memo[51],count,p1=0,max=p;
+	memset(memo,0,sizeof(memo));
+	while(1){
+		if(p==0){
+			p=memo[p1];
+			memo[p1]=0;
+		}else{
+			memo[p1]++;
+			p--;
+		}
+		if(memo[p1]==max)break;
+		p1=(p1+1)%n;
+	}
+	printf("%d\n",p1);
+ }
+ int main(){
+	int n,p;
+	while(1){
+		scanf("%d %d",&n,&p);
+		if(n==0&&p==0)break;
+		calc(n,p);
 	}
  }