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 e 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 ou o valor 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 .
Como o só vai até podemos fazer um algoritmo em uma complexidade de , 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:
This file contains 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
#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 , e são as idades dos filhos de Dona Mônica. Como temos que , 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.
This file contains 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
#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 que é definido da seguinte forma: , ou seja, o valor na posição é na verdade a soma acumulada de todos os valores de até no vetor original. Por exemplo, para o vetor , , com isso conseguimos calcular a soma de um intervalo fazendo .
Solução em : Podemos olhar para cada posição do vetor e procurar quantos caras nesse vetor começando na posição soma vai ser , no final basta somar as respostas para cada cara.
Solução em : 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 a soma de até a soma seja . Como temos valores temos que ter cuidado pois vai existir valores repetidos no prefixo, para isso basta procurar o primeiro cara que a soma da e o último cara que a soma da , a resposta começando em 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.
This file contains 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
#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 sendo 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:
This file contains 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
#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; | |
} |