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; } |
Bài viết liên quan
- BCCOM spoj PTIT – Số nén tối giản
- BCSEQ1 PTIT spoj – Đoạn số có tổng bằng nhau
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- BCMULONE spoj PTIT -Nhân 1
- BCACM11D spoj PTIT – Đường nguyên tố
- PTIT127C spoj ptit- Bố trí phòng họp
- PTIT013K spoj PTIT – SỐ NGUYÊN HỆ CƠ SỐ ACM
- PTIT013A spoj PTIT – Số may mắn