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:
https://gist.github.com/fredbr/3ca897ed9334928be0a98598c7d93948
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):
https://gist.github.com/fredbr/3daf06aa24558a256d0ea6f8ee2283f6
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:
https://gist.github.com/fredbr/a0283cce367c925a300cfff2328e4e74
Mancha
Para resolver esse problema devemos fazer a seguinte observação:
- Caso $$d_{manhattan}(x, y) > d(x, y)$$ então para algum ponto $$z$$ na mesma linha ou coluna que o $$x$$, é verdade que $$d_{manhattan}(x,z) > d(x, z)$$.
- Com isso podemos fazer uma busca, em cada linha ou coluna, vendo se existe um buraco nela. Sendo um buraco um quadrado que não faz parte da mancha, mas que para cima e pra baixo, ou pra esquerda e direita, tenha algum ponto que faz parte da mancha. Pois a distância entre esses pontos, será maior que a distância de manhattan, pois teremos que dar uma volta.
Então podemos escrever uma solução em $$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:
https://gist.github.com/fredbr/af1888ba0ea3591d417dba21869638c4
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:
https://gist.github.com/fredbr/812b52495ccfdb0cbaf56e146ded2f68
Deixe um comentário