842. Torres de Hanói

Olá meus amigos nerds, vocês sabiam que há uma lenda que diz que quando alguém conseguir resolver o problema das torres de Hanói usando 64 discos o mundo acabará? Hoje, vamos descobrir se essa lenda é verdadeira ou não ao resolver o problema 842. Torres de Hanói.

O conhecido quebra-cabeça consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação.

Na realidade esse problema não nos pede para resolver o desafio das torres de hanói, inclusive ele nos apresenta a solução do mesmo e nos pede para que computemos o número de operações necessárias para solucionar o quebra cabeça.

Hanoi(N, Orig, Dest, Temp)

   se N = 1 então

      mover o menor disco do pino Orig para o pino Dest;

   senão

      Hanoi(N-1, Orig, Temp, Dest);

      mover o N-ésimo menor disco do pino Orig para o pino Dest;

      Hanoi(N-1, Temp, Dest, Orig);

Solução

Do algorítimo acima tiramos a seguinte relação de recorrência:

Hanoi (N) = 2*Hanoi(N-1) + 1

Expandindo a recorrência mais um pouco temos:

Hanoi (N) = 2*(2*Hanoi(N-2) + 1) + 1 = 4*Hanoi(N-2) + 2+1 = 8*Hanoi(N-3) + 4 + 2 + 1

Observe que, após "resolvermos" a expressão acima i vezes ela poderia ser escrita da seguinte forma:

Hanoi(N) = 2^i * Hanoi (N - i) + [sum 2^(x - 1) para x de 1 a i]

quando i == N temos:

Hanoi(N) = 2^N * Hanoi (0) + [sum 2^(x - 1) para x de 1 a N]

Mas Hanoi(0) = 0 já que se não houver peças não precisamos mover nada. Por outro lado [sum 2^(x - 1) para x de 1 a N] = 2^(N-1) - 1. Logo:

Hanoi(N) = 2^(N-1)

É interessante notar, que há uma outra solução bem obvia para o problema: Implementar e instrumentar o algoritmo acima e contar o número de movimentos na força bruta. Como você pode ver, pela ordem de grandeza do número de operações, essa solução certamente seria muito ineficiente e receberia um TLE.

Só por curiosidade, a lenda é verdadeira, se alguém gastasse 1 segundo para mover um disco, 2^64  = 1.8446744e+19 segundos é muito mais tempo que a idade do universo.

Implementação

2844. Você pode dizer 11

Olá meus amigos nerds,  mais uma vez, vamos ver como coisas que aparentemente são fáceis podem se tornar um pouco mais difíceis quando estamos lidando com entradas de tamanho um pouco maior. Para isso, vamos resolver o problema 2844. Você pode dizer 11, que nos pede para verificar se um número é divisível por 11.

Solução

print x%11 == 0

Trivial. Infelizmente não é assim que funciona. A entrada pode conter números de até 1000 dígitos, enquanto um uint64_t tem mais ou menos 18 dígitos. Ai você se lembra, que tem a disposição a sua biblioteca de big int, vai lá copia e cola o código dela e tenta de novo e recebe, como resultado por não ter pensado bem a respeito, um belo de um TLE.

Lição dada é lição aprendida. Sempre tenha cuidado quando o problema envolver entradas grandes o suficiente, pois elas sempre podem trager surpresas.

Nesse momento, é hora de nos lembrarmos daqueles critérios de divisibilidade, que nos permitem saber se um número é divisível por outro sem a necessidade de fazer a conta. E para nossa sorte, o critério de divisibilidade por 11 não só existe, como também é linear no número de bits do número.

Um número é divisível por 11 caso a soma dos algarismos de ordem par menos a soma dos algarismos de ordem ímpar seja divisível por 11. A prova dessa regra é bem simples e envolve aritmética modular.

10 = 11 - 1 <=> 10 == -1 mod 11

qualquer número pode ser escrito como uma soma de potências de 10

 10^n*a_n + 10^(n-1)*a_(n-1) ... + 10*a_1 + a_0

ou tomando essa soma em mod 11

(-1)^n*a_n + (-1)^(n-1)*a_(n-1) ... + (-1)*a_1 + a_0 == 

- a_n + a_(n-1) - ... - a_1 + a_0 == soma dos dígitos pares - soma dos dígitos ímpares

Implementação

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?