PKU演習問メモ(7/3) - simezi

ICPC国内予選の記事は後ほど。

No.	問題名	問題の種類および解法	難易度
1350	Cabric Number Problem	実装	★★☆☆☆
2472	106 miles to Chicago	ダイクストラ法	★★☆☆☆

1350|Cabric Number Problem

問題概要

「全ての桁が同一」ではない4桁の数が与えられたとき、次のプロセスを繰り返すことでその数は0または6174になる。

数字を大きい順に並べる
数字を小さい順に並べる。数字に0が含まれていた場合3桁以下になりうる
(1)の数-(2)の数を求める
(3)を新たに与えられた数として(1)からプロセスを繰り返す。

「全ての桁が同一」ではない4桁の数字が与えられたとき、数が0または6174になるまでにかかるステップの数を求め、指定されたフォーマットで出力せよ。そうではない場合は"No!!"を出力せよ。

解法

与えられた条件にしたがって実装すれば良いのだがハマりポイントが多い。
ソート後の数では、先頭の0を出力してはならないし、入力には4桁以外の数も与えられうる。また6174が与えられたときは0を出力するなどである。

ソースコード

string num,sml;

int ton(string &s){
	int ret=0;
	rep(i,s.size())ret*=10,ret+=s[i]-'0';
	return ret;
}
string toa(int n){
	stringstream ss;
	ss<<n;
	return ss.str();
}

int main()
{
	while(cin>>num,num!="-1")
	{
		printf("N=%s:\n",num.c_str());
		if(num.size()!=4||num[0]==num[1]&&num[1]==num[2]&&num[2]==num[3])
		{
			printf("No!!\n"); continue;
		}
		
		int cnt=0;
		while(num!="6174"&&num!="0")
		{
			cnt++;
			sml=num;
			sort(all(num),greater<char>());
			sort(all(sml));
			int nxtnum=ton(num)-ton(sml);
			
			printf("%d-%d=%d\n",ton(num),ton(sml),nxtnum);
			num=toa(nxtnum);
		}
		printf("Ok!! %d times\n",cnt);
	}
	return 0;
}

2472 106 miles to Chicago

問題概要

n個の都市間をm本の道路がつないでいる。
m本の道路は双方向に通行可能で、それぞれ両端の都市の番号およびその道路を無事通過できる確率が与えられる。

このときスタートの都市からゴールの都市まで最も高い確率で辿り着く経路における確率を求めよ。

解法

ある都市まで辿り着く確率をその都市におけるコストとみればダイクストラ法が使える。

ソースコード

int n,m;
double p[100][100];
double mx[100];

int main()
{
	while(cin>>n,n)
	{
		rep(i,n)rep(j,n)p[i][j]=0;
		rep(i,n)mx[i]=0;
		
		cin>>m;
		rep(i,m)
		{
			int a,b,c; cin>>a>>b>>c; a--; b--;
			p[a][b]=p[b][a]=c/100.0;
		}
		mx[0]=1;
		priority_queue<pair<double,int> > Q; Q.push(mp(1,0));
		while(!Q.empty())
		{
			int cur=Q.top().second; double cp=Q.top().first; Q.pop();
			
			if(mx[cur]<cp)continue;
			if(cur==n-1)break;
			
			rep(i,n)if(p[cur][i]>0)
			{
				double np=cp*p[cur][i];
				if(mx[i]>=np)continue;
				mx[i]=np; Q.push(mp(np,i));
			}
		}
		
		printf("%.6f percent\n",mx[n-1]*100);
	}
	return 0;
}