Comentário por Lúcio Cardoso
Xadrez
Conhecimento prévio necessário:
Seja $$(x,y)$$ o quadrado na linha $$x$$ e coluna $$y$$ do tabuleiro. Já que a cor do quadrado $$(1, 1)$$ é branca, a cor de cada quadrado $$(x,y)$$ pode ser encontrada baseando-se nos seguintes casos:
1. Se x e y tem a mesma paridade, a cor de $$(x,y)$$ é branca.
2. Se x e y tem paridades diferentes, a cor de $$(x, y)$$ é preta.
Como queremos encontrar a cor do $$(L,C)$$ (canto inferior direito), basta checar em qual dos casos o quadrado se encaixa, imprimindo sua respectiva cor. Segue o código para melhor entendimento.
| //Xadrez – Fase 1 P1 – 2018 | |
| //Por Lucio Cardoso | |
| //Complexidade: O(1) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(void) | |
| { | |
| int l, c; | |
| cin >> l >> c; | |
| if ((l%2) == (c%2)) { | |
| // se l e c tem mesma paridade | |
| cout << "1\n"; | |
| } | |
| else { | |
| // se l e c tem paridades distintas | |
| cout << "0\n"; | |
| } | |
| } |
Escadinha
Conhecimento prévio necessário:
Perceba que uma escadinha é, na verdade, uma Progressão Aritmética (PA). Então, o problema se resume em encontrar a quantidade de PAs na sequência tais que nenhuma delas esteja totalmente contida em alguma outra,
e todas as PAs calculadas possuam o maior tamanho possível. Assim, para um índice $$i$$ (inicialmente 1), encontraremos o maior índice $$j$$ tal que a sequência de $$i$$ a $$j$$ seja uma PA, repetindo o processo novamente, ou seja, fazendo o novo indíce inical de uma escadinha sendo $$j$$, até que o último índice seja o próprio fim da sequência $$(n)$$. Segue o código para melhor entendimento.
| //Escadinha – Fase 1 P1 – 2018 | |
| //Por Lucio Cardoso | |
| //Complexidade: O(n) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int MAXN = 1010; | |
| // sequência de números | |
| int num[MAXN]; | |
| int main(void) | |
| { | |
| int n; | |
| cin >> n; | |
| for (int i = 1; i <= n; i++) | |
| cin >> num[i]; | |
| // faremos esse caso separadamente | |
| if (n == 1) | |
| { | |
| cout << "1\n"; | |
| return 0; | |
| } | |
| // resposta do problema | |
| int ans = 0; | |
| for (int i = 1; i < n; i++) | |
| { | |
| // razão da PA | |
| int dif = num[i]-num[i+1]; | |
| for (int j = i; j < n; j++) | |
| { | |
| // se j é o último número na PA | |
| if (num[j]-num[j+1] != dif) | |
| { | |
| // na prox. iteração, i receberá j-1+1 = j | |
| i = j-1; | |
| break; | |
| } | |
| // n é o último número da PA, então faço i = n-1 para sair do loop | |
| if (j+1 == n) i = n-1; | |
| } | |
| // chegamos ao fim da PA atual, então incremento ans | |
| ans++; | |
| } | |
| cout << ans << "\n"; | |
| return 0; | |
| } |
Pirâmide
- Programação dinâmica (Aula 13)
Para cada linha $$i$$ da pirâmide com $$i$$ caixas numeradas por colunas de $$j$$ a $$j+i-1$$, a linha acima $$(i-1)$$ possui $$i-1$$ caixas consecutivas, ou com colunas desde $$j$$ a $$j+i-2$$, ou desde $$j+1$$ a $$j+i-1$$, já que, caso contrário, ao menos uma das caixas não possuiria uma respectiva caixa abaixo dela, na linha $$i$$. Assim, podemos utilizar uma função recursiva $$f(k, j)$$ para encontrar a resposta mínima do problema, representando a pirâmide com a linha de índice $$k$$ em sua base, e que por sua vez tem $$k$$ caixas consecutivas a partir da coluna $$j$$. Temos, assim, que:
1. O caso base da função pode ser tomado quando $$k = 1$$, já que a resposta neste caso é apenas o valor da caixa na linha $$1$$, coluna $$j$$.
2. Como a linha $$k$$ é a base da pirâmide, a soma de todos os valores das $$k$$ caixas desde a coluna $$j$$ até a coluna $$j+k-1$$ estará incluída na resposta de $$f(k, j)$$.
3. Pelas observações anteriores, há dois casos para a coluna inicial na linha $$k-1$$: ou $$j$$, ou $$j+1$$. Perceba que assim, a coluna final em tal linha está definida: será, respectivamente, $$j+k-2$$ ou $$j+k-1$$, já que a linha $$k-1$$ possui $$k-1$$ caixas. Como queremos a soma mínima possível dos valores das caixas, escolheremos o mínimo entre estes dois casos.
Podemos, então, finalmente montar a relação de recursão de $$f(k, j)$$:
Se $$k = 1$$, $$f(k, j) = caixa[1][j];$$
Senão, $$f(k, j) = s[k][j…j+k-1] + min(f(k-1, j), f(k-1, j+1))$$, onde $$s[x][a…b]$$ é a soma dos números na linha $$x$$ desde a coluna $$a$$ até a coluna $$b$$. No entanto, a complexidade da função é exponencial, e logo, não passa nas restrições do problema. Para tornar a complexidade aceitável, utilizaremos duas técnicas adicionais:
1. Podemos conseguir $$s[x][a..b]$$ em $$O(1)$$, com pré-cálculo em $$O(n²)$$, da seguinte maneira: Primeiro, vamos definir uma matriz $$soma[x][b]$$ como sendo a soma dos números na linha $$x$$ desde a coluna $$1$$ até a coluna $$b$$. Inicialmente, $$soma[x][0] = 0$$, para todo $$x$$ tal que $$1 <= x <= n$$. Então, $$soma[x][b] = soma[x][b-1]+caixa[x][b]$$, com $$1 <= b <= n$$. Portanto, é possível conseguir $$s[x][1…b]$$ em $$O(1)$$ após o pré-cálculo, já que $$s[x][a…b] = s[x][1…b]-s[x][1…(a-1)]$$, ou seja, $$s[x][a…b] = soma[x][b]-soma[x][a-1]$$.
2. Finalmente, usaremos uma matriz $$n*n$$ chamada $$dp[n][n]$$ que irá guardar todos os estados que já foram previamente calculados na recursão (essa técnica é conhecida como programação dinâmica). Assim, evitamos que um estado seja calculado mais de uma vez, tornando a complexidade da função $$O(n²)$$, já que $$1 <= k, j <= n$$. Obteremos então a resposta do problema chamando $$f(n, 1)$$.
Segue o código para melhor entendimento.
| //Piramide – Fase 1 P1 – 2018 | |
| //Por Lucio Cardoso | |
| //Complexidade: O(n²) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int MAXN = 110; | |
| int num[MAXN][MAXN], soma[MAXN][MAXN], dp[MAXN][MAXN], n; | |
| // pre-cálculo em O(n^2) para encontrar soma[][] | |
| void pre(void) | |
| { | |
| for (int i = 1; i <= n; i++) | |
| for (int j = 1; j <= n; j++) | |
| soma[i][j] = soma[i][j-1]+num[i][j]; | |
| } | |
| // recursão em O(n^2) | |
| int f(int k, int j) | |
| { | |
| if (k == 1) return num[1][j]; // caso base | |
| if (dp[k][j] != -1) return dp[k][j]; // se f(k,j) já foi calculado | |
| int s = soma[k][j+k-1]-soma[k][j-1]; // soma na linha atual | |
| int caso1 = f(k-1, j); | |
| int caso2 = f(k-1, j+1); | |
| // salvo em dp a resposta de f(k, j) e a retorno | |
| return dp[k][j] = s+min(caso1, caso2); | |
| } | |
| int main(void) | |
| { | |
| cin >> n; | |
| for (int i = 1; i <= n; i++) | |
| for (int j = 1; j <= n; j++) | |
| cin >> num[i][j]; | |
| pre(); // faço o pré-cálculo | |
| // inicializo dp com um valor que nunca será resposta, digamos -1 | |
| memset(dp, -1, sizeof dp); | |
| cout << f(n, 1) << "\n"; // imprimo a resposta, começando na base | |
| } |
