1 files changed, 57 insertions, 0 deletions
diff --git a/trees/blog/obi2018-muro.typ b/trees/blog/obi2018-muro.typ
new file mode 100644
index 0000000..acf3693
--- /dev/null
+++ b/trees/blog/obi2018-muro.typ
@@ -0,0 +1,57 @@
+#import "html_elements.typ": post
+#import "./lib.typ": flex, svg_inline
+#show: post
+
+
+- #link("https://olimpiada.ic.unicamp.br/pratique/ps/2018/f3/muro/")[Enunciado]
+
+Podemos criar uma função recursiva #svg_inline[f]:
+
+#html.frame()[
+  #text(fill: white)[
+    $
+      & f(0) = 1 \
+      & f(n) = f(n-1) + 4f(n-2) + 2f(n-3) "para" n > 0
+    $
+  ]
+]
+
+Como existem estados que irão se repetir, podemos
+usar um vetor para guardar o valor da função já computados.
+
+
+```cpp
+#include <bits/stdc++.h>
+#define int long long int
+using namespace std;
+
+const int mod = 1e9+7;
+const int MAX = 1e4+20;
+
+int dp[MAX]={};
+
+int solve(int pos) {
+    if(pos==0) return 1;
+    if(~dp[pos]) return dp[pos];
+
+    int ans=0;
+
+    ans = (ans+solve(pos-1))%mod;
+    if(pos>=2) ans = (ans+4*solve(pos-2))%mod;
+    if(pos>=3) ans = (ans+2*solve(pos-3))%mod;
+
+    return dp[pos]=ans;
+}
+
+int32_t main() {
+
+    memset(dp,-1,sizeof(dp));
+    int n;
+    scanf("%lld",&n);
+
+    printf("%lld\n",solve(n));
+
+    return 0;
+}
+```
+