814. Macaco-prego

Olá meus amigos nerds! Hoje vamos achar o melhor lugar para uma reserva ambiental de macacos prego, já que é isso que o problema 814. Macaco-prego pede para fazer. Mais especificamente, dadas as coordenadas de várias zonas retangulares de um mapa determinar a interseção de todas elas.

Solução

No caso geral esse problema seria bem difícil, mas como só temos retângulos com os lados paralelos aos eixos ele fica mais fácil. Só saber que os retângulos se interceptam também é muito fácil, mas não basta para resolvermos o problema! Precisamos ser capazes de calcular a interseção.

Sejam A e B os dois retângulos que queremos interceptar. Construa um retângulo que contenha A e B e que tenha como pontos extremos os pontos mais distantes de cada retângulo (ou seja, ordena as coordenadas de A e B e pegue o primeiro e último elementos do vetor). Os pontos restantes da ordenação formam um segundo retângulo C que está contido no super retângulo. Esses pontos formam a interseção de A e B, caso ela exista. Para saber se a interseção existe, veja se tanto A quanto B contém o centro de C.

Implementação

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

8781. Floresta

Olá meus amigos nerds. Como não podemos fazer muito para tirar a lama la do rio Doce, hoje vamos, pelo menos, ajudar a plantar algumas árvores. Já que é isso que o problema 8781. Floresta nos pede para fazer. Mais especificamente, dado o número de árvores que se deseja plantar, queremos saber de quantas formas elas podem ser plantadas, respeitando-se as restrições do problema.

Solução

Esse é essencialmente um problema de matemática. Queremos plantar carvalhos formando um quadriculado (um retângulo cheio de carvalhos dentro). Sejam a e b os lados desse retângulo. Então:

# de carvalhos dentro do retângulo = a*b

Como no centro de cada quadradinho de carvalhos temos que plantar um encalipto. O número de encaliptos plantados será:

# de encaliptos plantados = (a-1)*(b-1)

Assim o número total de árvores plantadas será:

n = ab + (a-1)*(b-1)
= 2ab -a -b + 1

resolvendo em relação a b temos:

2ab - b = n + a - 1
b = (n + a - 1)/(2a - 1)

Ou seja, todos os pares de números inteiros da forma [a, (n+a-1)/(2a-1)] satisfazem as condições do problema. Então é só contar quantos pares desses números existem.

Como retângulos axb e bxa não são considerados como elementos distintos, podemos supor que a <= b, assim:

a <= (n + a - 1)/(2a - 1)

donde tiramos a condição de parada do for: 2*a^2 - 2*a + 1 <= n

Implementação

3826. Miojo

Olá meus amigos nerds. Quando se mora sozinho, cozinhar passa a ser um problema, principalmente se você não gosta de jogar comida fora e não tem muito tempo livre (eu que o diga kkk). Uma solução para isso é comer besteiras, tipo miojo. Como somos muito bonzinhos, hoje vamos ajudar o pobre do João a preparar miojos. Já que é isso que o problema 3826. Miojo nos pede para fazer. Mais especificamente, dadas duas ampulhetas (os únicos 'relógios' que ele tem), capazes de medir tempos a e b diferentes e o tempo T necessário para se fazer o miojo, determinar qual será o tempo total gasto para preparar o miojo, incluindo o tempo gasto esperando as ampulhetas estarem em um estado capaz de medir o tempo exato do cozimento do miojo.

Solução

Podemos pensar nesse problema como um problema de decisão. Qual das ampulhetas deve ser virada em seguida para que sejamos capazes de medir exatamente T minutos? Como não podemos inferir a resposta para essa questão, temos que tentar todas as possibilidades e ver qual delas resulta em um menor tempo total.

Os únicos instantes que nos interessam seriam os momentos em que viramos uma ampulheta. Podemos começar virando a ampulheta a, a ampulheta b, ou ambas ao mesmo tempo. Quando uma ampulheta acaba de contar, temos duas opções: (1) vira-la e deixar que ela recomece a contar ou (2) virar as duas ampulhetas, assim a outra ira contar o tempo correspondente a parte da areia que já caiu em seu compartimento inferior. Fazendo-se um backtracking, baseado nessas condições somos capazes de calcular o tempo total.

A condição de parada é que uma das ampulhetas seja capaz de medir exatamente T minutos com a areia remanescente em sua parte superior.

Possivelmente esse problema possui uma solução mais elaborada usando-se teoria dos números (mmc, mdc, etc), mas como a solução por força bruta não é difícil de implementar, resolvi testa-la primeiro e ela se mostrou suficientemente boa para o problema receber um acept.

