P151PROA spoj , CF #292 (Div. 2) C. Drazil and Factorial

Nguồn đề bài:

http://codeforces.com/problemset/problem/515/C

http://www.spoj.com/PTIT/problems/P151PROA/

1. Đề bài P151PROA spoj CF292

Codeforces Round #292 (Div. 2) – C. Drazil and Factorial

Axe chơi một trò chơi với Lina.
Họ định nghĩa hàm F(x) với số x nguyên dương là tích giai thừa các chữ số của x.

Ví dụ F(135) = 1! * 3! * 5! = 720.

Đầu tiên, họ chọn một số a có n chữ số và có ít nhất một chữ số lớn hơn 1, có thể có chữ số không ở đầu. Sau đó họ tìm một số nguyên dương x lớn nhất thỏa mãn:

X không chứa chữ số 0 hoặc 1
F(x) = F(a)

Hãy giúp Axe và Lina tìm ra được số đó.

Input

Dòng đầu tiên chứa số bộ test T (T < 100).

Mỗi test gồm một dòng chứa số n và số a (1 <= n <= 15).

Output

In ra kết quả mỗi test trên một dòng là số lớn nhất tìm được.

Example

Input:
1
4 1234

Output:
33222

2. Hướng dẫn giải

– Bạn phân tích các giai thừa ra như sau. và đó chính là kết quả của bài toán. Nhưng đề bài yêu cầu là tìm số lớn nhất. nên bạn phải ưu tiên nhưng số lớn nhất đứng đầu.

//1! = 0! = 1

//2! = 2!

//3! = 3!

//4! = 3! * 2! * 2!

//5! = 5!

//6! = 5! * 3!

//7! = 7!

//8! = 7! * 2! * 2! * 2!

//9! = 7! * 3! * 3! * 2!

3. Code tham khảo

code cho bài P151PROA spoj

const   fi='';
type    data=longint;
var
        f:text;
        DD:array[0..10] of data;
        n,A,test:data;
        s:ansistring;
procedure xuli;
var     i,j:data;
begin
        fillchar(dd,sizeof(dd),0);
        for i:=1 to n do
                begin
                        case s[i] of
                        '2': inc(dd[2]);
                        '3': inc(dd[3]);
                        '4':    begin
                                        inc(dd[3]);
                                        inc(dd[2],2);
                                end;
                        '5': inc(dd[5]);
                        '6':    begin
                                        inc(dd[5]);
                                        inc(dd[3]);
                                end;
                        '7': inc(dd[7]);
                        '8':    begin
                                        inc(dd[7]);
                                        inc(dd[2],3);
                                end;
                        '9':
                                begin
                                        inc(dd[2]);
                                        inc(dd[3],2);
                                        inc(dd[7]);
                                end;
                        end;
                end;
        for i:=9 downto 2 do
                for j:=1 to dd[i] do
                        write(i);
        writeln;
end;

procedure docfile;
var     i,j:data;
        c:char;
begin
        assign(f,fi); reset(f);
        readln(f,test);
        for i:=1 to test do
                begin
                        read(f,n,c);
                        readln(f,s);
                        xuli;
                end;
        close(f);
end;
begin
        docfile;

end.

lưu ý code bằng C++ dưới đây không dùng để submit P151PROA spoj, vì code này nhập vào 1 test duy nhất.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#define PI acos(-1.0)
const int  inf =  (1<<30) - 10;
using namespace std;

int vis[11];

int main()
{
    int n;
    char str[100];
    for(int i = 0;i < 11; ++i)
        vis[i] = 0;
    cin>>n;
    scanf("%s",str);
    for(int i = 0;i < n; ++i)
    {
        if(str[i] == '2')
        {
            vis[2]++;
        }
        else if(str[i] == '3')
        {
            vis[3]++;
        }
        else if(str[i] == '4')
        {
            vis[3]++;
            vis[2] = vis[2] + 2;
        }
        else if(str[i] == '5')
        {
            vis[5]++;
        }
        else if(str[i] == '6')
        {
            vis[5]++;
            vis[3]++;
        }
        else if(str[i] == '7')
        {
            vis[7]++;
        }
        else if(str[i] == '8')
        {
            vis[7]++;
            vis[2] = vis[2] + 3;
        }
        else if(str[i] == '9')
        {
            vis[7]++;
            vis[3] = vis[3] + 2;
            vis[2]++;
        }
    }
    for(int i = 10;i >= 0; --i)
    {
        if(vis[i])
        {
            while(vis[i])
            {
                cout<<i;
                vis[i]--;
            }
        }
    }
    cout<<endl;
    return 0;
}