SPOJ.com - Problem BCPARTI

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCPARTI - Partition thuận nghịch đệ quy

Một biểu diễn của một số nguyên dương N dưới dạng tổng các số nguyên dương nhỏ hơn hoặc bằng N được gọi là partition của số N. Ví dụ với N =15 ta có thể biểu diễn: 15 = 1+2+3+4+5 = 1+2+1+7+1+2+1.

Một partition được gọi là thuận nghịch nếu đọc theo cả hai chiều đều được kết quả giống nhau. Ví dụ {1+2+1+7+1+2+1} là một partition của 15 thoả mãn tính chất thuận nghịch.

Một partition được gọi là thuận nghịch đệ quy nếu nửa bên trái của nó cũng thuận nghịch đệ quy hoặc rỗng. Với định nghĩa này, mỗi số N sẽ hiển nhiên sẽ có hai partition thuận nghịch đệ quy là dãy N số 1 và dãy chỉ gồm duy nhất số N.

Ví dụ, các partition thuận nghịch đệ quy của 7 là:

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

Viết chương trình nhập vào số tự nhiên N và đưa ra số partition thuận nghịch đệ quy của N.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên 1 ≤ t ≤ 1000 là số lượng bộ test. Mỗi bộ test sẽ viết trên một dòng duy nhất một số nguyên N(N<=1000)

Dữ liệu ra

Với mỗi bộ dữ liệu vào, đưa ra một dòng gồm 2 số: số thứ tự bộ test và số lượng partition thuận nghịch đệ quy tương ứng. Hai số cách nhau bởi một dấu cách.

Example

Input:

20 Output:

1 4

2 6

3 60

ID	RESULT	TIME

code...

Submit solution!

Được gửi lên bởi:	adm
Ngày:	2011-10-19
Thời gian chạy:	1s
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

hide comments



2017-07-26 12:02:13 BCPARTI: https://e16cn-ptit.blogspot.com/2017/12/bcparti-partition-thuan-nghich-de-quy.html Last edit: 2017-12-12 11:03:00
2016-07-02 04:41:17 HD: http://q.gs/AEIVB

Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

BCPARTI - Partition thuận nghịch đệ quy