| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT134H - Sắp xếp xen kẽ |
Bố của Tí là một nghệ nhân đồ mỹ nghệ. Công việc chính của ông là làm các pho tượng bằng gỗ. Tí rất thích thú với những sản phẩm của bố mình. Cậu thường bảo bố đồ chơi cho mình.
Tí sắp xếp các tượng gỗ của mình theo 1 hàng, và cậu thích sắp xếp xen kẽ theo chiều cao, tức là một tượng gỗ có chiều cao cùng nhỏ hơn hoặc cùng lớn hơn cái đằng trước và cái đằng sau.
Ví dụ Tí có 7 bức tượng có chiều cao lần lượt là 160, 162, 164, 166, 168, 170 và 172 mm . Tí có thể sắp xếp như sau:
hoặc
Và Tí muốn biết mình có tất cả bao nhiêu cách sắp xếp, biết rằng chiều cao của các tượng gỗ là phân biệt.
Cụ thể, Tí có n tượng gỗ và có chiều cao được sắp xếp sẵn theo số thứ tự là 1, 2, ..., n. Các bạn hãy giúp Tí giải quyết bài toán này.
Ví dụ, với n = 4, thứ tự các bức tượng lần lượt là 1, 2, 3, 4, sẽ có tất cả 10 cách sắp xếp, đó là:
1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423
Input
Dòng đầu tiên là số bộ test (<= 1000).
Mỗi dòng tiếp theo gồm 2 số, số thứ tự của bộ test và số n là tượng gỗ mà Tí hiện có (n <= 20).
Output
Với mỗi test, in ra trên 1 dòng 2 số, số thứ tự của bộ test và đáp án trong trường hợp đó.
Example
Input:
4 1 1 2 3 3 4 4 20Output:
1 1 2 4 3 10 4 740742376475050
| Được gửi lên bởi: | adm |
| Ngày: | 2013-02-28 |
| Thời gian chạy: | 3s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
