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

Nguon:Suutam

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ác dã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

#include<iostream>
using namespace std;

int a[102],b[102],k,n,OK ,dem ;

void Init()
{
     cin>>n;
     cin>>k;
     dem =0;
     OK =1;
     for(int i=1;i<=100;i++)
       a[i] =i;
     for( int i =1;i<=n;i++)
     cin>>b[i];
}
void sinh_to_hop()
{
     int i = k ;
     while( a[i] >= n-k+i&& i>0)i--;
     if( i>0)
     {
         a[i] = a[i] +1;
         for( int j = i+1;j<=k;j++) a[j] = a[i] + j-i;
         
     }
     else OK =0;
}
     
void test()
{
     int q =1;
     for( int i=1;i<k;i++)
     if( b[a[i]] >= b[a[i+1]])
     {
         q =0;
         break;
     }
     if( q == 1) dem++;
}

int main()
{
    int slg;
    cin>> slg;
    
     
    for( int i=1;i<=slg;i++)
    {
         Init();
         while(OK)
         {
             test();
             sinh_to_hop();
             
         }
    
         cout<< dem<< endl;
         
    }
    
    //system("pause");
    return 0;
}