Implementação

1368. Orkut

Olá meus amigos nerds. Hoje vamos voltar no tempo e ajudar nossa amiga Larissa a adicionar seus amigos no Orkut (muitas recordações? kkk). Já que é isso que o problema 1368. Orkut nos pede para fazer. Mais especificamente, dados os amigos de Larissa e as restrições que eles impõe a ela (na forma de quais outros usuários ela deve ser amiga), para aceitarem seu convite, determine a ordem em que ela deve adiciona-los de modo que todos a aceitem.

Solução

Esse problema implora que usemos grafos para modela-lo (grande novidade, já que eu adoro grafos kkk). Onde os vértices representam os amigos de Larissa e existe uma aresta de a para b se b exige que Larissa seja amiga de a para aceitar seu convite. Observe que esse grafo representa as dependências para que um amigo aceite Larissa.

Em teoria de grafos, existe o conceito de ordenação topológica, que é uma ordenação dos vértices de um grafo de modo que se existe uma aresta ab então  a deve vir antes de b nessa ordenação. Em outras palavras, se enxergarmos as arestas como dependências, todos os vértices que dependem de um vértice (têm uma aresta os ligando) devem vir após ele na ordenação. Oras, mas isso é exatamente o que queremos.

Assim a resposta para o problema é ordenar topologicamente o grafo. Note que pela definição de ordenação topológica o grafo deve ser acíclico, caso contrário seria impossível existir uma ordenação válida. Note ainda, que existem várias ordenações possíveis, basta permutar vértices que não dependem de ninguém em uma ordenação válida, que você obtém outra ordenação válida diferente.

Existem dois algoritmos, relativamente simples, para se obter uma ordenação topológica. Você pode encontrar uma explicação mais detalhada sobre eles aqui. Vou descrever, em linhas gerais, um deles que eu usei para resolver esse problema.

Suponha que o grafo é acíclico. A ideia é fazer uma busca em profundidade começando de algum vértice não visitado ainda. Nessa busca, as dependências de um dado vértice são visitadas depois de ele ter sido visitado. Então se eu escrever os vértices na ordem contrária que eles são visitados isso constituirá em uma ordenação válida.

Implementação

Observe que eu primeiramente verifico se o grafo é acíclico. Isso não seria necessário se eu implementasse com um pouco mais de cuidado a ordenação topológica, mas para os fim desse problema acho que isso é suficiente.

3237. Apagando e ganhando

Olá meus amigos nerds. Hoje vamos tentar descobrir qual é o maior número que podemos formar apagando D dígitos de um número de N dígitos. Já que é isso que o problema 3237. Apagando e ganhando nos pede para fazer.

Eu tenho uma história engraçada com esse problema. Em uma regional da maratona de programação do ICPC eu consegui resolver-lo, mas meu colega de time me convenceu que minha solução estava errada (mesmo estando certa). No final, faltou justamente esse problema para passarmos de fase. Quem mandou eu ser burro kkk.

Solução

Existe uma solução trivial para esse problema:

Seja num o número de N digitos dado
max = 0
while d > 0
    d--
    m = 0
    for i in len(num)
        Seja x o número obtido apagando o i-ésimo digito de num
        m = maximo(x, m)
    max = maximo (m, max)

Obviamente ela não passa no tempo! Isso porque a comparação entre x e m tem complexidade N (o número de bits de x), sendo a complexidade do algoritmo O(d*N^2), o que é muito ineficiente para o problema.

Pense comigo, dados dois números com a mesma quantidade de dígitos, qual deles é maior? Aquele que tem o digito mais a esquerda maior, oras. Essa simples observação nos fornece um algoritmo guloso capaz de responder o problema. Se o primeiro dígito da esquerda for menor que o segundo, a decisão de apagar o primeiro dígito é ótima. Assim:

Seja num uma lista com os N digitos dados
i = num.begin()
j = i++
while i != num.end()
    if == 0
        pare
    if num[i] < num[j]
        apaga(num[i])
    else
        i++

Se conseguirmos apagar os d dígitos usando a observação do parágrafo anterior o problema está resolvido. Pode ocorrer que não consigamos fazer isso, nesse caso, os dígitos do início do número estaram em ordem estritamente decrescente. Basta então repetir o processo acima do fim para o inicio do número para apagar os dígitos que faltam.

Observe que o algoritmo acima é muito mais rápido, tendo complexidade O(N).

Implementação

Observe que em c++ list.erase(it) apaga e invalida o iterador o que nos força a função apaga para evitar problemas.

