CodeForces 515C. Drazil and Factorial

Drazil is playing a math game with Varda.

Let's define $\text{[math]}$ for positive integer x as a product of factorials of its digits. For example, $\text{[math]}$ .

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. $\text{[math]}$ = $\text{[math]}$ .

Help friends find such number.

Input

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

Output a maximum possible integer satisfying the conditions above. There should be no zeroes and ones in this number decimal representation.

Sample test(s)

Input

4
1234

Output

Input

3
555

Output

Note

In the first case, $\text{[math]}$

真的说，这道题目是比较简单的，只是我的想法有点问题。

我做的过程太过于复杂了！在中间操作过程已经使结果超过 long long

而JS相当于在中间过程有简单的优化，是我没想到的，我把每个数还原的过于简单了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <ctype.h>
 7 using namespace std;
 8 #define LL long long
 9 
10 int main()
11 {
12     int n;
13     char num[20];
14     int cnt[10] = {0};
15     int bit[100000];
16     while(scanf("%d%*c", &n) != EOF)
17     {
18         int tag = 0;
19         for(int i = 0; i < n; i++)
20         {
21             scanf("%c", &num[i]);
22             cnt[num[i] - '0']++;
23         }
24 
25         for(int i = 0; i < n; i++)
26         {
27             if(cnt[9] && num[i] == '9')
28             {
29                 bit[tag++] = 7;
30                 bit[tag++] = 3;
31                 bit[tag++] = 3;
32                 bit[tag++] = 2;
33                 cnt[9]--;
34             }
35             else if(cnt[8] && num[i] == '8')
36             {
37                 bit[tag++] = 7;
38                 bit[tag++] = 2;
39                 bit[tag++] = 2;
40                 bit[tag++] = 2;
41                 cnt[8]--;
42             }
43             else if(cnt[7] && num[i] == '7')
44             {
45                 bit[tag++] = 7;
46                 cnt[7]--;
47             }
48             else if(cnt[6] && num[i] == '6')
49             {
50                 bit[tag++] = 5;
51                 bit[tag++] = 3;
52                 cnt[6]--;
53             }
54             else if(cnt[5] && num[i] == '5')
55             {
56                 bit[tag++] = 5;
57                 cnt[5]--;
58             }
59             else if(cnt[4] && num[i] == '4')
60             {
61                 bit[tag++] = 3;
62                 bit[tag++] = 2;
63                 bit[tag++] = 2;
64                 cnt[4]--;
65             }
66             else if(cnt[3] && num[i] == '3')
67             {
68                 bit[tag++] = 3;
69                 cnt[3]--;
70             }
71             else if(cnt[2] && num[i] == '2')
72             {
73                 bit[tag++] = 2;
74                 cnt[2]--;
75             }
76         }
77         sort(bit, bit+tag);
78         for(int i = tag-1; i >= 0; i--)
79         {
80             cout << bit[i];
81         }
82         cout << endl;
83     }
84     return 0;
85 }

View Code