XXVI Olimpíada Brasileira de Informática
Dona Pulga
Dona Pulga move-se de uma forma peculiar, sempre em linha reta. Ela não gosta de se distanciar muito de sua casa, e pula exatamente três vezes para ir a qualquer destino. Quando sai de sua casa, ela pode escolher ir inicialmente para a direita ou para a esquerda, e dá um pulo nessa direção. Depois do primeiro pulo, o próximo pulo é sempre na direção oposta do último pulo. Ou seja, ela pula nas direções (direita, esquerda, direita) ou (esquerda, direita, esquerda). Além disso, cada pulo é feito com a distância de ou 1, ou 2 ou 3 metros. No entanto, uma vez que tenha pulado uma dessas distâncias, ela não pula novamente essa mesma distância, sempre escolhe uma outra distância (entre 1, 2 ou 3 metros).
Por exemplo, para chegar ao destino marcado como X, ela pode- pular dois metros para a direita
- pular um metro para a esquerda
- pular três metros para a direita.