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...

844. Número de Erdos

Olá meus amigos nerds. Hoje vamos resolver um dos primeiros problemas que me apresentaram a essa vida de resolver problemas. Vamos tentar descobrir qual é nosso número de Erdos, já que é isso que o problema 844. Número de Erdos nos pede para fazer. Mais especificamente, nossa tarefa é determinar, a partir de uma lista de autores de artigos, o número de Erdos dos autores.

Nesse problema, vale a pena até contar mais um pouco de história. O matemático húngaro Paul Erdos (1913-1996), é considerado o matemático mais prolífico da história, devido ao seu alto número de publicações (mais de 1500). Em homenagem a este gênio húngaro, os matemáticos criaram um número, denominado "número de Erdos". Toda pessoa que escreveu um artigo com Erdos tem o número 1. Todos que não possuem número 1, mas escreveram algum artigo juntamente com alguém que possui número 1, possuem número 2. E assim por diante. Quando nenhuma ligação pode ser estabelecida entre Erdos e uma pessoa, diz-se que esta possui número de Erdos infinito. Por exemplo, o número de Erdos de Albert Einstein é 2. E, talvez surpreendentemente, o número de Erdos de Bill Gates é 4.

Solução

Outro problema que a solução é uma busca em largura! Mas por motivos históricos, não resisti a tentação de escrever ele. Dado um grafo onde os vértices representam os autores e existe uma aresta entre dois vértices se os autores publicaram juntos, o tamanho do caminho mínimo entre o cada vértice e o vértice que representa Erdos é o número procurado. Como todas as arestas tem o mesmo peso (o grafo não é ponderado), uma simples busca em largura resolve.

Implementação

Que código feio, mas vocês tem que me perdoar já que ele foi escrito há muitos anos atrás.

19948. PacMan

Olá meus amigos nerds. Hoje vamos brincar de Pacman, já que é isso que o problema 19948. PacMan nos pede para fazer. Mais especificamente, dadas as posições do pacman, comida e fantasmas determinar quantos pontos o pacman consegue fazer.

Solução

Vou confessar que não resisti a tentação de escrever sobre um problema com esse nome, mesmo que ele seja muito fácil (o que obviamente eu só descobri após o ler :P). Basta iterar sobre a matriz que representa o campo de jogo e contar quantos pontos o jogador faria usando a estratégia descrita no problema. É só zerar os pontos se ele encontrar um fantasma, e imprimir no final a maior quantidade de pontos que ele fez.

Implementação

2609. Trilhas

Olá meus amigos nerds. Hoje vamos brincar fazer trilhas, já que é isso que o problema 2609. Trilhas nos pede para fazer. Mais especificamente, dadas as informações sobre distâncias e altitudes de um conjunto de trilhas, determinar qual é a trilha que exige o menor esforço de subida. Onde o esforço de subida é proporcional ao desnível do trecho percorrido.

Solução

O problema não nos diz como calcular o esforço de subida, mas apenas que ele é proporcional ao desnível do trecho, em outras palavras à altura do trecho subido. Ora mas se o esforço é proporcional a cada uma das alturas ele será proporcional a soma delas. Sendo assim, o problema fica bem fácil, basta calcular a soma das alturas. Para isso, é só percorrer o vetor com a altura dos trechos e ir fazendo as diferenças entre dois trechos seguidos.

Um detalhe importante é que ele não se importa com o sentido do trecho, assim sendo devemos calcular o desnível do terreno considerando que ele pode estar indo do trecho a para o b, ou vice versa.

A resposta final será a opção de trilha com a menor soma das alturas.

Implementação

11006. Colorindo

Olá meus amigos nerds. Dizem que livrinhos de colorir estão na moda hoje em dia. Se isso é verdade eu não sei, mas sei que hoje vamos brincar de colorir alguns, já que é isso que o problema 11006. Colorindo nos pede para fazer. Mais especificamente, dados um desenho quadriculado e um ponto que se deseja começar a colorir, devemos determinar quantos quadrados desse desenho serão coloridos no total sendo que se eu colorir um quadrado devo colorir todos os seus vizinhos a menos que eles já estejam coloridos.

Solução

Esse é um problema bem simples. O processo de colorir descrito no problema é exatamente uma busca em largura, feita sobre o papel quadriculado. Sendo assim basta executarmos a busca e contarmos quantos quadradinhos serão coloridos ao final do processo.

Implementação

Lembram que no problema anterior eu preenchi as bordas da matriz com 0's. Vejam que nesse problema, como eu não fiz isso a cada iteração do loop eu tenho que ficar checando se x e y estão de fato dentro da matriz.

18538. Robô

Olá meus amigos nerds. Hoje vamos determinar onde um robô de limpeza deve parar depois de limpar um salão. Meio chato, mas nem só de coisas legais vive o mundo, né! Já que é isso que o problema 18538. Robô nos pede para fazer. Mais especificamente, dados um mapa indicando a cor de cada ladrilho no chão e a posição inicial do robô, devemos determinar a posição final do robô que só se locomove através de ladrilhos pretos.

Solução

Esse é um problema bem simples. Basta simularmos a trajetória do robô. Para isso, basta ir iterando sobre a posição atual do robô procurando pela próxima posição válida. Para não correr o risco de voltar pelo mesmo caminho que o robô veio, basta ir apagando o caminho a medida que ele vai sendo percorrido.

Implementação

Observe como envolvo a minha matriz com 0's (sentinelas) para evitar que a busca saia dos limites da matriz e eu tenha que ficar verificando isso no código.

12939. Păo a metro

Olá meus amigos nerds. Hoje vamos brincar de cortar pães para fazermos sanduíches que serão usados durante uma maratona de programação. Isso mesmo! Já que é isso que o problema 12939. Pão a metro nos pede para fazer. Mais especificamente, dados os tamanhos de pão disponíveis (em centímetros) e a quantidade de pessoas a serem servidas, queremos saber o tamanho inteiro máximo (em centímetros) da fatia que pode ser cortada de maneira a atender todas as pessoas.

Solução

A solução simples para esse problema seria tentar todos os tamanhos possíveis para os pães e escolher o maior. Entretanto, isso, é claro, não é eficiente o suficiente.

Suponha que conheçamos o tamanho de pão máximo. Para tamanhos superiores de pão não conseguimos servir as n pessoas (caso contrário por contradição esse tamanho não seria máximo). Assim, ao invés de procurar por força bruta o tamanho ótimo, podemos aplicar busca binária ao problema, uma vez que temos uma propriedade que é verificada para valores inferiores a um número (o tamanho máximo), mas não o é para valores inferiores.

Agora só nos falta definir os limites nos quais queremos aplicar busca binária. Obviamente, o tamanho mínimo de pão é 1. Já o máximo é o maior tamanho entre as k fatias de pão (lembre-se de que não podemos juntar duas fatias).

Implementação

Observe que o código testa duas condições de contorno. Uma delas é o pão de tamanho 1 (limite inferior do intervalo) e outra o pão de tamanho k (todos os pedaços são do mesmo tamanho).