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:

  1. X không chứa chữ số 0 hoặc 1
  2. 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

 

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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *