「CF516A」Drazil and Factorial
Drazil is playing a math game with Varda.
Let’s define 
for positive integer x as a product of factorials of its digits. For example, 
.
First, they choose a decimal number a consisting of n digits that contains at least one digit larger than 1. This number may possibly start with leading zeroes. Then they should find maximum positive number x satisfying following two conditions:
1. x doesn’t contain neither digit 0 nor digit 1.
2. = 
.
Help friends find such number.
The first line contains an integer n (1 ≤ n ≤ 15) — the number of digits in a.
The second line contains n digits of a. There is at least one digit in a that is larger than 1. Number a may possibly contain leading zeroes.
Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.
|
1 2 |
4 1234 |
|
1 |
33222 |
|
1 2 |
3 555 |
|
1 |
555 |
In the first case, 
题解
定义函数F(a) 为a的数位阶乘乘积。例如 F(135) = 1! * 3! * 5! 。求 max{x}，F(x) = F(a)，且组成 x 的数字中没有0和1
质因数分解以后按素数贪心即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n; int fac[25],t[10]; char ch[25]; void solve(int num,int val) { for(int x=2;x*x<=num;x++) { while(num%x==0)num/=x,t[x]+=val; } if(num>1)t[num]+=val; } int main() { fac[1]=1; for(int i=2;i<=9;i++)fac[i]=fac[i-1]*i; n=read(); scanf("%s",ch+1); for(int i=1;i<=n;i++) solve(fac[ch[i]-'0'],1); while(t[7]!=0)solve(fac[7],-1),printf("7"); while(t[5]!=0)solve(fac[5],-1),printf("5"); while(t[3]!=0)solve(fac[3],-1),printf("3"); while(t[2]!=0)solve(fac[2],-1),printf("2"); return 0; } |
OI 课件=>
