Comentário OBI – Fase 3 – Programação 2

Comentário por Frederico Bulhões

Cinco

Para resolvermos essa questão devemos observar uma coisa:

• O número inicial dado não é divisível por cinco
  • Então para que haja resposta é necessário que a troca ocorra entre um número igual a 0 ou 5 e o número da ultima posição, pois então o novo número terminará em 0 ou 5, tornando-o divisível por cinc0.

Como $N \leq 1000$, podemos então fazer um algoritmo em $O(n^2)$ da seguinte forma:

Para todas as posições entre $1$ e $N$ checamos se o dígito daquela posição é 0 ou 5, caso seja, trocamos ele com o ultímo, e comparamos com a resposta computada até agora, caso maior ele se torna a resposta, e depois trocamos de volta o dígito atual com o ultímo.

Na implementação a seguir é ussado a função $max$ do C++, que compara lexicográficamente dois vetores passados e retorna o maior.

Código para melhor entendimento:

Muro

Essa é uma questão de combinatória, em que podemos usar programação dinâmica como meio de resolver.

Vamos tentar achar uma recorrência para reolver o caso $N$:

Pelo desenho fornecido na questão pode-se ver que caso tenhamos um muro de tamanho $N$ podemos preênche-lo da seguinte maneira:

• Colocando dois blocos de tamanho 1 próximos a um muro de tamanho $N-1\Rightarrow F_{N-1}$
• Colocando dois blocos, um L e o outro um quadrado, de quatro formas diferentes, próximos a um muro de tamanho $N-2\Rightarrow 4\cdot F_{N-2}$
• Colocado dois blocos L próximos de duas formas diferentes, próximos a um muro de tamanho $N-3\Rightarrow 2\cdot F_{N-3}$

Então ficamos com a recorrência $F_N = F_{N-1} + 4\cdot F_{N-2} + 2\cdot F_{N-3} \mod{10^9+7}$. (Sempre tirando o módulo, como pedido na questão)

Os casos base são dados na questão, $F_0$ = 1, $F_1$ = 1, $F_2 = 5$.

Para computar $F_N$ podemos usar programação dinâmica, de forma recursiva, salvando o resultado computado agora para não termos que computa-lo de novo, reduzindo a complexidade de $O(3^N)$ para $O(N)$, ou podemos fazer de forma iterativa, fazendo um for de $3$ até o $N$ desejado, computado o valor atual usando a recorrência dada e os 3 valores anteriores.

Segue o código para melhor entandimento, (implementado de forma iterativa):

Baldes

Para resolvermos esse problema, devemos ter uma noção da estrutura Segment Tree, caso não a conheça recomendo que leia esse TUTORIAL para ter uma noção do que vamos falar agora.

Primeiro devemos perceber que para cada balde só importa o menor e o maior valor, e os outros são irrelevantes para a resposta, pois não faz sentido colocar uma bola com o outra de outro balde quando poderíamos pegar uma menor ou maior.

Nesse problema podemos em cada nó da Seg Tree, que representa os baldes entre $L$ e $R$, guardar três valores:

• Valor máximo das bolas entre os baldes $L$ e $R$, incluso.
• Valor mínimo das bola entre os baldes $L$ e $R$, incluso.
• Máximo entre:
  • Diferença máxima entre bolas de baldes entre $L$ a $M$ e de baldes entre $M+1$ e $R$, (sendo $M$ ponto do meio entre $L$ e $R$);
  • Diferença máxima do filho da esquerda, bloco que representa $L$ a $M$
  • Diferênca máxima do filho da direita, bloco que representa $M+1$ a $R$

Podemos então fazer as queries  e  updates de acordo com a questão, cada uma em $O(log(N))$, somando u tempo total de $O(N + Q log(N))$

Recomendo que leia a implementação com cuidado, e caso tenha dúvidas consulte um tutorial de Segment Tree

Código para melhor entendimento:

Mancha

Para resolver esse problema devemos fazer a seguinte observação:

• Caso $z$ na mesma linha ou coluna que o $x$, é verdade que $O(n^2)$ para resolver esse problema, passando por cada linha e cada coluna checando essa condição em $O(n)$.

  Nessa implementação checamosse a soma de pontos que são da mancha entre o primeiro e ultimo daquela linha/coluna é igual a distância entre o primeiro e o último. Caso sim para toadas as linhas e colunas a resposta é sim. Senão a resposta é não.

  Código para melhor entendimento:

  
  

  	#include <bits/stdc++.h>
  	using namespace std;
  	const int maxn = 1010;
  	char m[maxn][maxn];
  	int main()
  	{
  	int n;
  	cin >> n;
  	for (int i = 0; i < n; i++)
  	for (int j = 0; j < n; j++)
  	cin >> m[i][j];
  	for (int i = 0; i < n; i++) {
  	int ini = n, fim, cnt = 0;
  	for (int j = 0; j < n; j++) {
  	if (m[i][j] == '*') {
  	if (ini == n) {
  	ini = j;
  	}
  	cnt++;
  	fim = j;
  	}
  	}
  	if (ini != n and cnt != fim-ini+1) {
  	cout << "N\n";
  	return 0;
  	}
  	}
  	for (int i = 0; i < n; i++) {
  	int ini = n, fim, cnt = 0;
  	for (int j = 0; j < n; j++) {
  	if (m[j][i] == '*') {
  	if (ini == n) {
  	ini = j;
  	}
  	cnt++;
  	fim = j;
  	}
  	}
  	if (ini != n and cnt != fim-ini+1) {
  	cout << "N\n";
  	return 0;
  	}
  	}
  	cout << "S\n";
  	}

  view raw
  
  mancha.cpp
  
  hosted with ❤ by GitHub

  Bolas

  Para resolver esse problema podemos usar o Prinípio da Casa dos Pombos. Caso tenhamos um valor com mais de 4 ocorrências, então obrigatoriamente vamos ter que colocar uma dessas bola do lado da outra igual. Para resolver esse problema bastachecar essa condição, pois caso ela ocorra, só pode ocorrer com uma bola de um valor.

  O código resultante tem complexidade de $O(1)$.

  Código para melhor entendimento:

  
  

  	#include <bits/stdc++.h>
  	using namespace std;
  	int freq[10];
  	int main()
  	{
  	for (int i = 0; i < 8; i++) {
  	int x;
  	cin >> x;
  	freq[x]++;
  	}
  	for (int i = 0; i <= 9; i++) {
  	if (freq[i] > 4) {
  	cout << "N\n";
  	return 0;
  	}
  	}
  	cout << "S\n";
  	}

  view raw
  
  bolas.cpp
  
  hosted with ❤ by GitHub