1170～1180 - c21coterie @ ウィキ

---

1172　Chebyshev's Theorem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1172&lang=jp
チェビシフの不等式という数式が成立することを確認する問題。
解法
エラトステネスの篩で素数を作って下から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
升目に区切られたボードの色を一定のルールで塗り替えていったときどこまで同じ色をつなげられるかという問題。

解法
２重再帰で探索します。
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();
}
}

1179　Millennium

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1179&lang=jp
独特な暦を利用する国で与えられた日付から１０００年１月１日まで何日あるか答える問題。
数式をかなり縮めたつもりがコードの短さで２位だった。
最近コードの短さかコード実行速度で一位を抜けるかが時折視界に入ってくるようになった。
ほとんどが0：00：00になる問題はいいとして、コード実行速度にバラツキがある問題では何とかいろいろな問題で一位を狙いたいものである。

#include<stdio.h>
int main(){
int ys[3]={195,390,590};
int n,y,m,d,ans;
scanf("%d",&n);
while(n--){
	scanf("%d %d %d",&y,&m,&d);
	ans=ys[2]*((y-1)/3)+ys[(y-1)%3]-195+(y%3!=0)*5;
	ans+=(y%3==0)*(m-1)*20+(y%3!=0)*((m-1)*20-(m-1)/2)+d;
	printf("%d\n",196476-ans);
}
}

流石に上は10分で書いたコード。
一晩寝たらあらがたくさん見つかったのでコードの短さ一位を狙ってコードを短縮してみる。
相変わらず一位が意味不明な短さである。
ここから５０文字削れるらしい。
よくわからない、、、

#include<stdio.h>
int main(){
int n,y,m,d;
scanf("%d",&n);
while(n--){
	scanf("%d %d %d",&y,&m,&d);
	printf("%d\n",196471-((y-1)/3*590+(y-1)%3*195+(m-1)*20-(m-1)/2*(y%3!=0)+d));
}
}

1180 Recurring Decimals

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1180
数字をそろえて並べ替えて最大値と最小値を作りその差を求めることを繰り返していく時、前に出た数字が出てくるのは何回目か求める問題。

簡単な問題なので手抜き実装で十分通ります。
この問題桁数が小さいので簡単ですが、数百ケタとかになったらちょっと特殊な処理が要りますね。

#include<stdio.h>
#include<map>
#include<string.h>
void calc(int a,int l){
std::map<int,int> memo;
int b,c,nums[10],no=0;
while(1){
	memset(nums,0,sizeof(nums));
	if(memo.find(a)!=memo.end())break;
	memo[a]=no;
	for(int i=0;i<l;i++){
		nums[a%10]++;
		a/=10;
	}
	int count=0;
	b=c=0;
	//最小値を求める
	for(int i=0;i<10;i++){
		for(int j=0;j<nums[i];j++){
			b*=10;
			b+=i;
		}
	}
	//最大値を求める
	for(int i=9;i>=0;i--){
		while(nums[i]--){
			c*=10;
			c+=i;
			count++;
		}
	}
	for(int i=count;i<l;i++)c*=10;
	a=c-b;
	//printf("%d\n",a);
	no++;
}
printf("%d %d %d\n",memo[a],a,no-memo[a]);
}
int main(){
int a,l;
while(1){
	scanf("%d %d",&a,&l);
	if(a==0&&l==0)break;
	calc(a,l);
}
}