J'ai essaye mais il ne semble pas possible de livrer les sujets sans s'inscrire. Et a la fin de chaque probleme, il y a un gros copyright.
Je peux quand meme parler des types de problemes. L'avant dernier jeu de problemes etait pas mal:
pb facile:
Soit:
- A tq 10 <= A <= 100000
- B tq A <= B <= 100000
- A-B <= 1000
- trouver le nombre d'entiers entre A et B tq si v est un nb qu'on cherche, il n'y a aucun nombre premier entre v-10 et v+10 inclus
Rappel: temps d'execution en moins de deux secondes.
Exemple :
97001
97691
Returns: 89
La bonne methode, c'est de faire un crible d'Eratosthene. Sinon, meme en y allant bourrin, ca marche. Genre tu iteres sur tous les nombres entre A et B, et pour chacun de ces nombres tu vas de nombre-10 a nombre+10 et pour chacun de ces sous-nombres, tu verifies s'il est premier. J"ai gagne des points en cassant une solution qui faisait (A-B)*20 verifications de nombre premier, sans optimiser ou cacher la recherche de nombre premier en java et qui au final prenait plus de 2 secondes. Des que tu optimises un minimum (cache facon Eratosthene) ou tentative de division par tous les nombre jusqu'a sqrt(n), ca passe en 2 secondes.
Ca parait choquant d'etre bourrin, mais le but, c'est de coder ca en moins de 10 minutes.
Probleme moyen:
Tu plies un carre en 2 jusqu'a obtenir un triangle faisant 1/8 de ton carre original (le dernier pli est en diagonal). Tu fais des trous sur ce triangle, et il faut generer le carre deplie avec les trous.
L'entree est un vector qui represente le triangle avec des * pour les trous et des . pour les non-trous.
C'etait plutot facile, il suffit de faire des symetries dans tous les sens.
Probleme difficile:
Tu as une suite de chambres. Chaque piece contient un interrupteur qui controle la lumiere dans une autre piece. Tu commences avec la premiere piece allumee. Tu peux aller a tout moment dans n'importe quelle piece du moment que la lumiere est deja allumee et tu ne peux pas eteindre la lumiere dans ta propre piece. Tu veux fnir avec la lumiere allumee dans la derniere piece uniquement. Retourner le nombre minimal de deplacement necessaires, ou -1 si c'est pas possible.
Celui-la etait coton. Mais j'avais deja vu un probleme dans le meme style. Chaque etat global de tes pieces peut etre represente sous forme d'un entier, avec un bit par piece + une valeur entre 0 et 15 pour ta position. Tu veux partir de l'etat 1e piece allumee, present dans la premiere piece, jusqu'a l'etat derniere piece allumee, present dans la derniere piece. C'est donc un graphe dans lequel tu cherches le chemin le plus court. Pour un etat donne, il est facile de trouver tous les etats que tu peux rejoindre : le meme etat avec l'interrupteur qui a bascule (cout 0) ou bien le meme etat mais present dans une autre piece allumee (cout 1). Un petit coup de djikstra et tu trouves le chemin le plus court.
A coder en une heure, je peux te dire que tu n'a pas le temps de respirer.
[^] # Re: Question bête
Posté par Philippe F (site web personnel) . En réponse au journal Topcoder. Évalué à 4.
Je peux quand meme parler des types de problemes. L'avant dernier jeu de problemes etait pas mal:
pb facile:
Soit:
- A tq 10 <= A <= 100000
- B tq A <= B <= 100000
- A-B <= 1000
- trouver le nombre d'entiers entre A et B tq si v est un nb qu'on cherche, il n'y a aucun nombre premier entre v-10 et v+10 inclus
Rappel: temps d'execution en moins de deux secondes.
Exemple :
97001
97691
Returns: 89
La bonne methode, c'est de faire un crible d'Eratosthene. Sinon, meme en y allant bourrin, ca marche. Genre tu iteres sur tous les nombres entre A et B, et pour chacun de ces nombres tu vas de nombre-10 a nombre+10 et pour chacun de ces sous-nombres, tu verifies s'il est premier. J"ai gagne des points en cassant une solution qui faisait (A-B)*20 verifications de nombre premier, sans optimiser ou cacher la recherche de nombre premier en java et qui au final prenait plus de 2 secondes. Des que tu optimises un minimum (cache facon Eratosthene) ou tentative de division par tous les nombre jusqu'a sqrt(n), ca passe en 2 secondes.
Ca parait choquant d'etre bourrin, mais le but, c'est de coder ca en moins de 10 minutes.
Probleme moyen:
Tu plies un carre en 2 jusqu'a obtenir un triangle faisant 1/8 de ton carre original (le dernier pli est en diagonal). Tu fais des trous sur ce triangle, et il faut generer le carre deplie avec les trous.
L'entree est un vector qui represente le triangle avec des * pour les trous et des . pour les non-trous.
Exemple :
{"*",
"..",
".*.",
".**.",
".*.**"}
Returns:
{"**.*..*.**",
"*.**..**.*",
".*.*..*.*.",
"***....***",
"....**....",
"....**....",
"***....***",
".*.*..*.*.",
"*.**..**.*",
"**.*..*.**" }
C'etait plutot facile, il suffit de faire des symetries dans tous les sens.
Probleme difficile:
Tu as une suite de chambres. Chaque piece contient un interrupteur qui controle la lumiere dans une autre piece. Tu commences avec la premiere piece allumee. Tu peux aller a tout moment dans n'importe quelle piece du moment que la lumiere est deja allumee et tu ne peux pas eteindre la lumiere dans ta propre piece. Tu veux fnir avec la lumiere allumee dans la derniere piece uniquement. Retourner le nombre minimal de deplacement necessaires, ou -1 si c'est pas possible.
Maximum 16 pieces.
Exemple:
{7, 11, 1, 12, 6, 3, 0, 2, 6, 0, 0, 5, 9}
Returns: 15
Celui-la etait coton. Mais j'avais deja vu un probleme dans le meme style. Chaque etat global de tes pieces peut etre represente sous forme d'un entier, avec un bit par piece + une valeur entre 0 et 15 pour ta position. Tu veux partir de l'etat 1e piece allumee, present dans la premiere piece, jusqu'a l'etat derniere piece allumee, present dans la derniere piece. C'est donc un graphe dans lequel tu cherches le chemin le plus court. Pour un etat donne, il est facile de trouver tous les etats que tu peux rejoindre : le meme etat avec l'interrupteur qui a bascule (cout 0) ou bien le meme etat mais present dans une autre piece allumee (cout 1). Un petit coup de djikstra et tu trouves le chemin le plus court.
A coder en une heure, je peux te dire que tu n'a pas le temps de respirer.