NY10E - Non-Decreasing Digits

NY10E - Non-Decreasing Digits

#dynamic-programming

A number is said to be made up of non-decreasing digits if all the digits to the left of any digit is less than or equal to that digit.For example, the four-digit number 1234 is composed of digits that are non-decreasing.  Some other four-digit numbers that are composed of non-decreasing digits are 0011, 1111, 1112, 1122, 2223.  As it turns out, there are exactly 715 four-digit numbers composed of non-decreasing digits. 
 
Notice that leading zeroes are required: 0000, 0001, 0002 are all valid four-digit numbers with non-decreasing digits. 
 
For this problem, you will write a program that determines how many such numbers there are with a specified number of digits.

Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow.  Each data set is a single line that contains the data set number, followed by a space, followed by a decimal integer giving the number of digits N, (1 ≤ N ≤ 64).

Output

For each data set there is one line of output.  It contains the data set number followed by a single space, followed by the number of N digit values that are composed entirely of non-decreasing digits.

Example

Input:
3
1 2
2 3
3 4

Output:
1 55
2 220
3 715

---------------------------------code------------------------------------------------------------------#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli dp[70][10];
int n;
lli solve(int idx,int last)
{
  if(idx==n) return 1;
  else if(dp[idx][last]!=-1) return dp[idx][last];
  else
  {
     lli ret=0;
     for(int i=0;i<=9;i++)
      {
        if(i>=last)
         ret+=solve(idx+1,i);
   }
   dp[idx][last]=ret;
   return ret;
  }
}
int main()
{
 int t;
  cin>>t;
  while(t--)
   {
     int tt;
      cin>>tt>>n;
      lli ans=0;
       for(int i=0;i<=9;i++)
          {
          memset(dp,-1,sizeof dp);
           ans+=solve(1,i);
     }
      cout<<tt<<" "<<ans<<endl;
      
   }
}