Advertisement
YEZAELP

SMMR-117: Call

Jul 7th, 2020
74
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.  
  6.     int n;
  7.     long long ans=0;
  8.     scanf("%d",&n);
  9.  
  10.     long long dp[n+1][10];
  11.  
  12.     for(int j=0;j<=9;j++) dp[1][j]=1;
  13.  
  14.     for(int i=2;i<=n;i++){
  15.         dp[i][1] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4];
  16.         dp[i][2] = dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][5];
  17.         dp[i][3] = dp[i-1][2] + dp[i-1][3] + dp[i-1][6];
  18.         dp[i][4] = dp[i-1][1] + dp[i-1][4] + dp[i-1][5] + dp[i-1][7];
  19.         dp[i][5] = dp[i-1][2] + dp[i-1][4] + dp[i-1][5] + dp[i-1][6] + dp[i-1][8];
  20.         dp[i][6] = dp[i-1][3] + dp[i-1][5] + dp[i-1][6] + dp[i-1][9];
  21.         dp[i][7] = dp[i-1][4] + dp[i-1][7] + dp[i-1][8];
  22.         dp[i][8] = dp[i-1][5] + dp[i-1][7] + dp[i-1][8] + dp[i-1][9] + dp[i-1][0];
  23.         dp[i][9] = dp[i-1][6] + dp[i-1][8] + dp[i-1][9];
  24.         dp[i][0] = dp[i-1][8] + dp[i-1][0];
  25.     }
  26.     for(int j=0;j<=9;j++){
  27.         ans+=dp[n][j];
  28.     }
  29.     printf("%lld",ans);
  30.  
  31.     return 0;
  32. }
Advertisement
RAW Paste Data Copied
Advertisement