résolution de projet Euler # 305

Problem # 305 résolution de projet Euler # 305

appel de Soit S la chaîne (infinie) qui est faite par concaténer les entiers positifs consécutifs (à partir de 1) écrit dans la base 10.

Ainsi, S = 1234567891011121314151617181920212223242 ...

Il est facile de voir que tout nombre va afficher une n nombre infini de fois dans S.

appel de Soit f (n), la position de départ de la nième occurrence de n dans S. Par exemple, f (1) = 1, f (5) = 81, f (12) = 271 et f (7780) = 111111365.

Trouver Summation [f (3^k)] pour 1 < = k < = 13.

Comment puis-je aller sur la résolution de ce sujet?

Source

2010-10-14 John Joskee

partez-vous toujours d'un nouveau S? Je demande parce que intuitivement la 3ème occurrence de 3 devrait être à la gauche de la 9ème occurrence de 9, qui devrait être à la gauche de la 27ème occurrence de 27, etc. Ainsi, vous devriez pouvoir passer le dernier état de S pour une valeur donnée de 3^k à l'appel de fonction pour 3^(k + 1) et ajustez la logique de votre algorithme en conséquence. –

Si je sauvegarde l'état de s, la recherche dans s prendrait du temps aussi. Ai-je raison? –

Mon estimation du temps de fonctionnement est O (n log n), donc cette approche de force brute n'est pas réalisable. Notez que vous êtes censé résoudre vous-même les problèmes du projet Euler, ce qui est particulièrement vrai pour les nouveaux problèmes.

Source

2010-10-14 16:51:06 starblue

Calculer S à une taille arbitraire est trompeusement facile, mais comme vous l'avez probablement déjà découvert, pas pratique, il devient simplement trop grand. Comme c'est souvent le cas pour les nouveaux problèmes de Project Euler, la force brute ne fonctionne tout simplement pas. Cela dit, vous pouvez toujours regarder S pour les petites valeurs de k et peut-être construire une formule qui résoudra le problème en parties (les premières valeurs sont faciles à gérer en mémoire). En outre, regardez Problème 40

Remarque: n'oubliez pas la règle d'une minute. (la plupart des problèmes peuvent être résolus en quelques millisecondes)

Source

2010-11-23 14:03:09 klang

Répondre

Questions connexes