11016. Reduzindo detalhes em um mapa

Reuso de código é algo muito desejável em engenharia de software. Muitos pensam que isso não é muito comum em maratonas  de programação, mas na verdade tem uma bibliotéca com os algoritmos clássicos implementados ajuda muito.

Hoje aconteceu algo muito engraçado! Como sempre, eu peguei um problema aleatoriamente no spoj e fui resolver (o problema do post anterior :P). Levei pouquissimo tempo para encontrar a solução e quando já tinha a modelagem sabia que precisaria implementar o algoritmo de Kruskal. Eu já havia implementado ele outras vezes. Como é um algoritmo mais longo eu estava com preguiça de fazer isso de novo, então resolvi dar um grep no diretório onde guardo os problemas que já fiz e encontrei tal algoritmo para solucionar o problema 11016. Reduzindo detalhes em um mapa. Até ai tudo normal, mas a coisa engraçada é que o mesmo código (incluindo a parte de entrada e saída) resolvia o problema anterior, ou seja, reuso de código é para os fracos, bom mesmo é reuso de toda a implementação kkk.

Mas especificamente, esse problema pede que dado um mapa de cidades e rodovias que as ligam, selecione um subconjunto das rodovias tal que entre qualquer par de cidades exista uma rota ligando-as e a soma dos comprimentos das rodovias é mínimo.

Solução

Como o problema da árvore geradora mínima e o algoritmo de Kruskal estão fresquinhos em sua cabeça você deve achar esse problema moleza (se não estiverem isso pode ajudá-lo). Não é difícil perceber que o sub conjunto de rodovias pedido é uma árvore. Caso não fosse, ou seja, houvesse algum ciclo no grafo, poderíamos remover a rodovia com maior comprimento o que não causaria a perda da conectividade entre as cidades (sobra o outro caminho) e ainda diminuiria o comprimento total.

Logo a sulução do problema é soma dos pesos da árvore geredora mínima formada.

Implementação

12999. Frete da Família Silva

Olá meus amigos nerds. Hoje vamos ajudar a família Silva a comemorar sua chegada a Marte. Já que é isso que o problema 12999. Frete da Família Silva nos pede para fazer.

Tenho que cumprimentar muito o autor desse problema, ele conseguiu ser extremamente criativo. O problema em si é interessante e o cara fez uma contextualização muito engraçada usando elementos do Chapolim Colorado. Vale até o quote:

"O presidente de Pizzalândia, Lagosta da Silva, ... Resolveu, então, mandar uma família inteira para Marte. No caso, a dele mesmo, a família Silva, provavelmente a mais numerosa do planeta.

Tal família estabeleceu-se em Marte sem problemas, ainda mais com novas invenções que havia por lá. Uma delas era a pílula de nanicolina, substância descoberta naquele planeta, próximo à uma região onde existem pedras voadoras, pedras macias e até pedras falantes. Lendas dizem que algum outro ser extra-terrestre depositou a nanicolina ali num passado distante, enquanto visitava o planeta. O efeito da pílula de nanicolina é a diminuição de tamanho de quem a toma, por um determinado tempo. Tal pílula foi, então, produzida em escala industrial e hoje em dia é distribuída pelos governos marcianos aos colonos que lá residem."

Mas deixando a brincadeira de lado. Mais especificamente, nossa tarefa é determinar o valor mínimo gasto por senhor Lagosta para fazer com que todos os parentes se encontrem.

Solução

Esse é claramente um problema que pede uma modelagem utilizando grafos (colônias = vértices, caminhos = arestas). Além disso, estamos lidando com um grafo ponderado (as 'estradas' tem peso) e conexo, já que sempre existe um caminho entre quaisquer duas colônias.

A primeira coisa a perceber  é que, dada um par de cidades, devemos usar o caminho mínimo entre essas cidades para deslocar todos os colonos de uma cidade para a outra.

Como a capacidade dos ônibus é inimitada, nessa viagem podemos aproveitar para levar todos os colonos que estão nos outro vértices do caminho mínimo,  já que esse também será o caminho mínimo para eles. Disso deduzimos que nenhuma estrada será usada mais que uma vez.

Do paragrafo anterior, também podemos concluir que o sub grafo formado pelos caminhos de todos os colonos até o ponto de encontro é uma árvore. Caso houvesse um ciclo poderíamos retirar a aresta de maior peso desse ciclo e usar o outro caminho restante para levar as pessoas que estavam nos vértices que a aresta foi removida.

