Solução Catálogo de Músicas

Solução por Lucca Siaudzionis

Suponha que você saiba o custo de usar uma determinada pasta como referência. Vamos, com isso, calcular o custo de usar uma pasta filha dessa como referência. Seja $$tam$$ o tamanho do nome da pasta, $$n_0$$ o número de arquivos que estão dentro dessa pasta (não necessariamente diretamente dentro) e $$N$$ o número total de arquivos. Então, para esses $$n_0$$ arquivos, teremos uma “economia” de $$tam$$ com relação ao que teríamos que digitar enraizando na pasta pai. Porém, para os outros $$(N – n_0)$$ arquivos, teremos que digitar um acréscimo de $$3$$ caracteres, que é correspondente a digitar “$$../$$”. Então, se $$C$$ é o custo de enraizar na pasta pai, o custo de enraizar na pasta filha será:

$$!C – tam \times n_0 + 3(N-n_0)$$

Como sabemos que o custo de usar o DVD como referência é o tamanho total da entrada, podemos calcular o custo de enraizar em cada pasta usando uma função recursiva e, no fim, selecionamos a pasta de menor custo.

Vamos ao código:

https://gist.github.com/luccasiau/f3e314b0b9011f4f2abc