domingo, 25 de agosto de 2013

Abstraindo um problema

Os enunciados dos exercícios escondem o tesouro, e você deve estar atento as pistas (mas apenas as importantes).

Nesse post vou citar um exemplo de como abstrair um exercício, ou seja, ignorar todas as informações inúteis e saber identificar os pontos chaves que nos levam à resolução. Isso inclui identificar pistas "falsas" ou "desnecessárias".

O exercício que vou usar como exemplo aqui é o Fechem as portas! (http://www.urionlinejudge.com.br/judge/problems/view/1371).

Antes de continuar, leiam o enunciado do exercício, e tirem suas conclusões iniciais.
Considerando que todas as portas estão inicialmente fechadas (todos os descendentes fecham as portas antes de descer para o jardim) e que cada descendente entra exatamente uma vez na mansão (a confusão é tão grande que não sabemos em que ordem), quais portas estarão abertas após a entrada de todos os descendentes na mansão?
Pista falsa: "(a confusão é tão grande que não sabemos em que ordem)".
A ordem em que eles entram não faz a menor diferença, visto que todos vão entrar e vão abrir (ou fechar) suas respectivas portas. Veja, se o estado da porta 3 vai ser trocado pelo descendente 1 e 3, nesta ordem, temos um total de duas trocas, e se vai ser trocado pelo descendente 3 e 1, nesta ordem, temos ainda um total de duas trocas, ou seja, a ordem é indiferente, e o total é o mesmo.

Objetivo: Descobrir quantas portas terminarão abertas.
Solução? Força bruta? Não! Veja, temos um valor máximo de 25milhões de portas e descendentes, um valor extremamente alto para se pensar em força bruta.

Pensem comigo: uma porta ou está fechada, ou está aberta, e seu estado troca de um para o outro apenas. Se inicia fechada, com uma troca de estados vai para aberta, e com duas volta para fechada. Se continuarmos nesse ritmo, notaremos que um número par de trocas de estados faz com que a porta termine fechada, e um número ímpar de trocas de estados faz com a porta termine aberta.

A porta número 3 vai ter seu estado trocado por dois descendentes. Vimos que a ordem não importa, o que nos importa mesmo é o número de vezes em que ela vai ter seu estado trocado. No caso da porta número 3, duas vezes. Como vimos no parágrafo anterior, quando o estado da porta é trocado um número par de vezes, ela terminará fechada, portanto temos uma resposta: terminará fechada.

Abstração: Descobrir o número Q de divisores de um valor N, e, com base nesse valor Q, imprimir N ou não.

Exemplo: Vamos descobrir o número de divisores dos valores de 1 até 10.
N                     Q
1: 1               = 1
2: 1, 2           = 2
3: 1, 3           = 2
4: 1, 2, 4       = 3
5: 1, 5           = 2
6: 1, 2, 3, 6   = 4
7: 1, 7           = 2
8: 1, 2, 4, 8   = 4
9: 1, 3, 9       = 3

Solução: Os valores N tal que o número Q total de divisores de N é impar -> 1, 4 e 9.

Abstraído o problema, resta encontrar uma forma eficaz de descobrir esse valor Q, mas com um pouco de observação, é fácil encontrar o padrão. Vou deixar essa tarefa pra vocês.

Nenhum comentário:

Postar um comentário