11629. Competição de chocolate

Olá meus amigos nerds. Hoje vamos brincar (literalmente) de comer bolinhas de chocolate. Já que é isso que o problema 11629. Competiçăo de chocolate nos pede para fazer. Mais especificamente, dado o jogo em que dois jogadores comem bolinhas de chocolate de modo alternado, com a restrição de que há n bolinhas e que um jogador pode comer no máximo m delas de cada vez. Determinar quem ganha o jogo, se o jogador que começou ou o que jogou em segundo lugar. 

Solução

Para quem já conhece, esse jogo é uma variação d Nim. A ideia para resolver esse problema é simples:

a) Se m >= n o jogador que começa pode comer todas as bolinhas de chocolate e ganhar o jogo.
b) Se m < n, teríamos.

1 Se há 1, 2, ..., m bolinhas restantes, então quem joga ganha (ele pode comer todas as bolinhas)
2 Se há m+1 bolinhas então quem joga perde, pois ele não pode comer todas as bolinhas e qualquer número de bolinhas que ele comer resulta em uma configuração em que o outro jogador pode comer todas as bolinhas.
3 Se há m+1,..., 2m+1 bolinhas quem joga ganha, basta comer de modo a restar m+1 bolinhas (cenário em que quem joga, ou seja, seu adversário perde, dado o item 2).

Do esposto acima é possível concluir que se n == 0 mod m+1 quem joga perde. Então vamos a indução (vale para 1, suponha que vale para n, prove que vale para n+1): Suponha que essa relação valha para n. Para n+1 teríamos:

n+1 == 1 mod m+1 já que n == 0 mod m+1, ou seja, quem joga ganha pois ele pode comer uma bolinha e deixar que o outro jogador perca, uma vez que o segundo jogador estará na situação em que n == 0 mod m+1. Logo a relação vale para n+1, cqd.

Implementação

18550. Troco

Olá meus amigos nerds. Hoje completa exatamente um ano que eu resolvi um problema relacionado a moedas. E para comemorar, nada melhor do que resolver outro problema do tipo. Vamos tentar verificar se é possível pagar uma conta de modo exato apenas com as moedas que estão em nosso bolso. Já que é isso que o problema 18550. Troco nos pede para fazer. Mais especificamente, dadas m moedas, determinar se é possível somar exatamente v centavos usando um subconjunto dessas moedas.

Solução

Como todo problema de programação dinâmica esse não é fácil. Uma solução que enumere todos os conjutos possíveis de moedas e verifique se eles somam v não viável.

O segredo, para resolver esse problema, esta em pensar o que acontece quando eu pego uma moeda. Suponha que eu conheça todos os valores que eu consigo somar com as moedas restantes, se a cada um desses valores, eu somar a moeda atual eu fico com um novo conjunto de valores que eu consigo somar. A união desse conjunto e do anterior forma todas as somas que eu consigo fazer até o momento.

Isso sugere uma solução usando programação dinâmica. Com 0 moedas eu só consigo somar 0. Adicionando a primeira moeda eu só consigo somar 0 e o valor da moeda. Com a segunda eu já consigo somar 0, o valor da primeira, o valor da segunda e a soma das duas... Ou seja, se eu armazenar para cada valor possível de soma (menor ou igual a v é claro) se é possível somar aquele valor, para adicionar uma moeda é só eu percorrer esse vetor de estados e ir atualizando as posições dele com as novas somas possíveis.

A ideia acima funciona pois: se já é possível somar x com um conjunto de moedas, se eu adicionar mais uma moeda ao problema, continua sendo possível eu somar x (basta eu não usar a nova moeda). Se eu consigo somar a, b e c e eu adiciono outra moeda (d) ao problema eu vou poder somar além de a, b e c, (a+d), (b+d), (c+d). Algoritmicamente falando:

somas_possiveis = {0}
para cada moeda x
    para cada soma em somas_possiveis
        novas_somas += (x+soma)
    somas_possiveis |= novas_somas

Ou considerando que somas_possiveis sera representado por um vetor
somas_possiveis[0] = True
para cada moeda x
    para i=len(somas_possiveis), i >= x, i--
        Se somas_possiveis[i-x]
            somas_possiveis[i] = True

Note que se eu posso somar i-x centavos, se eu adicionar a moeda atual eu posso somar i centavos. O loop é feito de forma decrescente para garantir que eu não use x duas vezes para uma mesma soma, já que i-x ainda não foi calculado para a moeda atual.

Note que a solução apresentada depende do valor de v, ou seja, é uma solução pseudo polinomial. Mais precisamente a complexidade dessa solução é O(v*m), como v e m são relativamente pequenos essa solução é suficiente para conseguirmos superar o time limit.

Implementação

:P O operador -- serve para alguma coisa! Observe que se invertermos a lógica do loop da linha 22 para uma lógica aditiva o programa deixa de produzir a resposta certa, pois nesse caso quebramos nosso invariante de que somas_possiveis[v-moeda] não utiliza a moeda atual para ser somado.

1831. f91

Olá meus amigos nerds, hoje vamos brincar de estudar uma função recursiva, já que é isso que o problema 1831. f91 nos pede. Mais especificamente o problema nos fornece uma função recursiva e pede que computemos o resultado.

