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

「1170~1180」の編集履歴(バックアップ)一覧に戻る

1170~1180 - (2011/09/06 (火) 08:20:55) の編集履歴(バックアップ)



1172

チェビシフの不等式という数式が成立することを確認する問題。
解法
エラトステネスの篩で素数を作って下からtに足しこむだけです。
後はtにアクセスして条件を満たす素数の数を計算します。

#include<stdio.h>
#include<string.h>
#include<math.h>
const int m=250000;
int t[m];
void setSo(){
memset(t,0,m*4);
t[2]=1;
for(int i=3;i<sqrt(m);i+=2){
	if(t[m]!=0) continue;
	for(int j=i*3;j<m;j+=i*2){
		t[j]=1;
	}
}
for(int i=3;i<m;i++){
	t[i]=t[i-1]+(i%2==0?0:!t[i]);
}
}
int main(){
setSo();
int n;
while(1){
	scanf("%d",&n);
	if(n==0) break;
	printf("%d\n",t[2*n]-t[n]);
}
}






1173 The Balance of the World

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1173
与えられた文章中の()と[]がきちんと対応しているかを調べる問題。
解法
スタックに積んだりおろしたりするだけです。


#include<stdio.h>
#include<stack>
#include<string.h>
int main(){
char text[102],size,t;
std::stack<char> sta;
while(scanf("%[^\n]",text),!(strlen(text)==1 && text[0]=='.')){
	scanf("%c",&t);
	bool allOK=true;
	size=strlen(text);		
	for(int i=0;i<size;i++){
		t=text[i];
		if(t==')' && (sta.empty() || sta.top()!='(')){
			allOK=false;
			break;
		}else if(t==']' &&(sta.empty() || sta.top()!='[')){
			allOK=false;
			break;
		}
		if(t=='(' || t=='['){
			sta.push(t);
		}
		if(t==')' || t==']'){
			sta.pop();
		}
	}
	if(allOK==true && sta.empty()){
		printf("yes\n");
	}else{
		printf("no\n");
	}
	while(!sta.empty()){
		sta.pop();
	}
}
}






1174 Identically Colored Panels Connection

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1174&lang=jp
升目に区切られたボードの色を一定のルールで塗り替えていったときどこまで同じ色をつなげられるかという問題。

解法
2重再帰で探索します。
saikiで色を塗り替えられる範囲を調べsaiki2で次の色塗り替えを試します。
最後にcolorCountで同色でつながっているマスの数をチェックします。
colorCount関数とsaiki関数は似ているので一つの関数にまとめられるかもしれません。


#include<stdio.h>
#include<string.h>
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
int h,w,c,ans;
void saiki(int map[8][8],int moveOKs[8][8],int x,int y,int nowColor,int nextColor){
int nx,ny;
moveOKs[y][x]=1;
map[y][x]=nextColor;
for(int i=0;i<4;i++){
	nx=x+dxs[i];
	ny=y+dys[i];
	if(nx<0 || w<=nx || ny<0 || h<=ny || moveOKs[ny][nx]==1) continue;
	if(map[ny][nx]==nowColor){
		saiki(map,moveOKs,nx,ny,nowColor,nextColor);
	}
}
}
void colorCount(int map[8][8],int moveOKs[8][8],int x,int y,int& count){
   int nx,ny;
   count++;
   moveOKs[y][x]=1;
   for(int i=0;i<4;i++){
       nx=x+dxs[i];
       ny=y+dys[i];
       if(nx<0 || w<=nx || ny<0 || h<=ny || moveOKs[ny][nx]==1 || map[ny][nx]!=c) continue;
       colorCount(map,moveOKs,nx,ny,count);
   }
}
void saiki2(int deep,int map[8][8]){
int nextMap[8][8],moveOKs[8][8],count=0;
if(deep>=4){
	memcpy(nextMap,map,8*8*4);
	memset(moveOKs,0,8*8*4);
	saiki(nextMap,moveOKs,0,0,map[0][0],c);
       memset(moveOKs,0,8*8*4);
       colorCount(nextMap,moveOKs,0,0,count);
	ans=ans>count?ans:count;
	return ;
}else{
	for(int i=1;i<7;i++){
		memcpy(nextMap,map,8*8*4);
	    memset(moveOKs,0,8*8*4);
           if(map[0][0]==i) continue;
		saiki(nextMap,moveOKs,0,0,map[0][0],i);
		saiki2(deep+1,nextMap);
	}
}
}
void setMap(){
int map[8][8];
for(int i=0;i<h;i++){
	for(int j=0;j<w;j++){
		scanf("%d",&map[i][j]);
	}
}
ans=0;
saiki2(0,map);
printf("%d\n",ans);
}
int main(){
while(1){
	scanf("%d %d %d",&h,&w,&c);
	if(w==0 && h==0 && c==0) break;
	setMap();
}
}