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à ...
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
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | 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.
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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #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; } |
