Comentário Noic OBI 2019 - Fase 1 - Programação Nível 2

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;
}

view raw

imperial.cpp

hosted with ❤ by GitHub

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;
}

view raw

idade.cpp

hosted with ❤ by GitHub

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;
}

view raw

soma.cpp

hosted with ❤ by GitHub

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;
}

view raw

chuva.cpp

hosted with ❤ by GitHub