Nesse sábado, dia 29/03, aconteceu o XIII Contest Algar Telecom, tanto presencialmente em Uberlândia, quanto online no portal do URI.
Eu colaborei escrevendo quatro exercícios, e vou comentar a solução deles aqui neste post. Caso eu resolva os outros, eu também posso comentar eles aqui, mas sem pressa.
Clique no link abaixo para ver o resto do post.
Detetive Watson – [link]
Há duas formas bem simples de se resolver este exercício.
Se você conhece algum método de ordenação, basta ordenar os valores, de um modo que você não perca a posição original deles. Ao final, basta imprimir a posição original do segundo maior valor.
Outro modo seria implementar um método que busca pelo maior valor dentro do vetor. Execute o método uma vez, e altere o maior valor para -1. Na segunda vez que você executar o método, este será o resultado.
Arremesso de Bolas – [link]
Para resolver este exercício, é necessário testar todas as possibilidades de velocidade com a qual você pode arremessar a bola inicialmente.
Para cada velocidade escolhida, simule os pontos em que a bola quica com alguns laços de repetição, e se em algum momento a bola quicar na posição N, o resultado é “possivel”.
Se ela nunca quicar na posição N, não importando qual das velocidades permitidas com a qual você arremesse, então a resposta é “impossivel”.
Fila do Banco – [link]
Este exercício pode ser resolvido de várias maneiras. A mais direta é utilizando o conceito de Classes de Equivalência em Combinatórias.
Vamos esquecer por um segundo a ordem em que as outras pessoas na fila estão ordenadas. Vamos representar a fila como uma sequência de caracteres, sendo A o André, B o Bruno, C o Carlos, e X qualquer outra pessoa.
Dentre as seguintes combinações, quantas são válidas?
ABCXX ACBXX BACXX BCAXX CABXX CBAXX
Apenas a primeira, pois André deve estar atrás de Bruno, e Bruno deve estar atrás de Carlos.
Então, independente da posição das outras pessoas, para cada 6 combinações, apenas 1 atende os requisitos do exercício.
Sabendo disso, o resultado pode ser obtido com a fórmula:
N! / 6
Basta agora tomar cuidado com o resto de divisão. Note que N! é divisível por 6, pois 6 faz parte da multiplicação, mas (N! Mod 10^9+7) pode não ser divisível por 6.
Como N >= 3, uma alternativa é dividir por 6 antes de calcular os outros fatoriais com a fórmula: fat[n] = n*fat[n-1].
Resultando em fat[3] = 1, fat[4] = 4, fat[5] = 20, e assim por diante.
Caso você pré-calcule os fatoriais Mod 10^9+7, em vez de dividir por 6 é possível multiplicar pelo inverso modular de 6 (a saber, 833333341), que o efeito é o mesmo. Pesquisem a respeito de inverso modular para mais detalhes.
Quadro Premiado – [link]
Este exercício pode ser resolvido utilizando-se o conceito de Programação Dinâmica. Basta descobrir quais padrões são compatíveis com quais outros padrões, e os relacionamentos entre os sub-problemas podem ser definidos.
O primeiro passo, portanto, é descobrir que padrões são compatíveis entre si. Um padrão m é compatível com um padrão k se, e somente se, para cada posição i do tamanho dos padrões, m[i] != k[i] || m[i] == “.” || k[i] == “.”.
Após isso podemos aplicar o conceito de programação dinâmica para tirar vantagem de sub-problemas que se repetem.
Seja dp[n][m] a soma máxima que é possível ser obtida utilizando o padrão m na linha n:
dp[n][m] = max(dp[n+1][k]) + soma(n, m),
para todo padrão k que é compatível com m,
e onde soma(n, m) resulta no valor obtido ao aplicar o padrão m na linha n.
Detalhe para o fato que o exercício pede “a soma máxima que é possível ser alcançada”. Isso não impede que a soma máxima seja negativa.
Qualquer dúvida, crítica ou sugestão, deixe um comentário abaixo.
Espero que tenham gostado dos exercícios, até mais.
Ótimo post, poderia falar sobre os outros problemas, como aqueles fáceis, que parecem ser bem simples mas deu bastante dor de cabeça para alguns durante o contest
Opa, obrigado.
Pois é, assim que der tempo vou tentar falar sobre eles.
Sobre o problema Fila do Banco, um outro modo simples de resolver que o meu professor de analise de algoritmos enxergou seria simplificar o fatorial para eliminar a divisão. Exemplo:
4! / 6 =
3! * 4 / 3! =
3!* 4 /3!=4
Desse modo tudo que precisariamos fazer é somar as multiplações até n, modularizando os resultados por 1000000009.
BTW, muito bom o problema… me fez quebrar a cabeça muito! kkk