J'ai pas joué, mais, c'est sympa. Ça ferait des bonnes questions d'entretiens d'embauche :)
1/ Se résout en écrivant une machine à états finis.
2/ L'algo glouton est la solution la plus simple. Ce problème est décrit en détails dans Introduction to Algorithms, par Cormen et al.
3/ Un exemple classique de programmation dynamique. Si tu avais mis dans un cache les résultats des sous-problèmes déjà calculés à une position donnée la chaîne, tu aurais résolu le problème très vite, à mon avis en quelque millisecondes.
En revanche, ça prend pas cinq heures… une heure devrait suffire.
# Sujet intéressant.
Posté par Axioplase ıɥs∀ (site web personnel) . En réponse au message Challenge Codingame n°3. Évalué à 1. Dernière modification le 01 février 2013 à 03:42.
J'ai pas joué, mais, c'est sympa. Ça ferait des bonnes questions d'entretiens d'embauche :)
1/ Se résout en écrivant une machine à états finis.
2/ L'algo glouton est la solution la plus simple. Ce problème est décrit en détails dans Introduction to Algorithms, par Cormen et al.
3/ Un exemple classique de programmation dynamique. Si tu avais mis dans un cache les résultats des sous-problèmes déjà calculés à une position donnée la chaîne, tu aurais résolu le problème très vite, à mon avis en quelque millisecondes.
En revanche, ça prend pas cinq heures… une heure devrait suffire.