Logo a solução para nosso problema é a árvore que tenha o menor custo (i. e. a soma dos pesos das arestas). Esse é um problema bastante famoso em computação chamado problema da árvore geradora mínima e pode ser resolvido utilizando o algoritmo de Kruskal.

O algoritmo de Kruskal, basicamente, ordena as arestas e depois itera sobre a lista ordenada escolhendo de forma gulosa as arestas que fazem parte da árvore. Assim, a complexidade dele é O(num_arestas*log(num_arestas) + num+arestas) = O(num_arestas*log(num_arestas)). Obs: a operação dsf_union tem custo amortizado O(1). Ela é parte da implementação de um conjunto disjunto, um algoritmo capaz  de fazer find e union entre conjuntos de forma eficiente.

Implementação

Veja que, a implementação do algoritmo de Kruskal não é muito complicada. De quebra ainda ganhamos a implementação de um conjunto disjunto de árvores para uso futuro :)

18536. Capital

Olá meus amigos nerds. Hoje vamos brincar de arquitetos e ajudar o senhor Bloggs a planejar uma cidade. Já que é isso que o problema 18536. Capital nos pede para fazer. Mais especificamente, nossa tarefa é determinar, se dados quatro valores de área (a1, a2, a3 e a4) determinar se é possível formar um retângulo que tenha area igual a soma das quatro áreas.

Solução

Problemas de geometria costumam ser bastante complexos, mas esse não é muito difícil. Para começar sabemos de duas coisas: o valor de cada uma das quatro áreas e que elas são necessariamente retangulares. Entretanto não conhecemos os lados de cada retângulo (é isso que queremos determinar).

Note que juntar, quatro áreas (retangulares) e formar um retângulo é equivalente a dado um retângulo dividí-lo em quatro outros retângulos. Vamos, então resolver esse problema. Observe a figura abaixo:

Onde temos um retângulo de lados a e b. Observe que:

a = x1 + x2
b = y1 + y2

Sejam A1, A2, A3 e A4 as quatro áreas dadas. Da figura, podemos escrever as áreas como:

x1*y1 = A1
x2*y1 = A2
x1*y2 = A3
x2*y2 = A4

Note que temos quatro variáveis e quatro equações, mas infelizmente esse não é um sistema linear. Mesmo assim podemos isolar y1 nas duas primeiras equações (supondo x1 e x2 diferentes de 0):

y1 = A1/x1
y1 = A2/x2

O que implica:

A1/x1 = A2/x2 => A1*x2 = A2*x1 => A1*x2 - A2*x1 = 0

Fazendo o mesmo para y2:

y2 = A3/x1
y2 = A4/x2

O que implica:
A3/x1 = A4/x2 => A3*x2 = A4*x1 => A3*x2 - A4*x1 = 0

O que resulta no seguinte sistema homogêneo:
A1*x2 - A2*x1 = 0
A3*x2 - A4*x1 = 0

Se o sistema possuir solução única ela será trivial (x1=x2=0). Essa solução não nos serve! Já que supusemos que x1, x2, x3 e x4 eram diferentes de 0 no inicio de nossa dedução. Ou melhor, essa solução indica que não é possível construir o retângulo com as quatro áreas dadas.

Nos resta ainda a possibilidade de esse sistema ter infinitas soluções (lembre-se, um sistema homogêneo nunca é impossível). Nesse caso podemos escolher algum x1, x2, diferentes de 0 (e maiores que 0, já que se tratam de lados de um retângulo). Para isso, o determinante da equação deve ser nulo, ou seja:

A1*A4 == A2*A3

Eu queria dizer que já está resolvido, mas falta ainda uma parte importante. Em nossa discussão supusemos que conhecíamos A1, A2, A3 e A4, mas na realidade não conhecemos a ordem em que as áreas devem ser testadas na equação acima, sendo assim temos que testar todas as permutações para ter certeza que alguma satisfaz a equação.

Implementação

Quem vê esse código até pensa que o problema é muito fácil! Ledo engano...

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

1353. Festa Junina

Olá meus amigos nerds, hoje vamos ajudar o diretor de uma escola a montar uma comissão para realização de sua tradicional festa junina, já que é isso que o problema 1353. Festa Junina nos pede para fazer.

Mais especificamente, dada uma lista de alunos e as relações de ódio entre eles (que triste rsrs), determinar qual é o número máximo de integrantes que a comissão da festa pode ter, se ela for formada pelos alunos da lista.

Solução

