|
|
Problema C - Prince's Highway |
Autor: Cristina Vieira e Pedro Guerreiro(Universidade do Algarve)
Tipo de problema: Sequência de Fibonacci (programação dinâmica)
Este problema era provavelmente o mais fácil do concurso e foi feito precisamente com essa intenção, tendo sido realmente o que foi resolvido por mais equipas.
Na prática, a solução era literalmente a muito conhecida números de Fibonacci, que todos os alunos universitário desta área já devem ter encontrado por várias vezes.
Mesmo que não tivessem "notado" que a solução era essa, resolvendo o problema com "força bruta" para os números mais pequenos (gerando mesmo todas as possibilidades de preenchimento), resultaria óbvio que a lógica da sequência era essa. Aliás, esta é uma técnica que pode e deve ser usada em concurso quando não se consegue progredir doutra forma: mesmo que seja sabido que a solução bruta não passa no tempo, podem e devem implementá-la para duplamente: tentar perceber a relação necessária para a solução eficiente; usar os resultados para validar a solução eficiente nos casos pequenos.
Por uma questão de perceber o porquê da solução serem os números de Fibonacci, considere-se ways[i] como sendo o número de maneiras de preencher um rectângulo de Nx2 com rectângulos de 2x1. Pode-se preencher colocando um rectângulo na vertical (e depois preenche-se o rectângulo de (N-1)x2 restante), ou então colocando dois na horizontal (e depois preenche-se o rectângulo de (N-1)x2 sobrante). Por outras palavras, ways[i] = ways[i-1]+ways[i-2]. Os casos base de i=1 ou 2 são fáceis de perceber.
Finalmente, era necessário não calcular os números de Fibonacci da forma "naive", recursiva. Uma hipótese intuitiva era calcular iterativamente, mantendo sempre em memória os últimos dois números.
Ligações interessantes: