Comentário por Thiago Mota
Para conferir a prova na íntegra, clique aqui.
Calçada Imperial
Conhecimento prévio necessário:
Vamos escolher dois valores arbitrários no vetor, como por exemplo os valores $$2$$ e $$10$$ no caso da imagem fornecido pela prova. Para descobrir a resposta para esses dois valores basta pecorrer e vetor e sempre que acharmos o valor $$2$$ ou o valor $$10$$ checaremos se ele foi colocado como último, se ele foi então teremos que ignorá-lo, caso não seja o último adicionaremos ele a resposta. Isso pode ser feito em $$O(N)$$.
Como o $$N$$ só vai até $$500$$ podemos fazer um algoritmo em uma complexidade de $$O(N^3)$$, logo podemos testar para cada par de valores possíveis e fazer o algoritmo descrito acima para obter a melhor respota, segue o código:
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 510; | |
| int v[maxn]; | |
| int main() { | |
| ios::sync_with_stdio(false), cin.tie(0); // OTIMIZAÇÃO DO CIN/COUT | |
| int n; | |
| cin >> n; | |
| for (int i = 1; i <= n; i++) { | |
| cin >> v[i]; | |
| } | |
| int ans = 0; | |
| for (int i = 1; i <= n; i++) { | |
| for (int j = i; j <= n; j++) { | |
| int a = v[i], b = v[j]; // A e B são os valores que iremos testar | |
| int ultimo = -1; // Ultimo cara que foi adicionado ( no inicio nenhum ) | |
| int resp_local = 0; // Resposta para os valores de A e B | |
| for(int k = 1; k <= n; k++) { | |
| if (v[k] != a && v[k] != b || v[k] == ultimo) continue; | |
| // Se o valor na posição k for diferente de A ou de B ou então for igual ao úlitmo basta ignorá-lo. | |
| resp_local++; // Adiciono o valor na posição k na resposta de A e B | |
| ultimo = v[k]; // Guardo que ele foi o último adicionado | |
| } | |
| ans = max(ans, resp_local); | |
| } | |
| } | |
| cout << ans << "\n"; | |
| return 0; | |
| } |
A idade da Dona Mônica
Conhecimento prévio necessário:
Diremos que $$A$$, $$B$$ e $$C$$ são as idades dos $$3$$ filhos de Dona Mônica. Como $$A + B + C = M$$ temos que $$C = M – A – B$$, logo conseguimos facilmente calcular a idade do terceiro filho, com isso basta utilizar IF para descobrir qual é o mais velho. Segue o código:
NÃO ESQUECER DO CASO EM QUE OS FILHOS TEM IDADES IGUAIS.
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main() { | |
| int m, a, b; | |
| cin >> m >> a >> b; | |
| int c = m – (a + b); // Terceiro filho | |
| if (a >= b && a >= c) cout << a << "\n"; // A é o maior | |
| else if (b >= a && b >= c) cout << b << "\n"; // B é o maior | |
| else if (c >= a && c >= b) cout << c << "\n"; // C é o maior | |
| return 0; | |
| } |
Soma
Conhecimento prévio necessário:
Para resolver este problema usaremos as funções lower_bound() e upper_bound() do C++, caso você não conheça essas funções é recomendado você acessar esse link, mas não é necessário para a resolução do problema, apenas será utilizada no código.
A solução consiste em montar o vetor de prefixos do dado pela questão, o vetor de prefixos é basicamente um vetor $$pref$$ que é definido da seguinte forma: $$pref(i) = pref(i-1) + v(i)$$, ou seja, o valor na posição $$pref(x)$$ é na verdade a soma acumulada de todos os valores de $$1$$ até $$x$$ no vetor original. Por exemplo, para o vetor $$v = [1, 3, 4, 5, 8, 9]$$, $$pref = [1, 4, 8, 13, 21, 30]$$, com isso conseguimos calcular a soma de um intervalo $$[l, r]$$ fazendo $$pref(r) – pref(l-1)$$.
Solução em $$O(n^2)$$: Podemos olhar para cada posição $$i$$ do vetor e procurar quantos caras nesse vetor começando na posição $$i$$ soma vai ser $$k$$, no final basta somar as respostas para cada cara.
Solução em $$O(n \log n)$$: Utilizando a mesma ideia da solução anterior, podemos notar que o vetor de prefixo apenas cresce ou permanece do mesmo tamanho já que não temos valores negativos, logo para cada cara podemos fazer uma busca binária procurando em que posição $$x$$ a soma de $$i$$ até $$x$$ a soma seja $$k$$. Como temos valores $$0$$ temos que ter cuidado pois vai existir valores repetidos no prefixo, para isso basta procurar o primeiro cara que a soma da $$k$$ e o último cara que a soma da $$k$$, a resposta começando em $$i$$ vai ser o número de elementos no intervalo do último menos o primeiro.
Iremos utilizar upper_bound() e lower_bound() no vetor de prefixos para acharmos o maior e o menor cara. Não esqueça do long long.
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 5e5 + 10; | |
| int n, k; | |
| int v[maxn], pref[maxn]; | |
| int main() { | |
| ios::sync_with_stdio(false), cin.tie(0); // OTIMIZAÇÃO CIN E COUT | |
| cin >> n >> k; | |
| for (int i = 1; i <= n; i++) { | |
| cin >> v[i]; | |
| } | |
| pref[1] = v[1]; // Inicializando o primeiro prefixo | |
| for (int i = 2; i <= n; i++) { | |
| pref[i] = pref[i-1] + v[i]; | |
| } | |
| for(int i=1;i<=n;i++) | |
| cout << pref[i] << " \n"[i==n]; | |
| long long ans = 0; // LONG LONG | |
| for (int i = 1; i <= n; i++) { | |
| // Subtrair o upper_bound pelo lower_bound retorna o numero de elementos que a gente deseja. | |
| int resp = upper_bound(pref+i, pref+n+1, pref[i-1] + k) – lower_bound(pref+i, pref+n+1, pref[i-1] + k); | |
| // cout << i << ": " << lower_bound(pref+i, pref+n+1, pref[i-1] + k) – pref << " " << upper_bound(pref+i, pref+n+1, pref[i-1] + k) – pref << " " << resp << "\n"; | |
| ans += resp; | |
| } | |
| cout << ans << "\n"; | |
| return 0; | |
| } |
Chuva
Conhecimento prévio necessário:
A solução é uma aplicação clara de DFS, basta apenas chamar uma função $$dfs(i, j)$$ sendo $$(i, j)$$ a gota na primeira linha, com isso basta expandir as gotas para os locais permitidos utilizando as condições dada pelo próprio enunciado. Segue o código para melhor entendimento:
| #include <bits/stdc++.h> | |
| using namespace std; | |
| const int maxn = 550; | |
| char mat[maxn][maxn]; | |
| void dfs(int x, int y){ | |
| if (mat[x+1][y]=='.'){ | |
| mat[x+1][y]='o'; | |
| dfs(x+1, y); | |
| } | |
| else if (mat[x+1][y]=='#'){ | |
| if (mat[x][y-1]=='.'){ | |
| mat[x][y-1]='o'; | |
| dfs(x, y-1); | |
| } | |
| if (mat[x][y+1]=='.'){ | |
| mat[x][y+1]='o'; | |
| dfs(x, y+1); | |
| } | |
| } | |
| } | |
| int main() { | |
| int n, m; | |
| cin >> n >> m; | |
| int inii, inij; | |
| for (int i = 1; i <= n; i++){ | |
| for (int j = 1; j <= m; j++){ | |
| cin >> mat[i][j]; | |
| if(mat[i][j]=='o'){ | |
| inii=i; | |
| inij=j; | |
| } | |
| } | |
| } | |
| dfs(inii, inij); | |
| for (int i = 1; i <= n; i++){ | |
| for (int j = 1; j <= m; j++){ | |
| cout << mat[i][j]; | |
| } | |
| cout << "\n"; | |
| } | |
| return 0; | |
| } |
