zoj 3327 Friend Number

zoj 3327 Friend Number

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<queue>#define maxn 310using namespace std;string s;int prime[20];void get(int x){ if(x==9)prime[3]+=2; else if(x==8)prime[2]+=3; else if(x==7)prime[7]++; else if(x==6)prime[2]++,prime[3]++; else if(x==5)prime[5]++; else if(x==4)prime[2]+=2; else if(x==3)prime[3]++; else if(x==2)prime[2]++;}bool can(int x){ if(x==9&′[3]>=2) { prime[3]-=2; return 1; } else if(x==8&′[2]>=3) { prime[2]-=3; return 1; } else if(x==7&′[7]>=1) { prime[7]--; return 1; } else if(x==6&′[2]>=1&′[3]>=1) { prime[2]--,prime[3]--; return 1; } else if(x==5&′[5]>=1) { prime[5]--; return 1; } else if(x==4&′[2]>=2) { prime[2]-=2; return 1; } else if(x==3&′[3]>=1) { prime[3]--; return 1; } else if(x==2&′[2]>=1) { prime[2]--; return 1; } return 0;}int change(){ if(prime[3]>=2) { prime[3]-=2; return 9; } if(prime[2]>=3) { prime[2]-=3; return 8; } if(prime[7]>=1) { prime[7]--; return 7; } if(prime[2]>=1&′[3]>=1) { prime[2]--,prime[3]--; return 6; } if(prime[5]>=1) { prime[5]--; return 5; } if(prime[2]>=2) { prime[2]-=2; return 4; } if(prime[3]>=1) { prime[3]--; return 3; } if(prime[2]>=1) { prime[2]--; return 2; } return 1;}void solve(){ int i,j; memset(prime,0,sizeof(prime)); int ff=0; for(i=0; i<s.size(); i++) { get(s[i]-'0'); int flag=0; for(j=s[i]-'0'+1; j<=9; j++) { if(can(j)) { flag=1; break; } } if(flag) { ff=1; s[i]=j+'0'; break; } } if(ff) { int tt=i; for(i=0; i<tt; i++) { s[i]=change()+'0'; } } else { s+="1"; for(i=0; i<s.size()-1; i++) { s[i]=change()+'0'; } }}bool find_zero(int& num){ int i,j; int flag=0; for(i=0; i<s.size(); i++) { if(s[i]=='0') { num++; flag=1; } } return flag;}int main(){ int i,j; int T; scanf("%d",&T); while(T--) { cin>>s; reverse(s.begin(),s.end()); if(s.size()==1) { cout<<1<<s[0]<<endl; continue; } int num=0; if(!find_zero(num)) { solve(); } else { if(num==1&&s[0]=='0') { for(i=1; i<s.size(); i++) { if(s[i]=='9') { s[i]='0'; } else { s[i]++; break; } } if(s[s.size()-1]=='0') { s+="1"; } } else { for(i=0; i<s.size(); i++) { if(s[i]=='9') { s[i]='0'; } else { s[i]++; break; } } } } reverse(s.begin(),s.end()); cout<<s<<endl; } return 0;}