fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. //  question link : https://h...content-available-to-author-only...s.com/contests/c/547/1045
  5.  
  6. int tileWaysDPCaller(int n, int m);
  7. int tileWaysDP(int *dp, int n, int m, int i = 0);
  8.  
  9. int main()
  10. {
  11.  
  12.     int T;
  13.     cin >> T;
  14.     int i = 0;
  15.     int n, m;
  16.     while (i++ < T)
  17.     {
  18.         cin >> n >> m;
  19.         cout << tileWaysDPCaller(n, m)<< endl;
  20.     }
  21.     return 0;
  22. }
  23.  
  24.  
  25. int tileWaysDPCaller(int n, int m)
  26. {
  27.  
  28.     int dp[n + 1];
  29.     dp[0] = 1;
  30.     if (m == 0)
  31.         return 0;
  32.     else if (n == m)
  33.         return 2;
  34.     return tileWaysDP(dp, n, m, 1);
  35. }
  36. int tileWaysDP(int *dp, int n, int m, int i)
  37. {
  38.     if (i == n + 1)
  39.         return dp[n];
  40.  
  41.     if (i >= m){
  42.         dp[i] = dp[i - 1] + dp[i - m];
  43.         if(dp[i]>=1000000007)
  44.         dp[i]=dp[i]-1000000007;}
  45.     else
  46.         dp[i] = 1;
  47.  
  48.     return tileWaysDP(dp, n, m, ++i);
  49. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
2
2 3
4 4
stdout
copy 
1
2
https://ideone.com/FVyWUd
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!