Esse é um problema bastante interessante. Uma solução baseada em testar todos os conjuntos de alunos possíveis é bem fácil de ser pensada, entretanto apresenta o problema de o número de partições de um conjunto ser exponencial (2^n). Tentemos então encontrar soluções melhores!

Vamos resolver esse problema usando uma modelagem por grafos. Cada vértice do grafo representa um aluno da lista. Existe uma aresta entre dois vértices, caso um dos alunos que aqueles vértices representam odeio o outro. Em outras palavras, esse grafo representa as relações de ódio entre os alunos. Observe que para uma comissão ser válida não podem haver arestas no grafo que liguem os membros da comissão, ou seja, as comissões válidas são os conjuntos independentes existentes no grafo. Logo o problema se resume a achar o conjunto independente máximo do grafo.

Achar o conjunto independente máximo é o problema dual de achar a clique máxima (um conjunto independente é uma clique (sub grafo completo) no grafo complementar). Mas por que eu estou falando isso? Se você já estudou um pouco de teoria de complexidade, você já deve ter ouvido falar que o problema da clique máxima é NP-completo. Sendo assim, estamos diante de um problema que a melhor solução que conhecemos tem complexidade exponencial.

Assim a ideia que mencionei no primeiro parágrafo apesar de ineficiente é ótima. Observando que o tamanho máximo da entrada é 20 mesmo uma solução assim é capaz de passar no tempo no spoj. O seguinte algoritmo implementa tal ideia:

construa o grafo de relações de odio entre os alunos
tamanhoMaximoGrupo = 0
para cada conjunto de alunos
   Seja S esse conjunto
   para cada a em S
     para cada b em S
        se existe a aresta a->b ou b->a no grafo
          conjunto invalido
   tamanhoMaximoGrupo = max(tamanhoMaximoGrupo, |S|)

Implementação

A solução abaixo utiliza um backtracking para implementar o algoritmo acima. Ela é basicamente, um algoritmo de enumeração de conjuntos.

Uma ideia um pouco mais elaborada é utilizar um bitset para representar os conjuntos. A implementação abaixo é baseada nisso. A ideia é iterar de 1 a 2^n e utilizando a representação binária do iterador como a representação do conjunto. Embora um pouco mais eficiente ela também é mais propícia a erros, já que operações com bits as vezes são traiçoeiras.

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.

1824. Monitorando a Amazônia

Olá meus amigos nerds, vocês acharam que essa semana não ia ter um probleminha? Se sim, se enganaram! Eu queria ter postado esse probleminha na quarta, mas vocês hão de convir comigo que seria uma pena perder os jogos dos dois melhores times do Brasil da atualidade... Deixando de papo furado, que a diversão comece!

Hoje vamos resolver o problema 1824. Monitorando a Amazônia, que nos pede para verificar se é possível enviar uma mensagem de uma estação de comunicação central para todas as outras estações de comunicação espalhadas pela amazônia. Sendo que, cada estação se comunica apenas com as duas estações mais próximas a ela.

Solução

Conceitualmente esse não é um problema difícil. Se pensarmos a rede de comunicação como sendo um grafo (direcionado), basta verificarmos se todos os vértices são alcançáveis, a partir do vértice que representa a estação central. Isso pode ser feito, facilmente, usando-se uma busca em profundidade. 

Note que, o problema pede apenas para verificar se é possível enviar uma mensagem a partir da estação central. Caso se pedisse para verificar a viabilidade da comunicação entre qualquer par de estações, o problema seria um pouco mais complexo. Nesse caso teríamos que verificar se o grafo possuía apenas um componente fortemente conectado, o que poderia ser feito usando-se o algoritmo de Tarjan.

O seguinte algoritmo resolve o problema

calcule a distância entre cada par de estações
Seja G um grafo onde os vértices representam as estações
para cada estação
    Sejam a e b as estações mais próximas a est
    adicione a aresta est -> a a G
    adicione a aresta est -> b a G
faça uma busca em profundidade a partir do vértice que representa a estação principal marcando todos os vertices visitados
if todos os vértices foram marcados
    print "All stations are reachable."
else
    print "There are stations that are unreachable."

Implementação

Observe que evitamos o uso de números de ponto flutuante trabalhando com o quadrado da distância. Em alguns problemas isso pode ser bem útil.

Observe ainda, que abrimos mão de alguma elegância no código em favor de não armazenar as distâncias entre cada par de estações. Sendo assim vou aproveitar e deixar um pequeno desafio para você: o código abaixo contém 2 bugs, quanto tempo você levaria para encontrá-los?

Obs: Caso você tenha dificuldade em encontrar os bugs use o diff :)