Solução

Você deve estar se perguntando o que tem de interessante nesse problema. Sim, esse é um problema razoavelmente fácil, mesmo assim tem alguns detalhes legais que podemos explorar. O problema define a seguinte função:

• Se N ≤ 100, então f91 (N) = f91 (f91 (N + 11));
• Se N ≥ 101, então f91 (N) = N - 10

Obviamente se implementarmos essa função já temos o problema resolvido:

f91(n)
    if n > 100 return N-10
    else return f91(f91(N+11))

Agora vamos tentar ser um pouco mais espertos e deduzir analiticamente o resultado dessa recursão. É ai que essa função fica divertida, pois ela sempre retorna 91 para todos os números menores ou iguais a 101. Desenvolvendo a função temos:

f91(n) = f91(f91(n+11)) = f91(f91(f91(f91(n+2*11)))) = f91(f91(f91(f91(f91(f91(n+3*11)))))) =...

Observe que n+11, n+2*11, n+3*11 é uma sequência extritamente crescente. Em algum momento, o valor dessa sequência ultrapassara 100 mas será menor ou igual a 111 (estamos somando 11). Nesse momento começaremos a subitrarir 10 e somar 11 a esse número, ou seja, duas chamadas consecutivas dessa função terão o efeito de somar 1 ao número (que ainda será menor que 100), exemplo:

f91(99) = f91(f91(99+11) = f91(f91(110)) = f91(100)

Ou seja, por indução f91(n) = f91(n+1) para todo n <= 90. Mas:

f91(100) = f91(f91(111)) = f91(101) = 91

logo f91(n) = 91 para todo n>=90. Para n < 90 temos:

f91(n) = f91(f91(n+11)) = f91(...f91(n+i*11)...)

e como n+i*11 é maior que 90 (basta tomar um i suficientemente grande):

f91(n) = f91(f91(n+11)) = f91(...f91(X > 90)...) = f91(...f91(91)...)

aplicando o fato de que f91(91) = 91 recursivamente temos: f(n) = f91(91) = 91.

Implementação

Agora que já entendemos como funciona a função f91, fica um desafio meu! Como seria definida a função f92? E a função f100000000?

817. Dobradura

Olá meus amigos nerds, não se preocupem que eu ainda não esqueci que estou devendo a vocês um post explicando melhor o funcionamento de uma segtree. Como ainda não consegui fazer um post que me agradasse isso vai ficar na minha todo list por mais um tempo.

Enquanto isso, vamos brincar de dobraduras? Hoje vamos ajudar os amigos de Zezinho a resolver o desafio proposto por ele. Como Zezinho gosta muito de matemática, resolveu inventar um quebra-cabeça envolvendo dobraduras. Zezinho definiu uma operação de dobradura D que consiste em dobrar duas vezes uma folha de papel quadrada de forma a conseguir um quadrado com 1/4 do tamanho original. Depois de repetir N vezes esta operação de dobradura D sobre o papel, Zezinho cortou o quadrado resultante com um corte vertical e um corte horizontal e desafiou seus colegas a dizer em quantos pedaços o papel ficou dividido.

Solução

Nesse tipo de problema, geralmente, é possível deduzir uma fórmula fechada para a resposta. E é precisamente isso que vamos fazer agora. Para isso, vamos usar uma técnica que você, provavelmente, já ouviu falar em suas aulas de algoritmos: indução finita.

para N = 0  =>  4   pedaços (o papel não é dobrado)

para N = 1  =>  9   pedaços
para N = 2  =>  25 pedaços

...

Agora vem a parte difícil, que é sacar qual é o padrão oculto nessa sequência de números. A pergunta é: o que 4, 9 e 25 tem em comum. Bem em primeiro lugar eles são quadrados perfeitos. Ok, mas qual a relação deles com n? Ou melhor, qual seria a relação de 2, 3 e 5 com 0, 1 e 2?

Observe que a cada dobra do papel o número de pedaços de papel dobra. Isso sugere que a relação existente tem que ser uma relação exponencial. Depois de pensar um pouco (ou melhor, depois de esperimentar muito) a gente chega a seguinte relação:

f(n) = (2^n + 1)^2

Agora é que começa a aplicação da indução finita. Observe que a fórmula acima vale para N = 0, pois:

f(0) = 4 = (2^0 + 1)^2

... Poderíamos continuar supondo que a fórmula vale para N e tentando a partir disso resolver a fórmula para N+1. Entretanto, nesse problema isso é bem difícil e eu vou deixar isso para vocês pensarem (dica: comece pensando em quantos pedaços o papel fica dividido após as dobras e depois pense me quantos pedaços cada dobra é dividida quando cortamos o papel). Em uma maratona de programação, o que você faria se tivesse boa confiança na sua fórmula mas não conseguisse prova-la formalmente? Sim, isso mesmo, você implementaria o problema já que ele não é difícil de implementar e submeteria. Nesse caso, se você fizer o mesmo, você será recompensado com uma resposta certa.

Implementação

Observe que, como a entrada é pequena, podemos pré calcular todos os valores e armazena-los em um vetor. Nesse problema isso não faz diferença, mas em outros problemas com tempo de execução mais apertado isso pode ser a diferença entre seu problema passar ou tomar TLE.