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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //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 | |
| } |