PHÂN CHIA DÃY SỐ - TÊN FILE CHƯƠNG TRÌNH

Câu 3. Phân chia dãy số - tên file chương trình: BL3.PAS

Cho dãy số nguyên A có N phần tử: A

, A

, ..., A

.

Yêu cầu: tìm một cách phân chia tất cả các phần tử của tập {1, 2, ..., N} thành các tập con thỏa mãn đồng

thời các điều kiện sau:

-Tổng các phần tử của A có chỉ số thuộc cùng một tập con chia hết cho số nguyên dương M cho

trước.

-Hai tập con khác nhau không có phần tử chung.

-Số tập con là nhiều nhất.

Dữ liệu vào: đọc từ file văn bản có tên BL3.INP, có cấu trúc:

-Dòng đầu tiên ghi hai số nguyên dương N, M (N≤100, M≤1000).

-Dòng thứ hai ghi các số thuộc dãy A, theo thứ tự từ A

đến A

.

Dữ liệu ra: ghi vào file văn bản có tên BL3.OUT theo cấu trúc:

-Dòng đầu tiên ghi số nguyên S là số tập con tìm được (S=0 nếu không có cách phân chia).

-Nếu S≠0 thì dòng thứ i trong số S dòng tiếp theo, mỗi dòng ghi thông tin về một tập con tìm được

bao gồm: số nguyên dương đầu tiên là số phần tử của A thuộc tập con, các số tiếp theo là chỉ số các phần

tử thuộc tập con đó.

Hai số liên tiếp trong các file dữ liệu vào và ra ghi cách nhau ít nhất một kí tự trống.

Ví dụ:

BL3.INP BL3.OUT

8 3

5

2 1 3 4 5 6 7 2

2 1 2

1 3

2 4 5

1 6

2 7 8