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/

Nội dung bài viết

1. Đề bài P151PROA spoj CF292
2. Hướng dẫn giải
3. Code tham khảo

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.

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;

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;
}

#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;

}

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

1. Đề bài P151PROA spoj CF292

Input

Output

Example

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

3. Code tham khảo

Bài viết liên quan

Trả lời Hủy