Advertisement
YEZAELP

CMU: Tiling

Dec 3rd, 2021
594
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// Tiling 1
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int main(){
  7.  
  8.     int n, m;
  9.     cin >> n >> m;
  10.  
  11.     long long dp[n + 1];
  12.     dp[0] = 1;
  13.     for(int i=1;i<=n;i++){
  14.         if(i - m < 0) dp[i] = dp[i - 1];
  15.         else dp[i] = dp[i - 1] + dp[i - m];
  16.     }
  17.  
  18.     cout << dp[n];
  19.  
  20.     return 0;
  21. }
  22.  
  23. /// Tiling 2
  24. #include <bits/stdc++.h>
  25.  
  26. using namespace std;
  27. const int N = 30;
  28. int three[N + 10], two[N + 10];
  29.  
  30. int main(){
  31.  
  32.     three[0] = 1;
  33.     three[1] = 0;
  34.     two[0] = 0;
  35.     two[1] = 1;
  36.  
  37.     for(int i=2;i<=N;i++){
  38.         three[i] = three[i - 2] + two[i - 1] + two[i - 1];
  39.         ///        full area      top          bottom
  40.  
  41.         two[i] = three[i - 1] + two[i - 2];
  42.     }
  43.  
  44.     int q;
  45.     scanf("%d", &q);
  46.  
  47.     while(q--){
  48.         int n;
  49.         scanf("%d", &n);
  50.         printf("%d\n", three[n]);
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
  56. /// Tiling 3
  57. #include <bits/stdc++.h>
  58.  
  59. using namespace std;
  60. using lli = long long;
  61. const lli mod = 1e9 + 7;
  62. const int N = 1e3 + 10;
  63. lli full[N], top[N], bottom[N];
  64.  
  65. int main(){
  66.  
  67.     int n;
  68.     scanf("%d", &n);
  69.  
  70.     full[1] = 1;
  71.     full[2] = 2;
  72.     top[2] = 1;
  73.     bottom[2] = 1;
  74.  
  75.     for(int i=3;i<=n;i++){
  76.         full[i] = (full[i - 1] + full[i - 2] + top[i - 1] + bottom[i - 1]) % mod;
  77.         top[i] = (full[i - 2] + bottom[i - 1]) % mod;
  78.         bottom[i] = (full[i - 2] + top[i - 1]) % mod;
  79.     }
  80.  
  81.     printf("%lld", full[n]);
  82.  
  83.     return 0;
  84. }
Advertisement
RAW Paste Data Copied
Advertisement