This is the second part of a series of articles that I’m writing to document by progress on building a Interpreter for myLisp, a lisp-like language. For the previous post click here.
What is an interpreter? An Interpreter is a program that takes souce code as input and executes it. It is composed of several parts, today we are going to write a lexer and a parser.
The lexer will read a string of characters and output a vector of tokens, with some information attached to them like its type.
This is the first part of a series of articles that I’ll be writing to document my progress on building a interpreter for a Lisp-like language.
I’ve been interested in learning different programming languages for a while now, I’ve read the first chapters of Haskell and Lisp books recently and the one that hooked me on was Land of lisp. Lisp’s simplicity really struck me: from very simple building blocks you can create anything in such an elegant and simple way.
Enunciado
Na minha primeira leitura, vi que esta é uma questão clássica de segtree. Um vetor de tamanho \(10^5\) e \(10^5\) queries dentro desse intervalo. Iremos fazer uma segtree para o mínimo num intervalo e outra para o máximo, sendo a resposta da query em um intervalo o max-min. Para simplificar isso, podemos guardar as duas árvores apenas em um vetor de pairs.
Porém após implementar a primeira solução e não funcionar fiz uma segunda leitura e percebi que o max e o min não podem estar no mesmo balde (na mesma posição no vetor).
Enunciado.
Como o tamano do vetor é \(8\) e temos sempre \(8\) números para escolher, existem \(8!\) permutações possíveis. Como \(8!\) é pequeno, podemos fazer uma solução de busca completa. Existem de varias soluções possíveis como com next_permutation. Segue uma solução de backtracking:
#include <bits/stdc++.h>using namespace std; int vet[9]={}; int solve(int pos, int n) { if(pos==8) return 1; int ans=0; for(int i=0;i<=9;i++) { if(n != i && vet[i]) { vet[i]--; ans|=solve(pos+1,i); vet[i]++; } } return ans; } int main() { for(int i=0;i<8;i++) { int aux; scanf("%d",&aux); vet[aux]++; } int ans=solve(0,-1); puts(ans?
Enunciado
Podemos criar um algoritmo guloso simples, trocar sempre (em ordem):
O dígito mais significativo que for trocado por um número maior do que ele (na falha do primeiro) O dígito menos significativo que for trocado por um número menor do que ele #include <bits/stdc++.h>using namespace std; int main() { int n; scanf("%d",&n); int arr[n]; for(int i=0;i<n;i++) scanf("%d",&arr[i]); for(int i=0;i<n;i++) { if(arr[i]<arr[n-1]&&(arr[i]==0||arr[i]==5)) { swap(arr[i],arr[n-1]); for(int j=0;j<n;j++) printf("%d%c",arr[j],j==n-1?'\n':' '); exit(0); } } for(int i=n-1;i>=0;i--) { if(arr[i]==0||arr[i]==5) { swap(arr[i],arr[n-1]); for(int j=0;j<n;j++) printf("%d%c",arr[j],j==n-1?
Enunciado
Como o tamanho máximo do vetor é \(10^5\) podemos ordená-lo. Fazendo isso podemos ver que o número que estamos procurando está entre dois números vizinhos no vetor ou está em alguma das extremidades.
#include <bits/stdc++.h>using namespace std; int main() { int n,r,l; scanf("%d%d%d",&n,&r,&l); int arr[n]; for(int i=0;i<n;i++) scanf("%d",&arr[i]); sort(arr,arr+n); int dif=0; for(int i=1;i<n;i++) { int mid=(arr[i]+arr[i-1])/2; if(mid>=r&&mid<=l) dif=max(dif,min(abs(mid-arr[i]),abs(mid-arr[i-1]))); } if(l>arr[n-1]) dif=max(dif, l-arr[n-1]); if(r<arr[0]) dif=max(dif,arr[0]-r); printf("%d\n",dif); return 0; }
Enunciado
Podemos criar uma função recursiva \(f\):
$$ f(0) = 1 $$
$$ f(n) = f(n-1) + 4f(n-2) + 2f(n-3) \quad \text{para } n > 0 $$
Como existem estados que irão se repetir, podemos usar um vetor para guardar o valor da função já computados.
#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; }