BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCACM11G/

1. Đề bài BCACM11G spoj

Cho dãy gồm N số phân biệt A_N = {a₁, a₂, .., a_N } và số tự nhiên K (K<=N<=100). Ta gọi một dãy con tăng dần bậc K của dãy số A_N là một dãy các số gồm K phần tử trong dãy đó thỏa mãn tính chất tăng dần. Bài toán được đặt ra là hãy tìm số cácdãy con tăng dần bậc K của dãy số A_N.

Input

Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test được xây dựng theo khuôn dạng sau:

• Dòng đầu tiên ghi lại hai số N và K tương ứng với số phần tử của dãy số và bậc của dãy con.
• Dòng kế tiếp ghi lại N số của dãy số A_N, các số trong dãy không lớn hơn 100.

Output

Với mỗi bộ test, in ra màn hình số các dãy con tăng dần tự nhiên bậc K của dãy số A_N.

Example

Input:
2

5 3

2 5 15 10 20

5 3

2 20 10 15 5

Output:

7

1

2. Gợi ý bài BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K

– Quay lui chọn k số theo thứ tự, sau đó duyệt kiểm tra k số số có tạo dãy con tăng hay không

3. Code BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K

const   fi='';
        nmax=140;
type    data=longint;
var
        f:text;
        A,B,luu:array[0..nmax+1] of data;
        n,test,k,sl,res:data;


function check:data;
var     i,j:data;
begin
        for i:=2 to sl do
                if  A[luu[i-1]]>a[luu[i]] then
                        exit(0);
        exit(1);
end;

procedure try(i:data); //da chon so co vi tri i
var     j:data;
begin
        if sl=k then
                begin
                        res:=res+check;
                        exit;
                end;
        for j:=i+1 to n do
                begin
                        inc(sl);
                        luu[sl]:=j;
                        try(j);
                        dec(sl);
                end;
end;


procedure xuli;
var     i,j:data;
begin
        sl:=0;
        res:=0;
        try(0);
        writeln(res);
end;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,test);
        for i:=1 to test do
                begin
                        read(f,n,k);
                        for j:=1 to n do
                                read(f,a[j]);
                        xuli;
                end;
        close(f);
end;

begin
        docfile;
end.