11753. Investindo no mercado de ações 1

Olá, desculpem-me meus amigos nerds mas essa semana não tive tempo de resolver nenhum problema junto com vocês (problemas mais desafiadores me atacaram). Mesmo assim, para não deixar passar em branco a semana mais divertida da copa (valeu Costa Rica e Chile), passei aqui para resolver mais um probleminha.

Investir no mercado de ações não é algo simples, normalmente exige tempo e atenção. Mesmo assim, nesse problema, vamos ter a oportunidade de ver como nosso amigo João investe de uma forma engraçada e peculiar. O problema 11753. Investindo no mercado de ações 1 nos pede para ajudar João a determinar em quantas partes ele deve dividir seu dinheiro para que ele obtenha um investimento mais seguro (pelo menos na opinião dele).

Modelagem

O problema nos pede para contar em quantas partes precisamos dividir N reais até que tenhamos apenas partes de no máximo k reais. Sendo que a divisão deve ser feita recursivamente em duas partes iguais a ⌊N/2⌋ e ⌈N/2⌉, até restar apenas partes de no máximo k reais.

Observe que, uma leitura atenta do problema já nos indica um algoritmo para resolvê-lo. Seja conta(N), o número de partes que devemos dividir N, assim temos nossa recursão:

conta(N) = conta(⌊N/2⌋) + conta(⌈N/2⌉) se N > k
conta(N) = 1                           se N <= k

Pronto, basta implementar essa recursão e o problema de João está resolvido. Sem graça, né? Então, vamos explorar um pouco mais esse problema? Vamos brincar de derivar a complexidade da nossa solução?

É possível achar uma fórmula fechada para essa recursão, entretanto fazer isso é complicado, pois teríamos que lidar com ⌊N/2⌋, o que não é simples. Observe, entretanto que a solução para um problema de tamanho N depende da solução de um problema de tamanho N/2, então a complexidade de nossa recursão é provavelmente logarítmica.

Para comprovar nossa hipótese de que o número de passos de nossa recursão é logarítmico, suponha que N seja uma potência de 2 (N=2^h), assim ⌊N/2⌋ e ⌈N/2⌉ serão iguais, logo temos:

conta(N)         = 2*conta(N/2) <=> conta(N/2^0) = 2*conta(N/2^1)
conta(N/2)       = 2*conta(N/4) <=> conta(N/2^1) = 2*conta(N/2^2)
...
conta(N/2^(h-1)) = 2*conta(N/2^h)

logo nossa recursão terá profundidade h. Mas h = log2(N). Assim a complexidade do nosso algoritmo é logarítmica. E como você já deve ter ouvido, em algum lugar, que algoritmos de complexidade logarítimica são eficientes vamos implementá-lo, então!

Implementação

O código abaixo, implementa nossa solução. Observe que ⌊N/2⌋ e ⌈N/2⌉ são simples de calcular (basta saber se N é par ou ímpar!).

1331. Dominó

Olá, hoje vamos comemorar a estreia do Brasil na copa resolvendo mais problemas de maratona! Todos conhecem o jogo de dominós, em que peças com dois valores devem ser colocadas na mesa em sequência, de tal forma que os valores de peças imediatamente vizinhas sejam iguais. O objetivo do problema 1331. Dominó é justamente esse: determinar se é possível formar uma sequência com todas as peças de dominó fornecidas.

Modelagem

Antes de resolver esse problema, irei fazer uma breve revisão sobre grafos. Falarei apenas do necessário para solucionar esse problema. Se você não sabe o que são grafos, eu sugiro fortemente que você estude um pouco sobre isso já que eles são uma ferramenta muito poderosa na resolução de problemas.

Em teoria de grafos, diz-se que um grafo possui um caminho euleriano se existe um caminho que visita cada aresta apenas uma vez. Com caso especial, um circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg.

Em um grafo euleriano G todos os vértices têm grau par.

Prova: Seja G um grafo euleriano. Logo, por definição, ele contém um circuito euleriano. Assim, por cada vértice desse circuito, existe uma aresta que chega nesse vértice e outra que sai desse vértice. Como toda aresta faz parte do caminho, isto é, nenhuma aresta fica fora do caminho, necessariamente o número de arestas que passam por cada vértice é par.

Se removermos uma aresta de um grafo euleriano, ele deixara de ser euleriano, mas ainda conterá um caminho euleriano (é só começar e terminar o caminho nos vértices correspondentes as arestas removidas). Isso significa que um grafo que contém um caminho euleriano pode ter dois vértices de grau ímpar.

Voltando aos dominós, ligar peças, montar caminhos, é um forte indicio de que nosso problema pode ser resolvido usando-se grafos. Seja o seguinte grafo: G, onde os vértices são os números 0..6 e as arestas são os dominós. Será possível montar uma sequência com todos os dominós se, e somente se, G contiver um caminho euleriano. Em outras palavras, uma sequência de dominós não é nada mais do que um caminho euleriano onde eu peguei as arestas do grafo (os dominós) e enfileirei.

Note que os dominós podem formar um grafo que não é conexo, mas que possui dois sub grafos conexos e eulerianos, assim é necessário testar isso (com uma busca em profundidade por exemplo) para garantir que os dominós formem uma sequência única.

Implementação

8776. Batalha naval

Olá, estamos aqui de novo para resolver mais problemas! Hoje vamos falar de batalha naval e nos divertir um pouco contando quantos navios conseguimos afundar nesse conhecido jogo, já que é isso que o problema 8776. Batalha naval nos pede. 

Modelagem

Mais especificamente, esse problema nos pede que, dadas a configuração do tabuleiro e uma sequência de disparos feitos por um jogador, determine o número de navios do outro jogador que foram destruídos.

A entrada do problema já nos dá uma boa ideia de como resolvê-lo, basta armazenar o tabuleiro em uma matriz e contar quantos navios foram afundados. Cada posição da matriz pode ser de três tipos: água, navio intacto ou navio avariado por um disparo. Observe que não precisamos armazenar a informação sobre os tiros que acertaram a água.

A restrição de que dois navios não podem ter arestas em comum nos permite aplicar uma busca em largura ao tabuleiro e ir contando quantos navios foram afundados. Não vou explicar, aqui, o que é uma busca em largura já que esse assunto é extensamente abordado em qualquer estudo sobre grafos. Veja que estou apenas pegando emprestada a ideia da busca em largura, mas não estou modelando o problema usando grafos.

Complexidade

Dado um tabuleiro de N x M nossa solução avalia cada posição da matriz uma vez, assim sendo nossa solução é O(N*M).

Implementação

Abaixo uma implementação em c++ do problema. Infelismente, não estou muito inspirado para falar sobre ela já que, como você deve ter visto, o problema é bem simples.

18285. Ano Novo

Para você que gostou de nossa últama postagem, estamos aqui de novo para resolver mais problemas!

Nem só de problemas complexos vive o spoj e hoje vamos falar de um problema, que se você não for capaz de resolver com facilidade, você deve pensar seriamente em parar de ler esse blog. Nesse post vamos falar do problema 18285. Ano Novo. De modo resumido o problema pede que, dada a hora atual, você responda quantos segundos faltam para meia noite.

Modelagem da solução

Converta a entrada para segundos e faça a subtração (eu falei que era simples).

Implementação

Uma dica que pode servir em outros problemas, sempre use printf e scanf eles são bem mais rápidos que cin/cout e além disso, é possível ler entradas mais complexas de forma mais simples.