Codeforces #292 Div1 A. Drazil and Factorial

CF292に参加。いつも通りABC早解き+Hackで良い順位。
ぼちぼちDを解かないとレートが上がりにくくなるね。
http://codeforces.com/contest/516/problem/A

問題

正の整数nに対し、F(n)はnが10進数でabcde...と表現されるときa!+b!+c!+....となる関数とする。

nが与えられるので、以下の条件を満たす最大のxを答えよ。

• F(x)=F(n)
• xの各桁は2以上である。

解法

当然桁数が多いxを求めるのが良い。
1桁の整数aを考えると、aが合成数の場合、以下のような関係がある。

• F(4)=4!=F(322)
• F(6)=6!=F(53)
• F(8)=8!=F(7222)
• F(9)=9!=F(7332)
• aが素数の場合、a!はa未満の数字を何桁連ねても作れない。

よってn中の4,6,8,9を322,53,7222,7332に置き換えたうえで、各桁の数値を大きい順位並び替えればよい。

int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) {
		if(S[i]=='2') s+="2";
		if(S[i]=='3') s+="3";
		if(S[i]=='4') s+="322";
		if(S[i]=='5') s+="5";
		if(S[i]=='6') s+="53";
		if(S[i]=='7') s+="7";
		if(S[i]=='8') s+="7222";
		if(S[i]=='9') s+="7332";
	}
	sort(s.begin(),s.end());
	reverse(s.begin(),s.end());
	cout<<s<<endl;
}

まとめ

シンプルで面白い問題。
Div1Aとしては手ごろだね。