train circulaire
vacelet
d'erreurs, auquel cas, n'hesitez pas
a poser des questions, pour lesquelles je me ferais un plaisir de
repondre par oui ou non.
Imaginez un train, sans locomotive. Il n'y a donc que des wagons.
Ces wagons sont disposés de manière circulaire.
On peut passer d'un wagon à un autre, grâce a des portes qui les
relient.
L'objectif est de compter le nombre de wagons.
Pour cela vous disposez d'une craie et d'un chiffon.
Il est à savoir que vous êtes seul dans le train, et que les wagons
peuvent contenir
différents tag a n'importe quel endroit.
Par exemple, dessiner une croix sur le sol et aller sur la gauche
jusqu'à en trouver une ne permet pas
de compter le nombre de wagon, car un tagueur aurait bien pu mettre une
croix similaire.
Nicolas
Orabīg
"vacelet" <vac...@lifc.univ-fcomte.fr> a écrit dans le message de news:
3C8DD5BC...@lifc.univ-fcomte.fr...
Zut, les contraintes sont assez difficile à comprendre.
En gros, si je trouve une marque, je ne suis pas certain que ce ne soit pas
une marque que j'ai fait moi ?
Est-ce que mon chiffon peut effacer une marque que j'ai posé ?
Est-ce que mon chiffon peut effacer un tag ?
Est-ce que je peux faire ma signature sur un wagon ?
--
Orabîg qui cherche à comprendre l'énoncé avant de réfléchir au problème
Jérôme Grimbert
> Par exemple, dessiner une croix sur le sol et aller sur la gauche
> jusqu'à en trouver une ne permet pas
> de compter le nombre de wagon, car un tagueur aurait bien pu mettre une
> croix similaire.
Oui, mais le taggeur n'aura pas laisser un chiffon avec une craie dedans.
Donc on laisse le chiffon à un endroit, et on fait le tour jusqu'a retrouver son chiffon.
Vigor
tentative de réponse plus bas
et si on faisait plusieurs passages. (on est bien tout seul dans le train,
hein?!)
Premier passage je fait 1 rond et une croix (par exemple) devant chaque
porte. A un moment donné, je vais à nouveau les rencontrer vu que le train
est circulaire. Je continue un peu à avancer pour vérifier.
Au deuxième passage j'efface avec le chiffon le rond (par exemple) jusqu'à
ce que je rencontre à nouveau la croix seule. Comme j'aurai compté les ronds
effacés, je saurai combien il y a de wagons!
Virginie
Ca me parrait bien simple comme solution!
vacelet
> En gros, si je trouve une marque, je ne suis pas certain que ce ne soit pas
> une marque que j'ai fait moi ?
c'est ca.
> Est-ce que mon chiffon peut effacer une marque que j'ai posé ?
oui
> Est-ce que mon chiffon peut effacer un tag ?
oui
> Est-ce que je peux faire ma signature sur un wagon ?
oui, mais rien ne prouve qu'un tagueur ait fait la meme signature.
vacelet
>
> Bonjour à tous,
>
> tentative de réponse plus bas
>
> et si on faisait plusieurs passages. (on est bien tout seul dans le train,
> hein?!)
> Premier passage je fait 1 rond et une croix (par exemple) devant chaque
> porte. A un moment donné, je vais à nouveau les rencontrer vu que le train
> est circulaire.
--> ou rencontrer ceux laissé par d'autres
"Je continue un peu à avancer pour vérifier."
--> "un peu"
C'est un peu vague. Non la solution est logique ...
FeliX
d'ariane, et quand je trouve une ligne similaire, je fais demi tour pour
revenir au depart (que je connais) pour savoir si c ma ligne (et donc si
j'ai boucle le tour) ou si c'est celle de qq1 d'autre (auquel cas je
continue d'avancer)
et comme ca on y arrive
--
FéliX
fee-eric
Et Si Je Laisse un Tag dans le 1ER Wagon. Je vais voir celui de droite et Je
le Nettoie. Je traverse le 1ER Wagon et vait nettoyer celui de gauche. Puis
Je Passe Au 2ém Wagon de Droite, Puis au 2ém de Gauche (Comme un mouvement
de pendule) .Et ainsi de suite, au bout d'un moment, quand j'aurais fait le
tour, J'effacerais mon propre tag. Quand je retraverserais le premier Wagon
(le centre de mon exploration) Je verais qu'il n'y es plus. Donc que j'ai
fait le tour.
C'est clair ou je comprend plus rien
(ps:Désolé pour l'aurtaugrafe)
Vigor
"vacelet" <vac...@lifc.univ-fcomte.fr> a écrit dans le message news:
3C8DE1CD...@lifc.univ-fcomte.fr...
>
> oui
>
> > Est-ce que je peux faire ma signature sur un wagon ?
>
> oui, mais rien ne prouve qu'un tagueur ait fait la meme signature.
Sauf qu'il me semble un peu capillotracté d'imaginer que le tagueur ait la
même signature!
Virginie!
vacelet
> Et Si Je Laisse un Tag dans le 1ER Wagon. Je vais voir celui de droite et Je
> le Nettoie. Je traverse le 1ER Wagon et vait nettoyer celui de gauche. Puis
> Je Passe Au 2ém Wagon de Droite, Puis au 2ém de Gauche (Comme un mouvement
> de pendule) .Et ainsi de suite, au bout d'un moment, quand j'aurais fait le
> tour, J'effacerais mon propre tag. Quand je retraverserais le premier Wagon
> (le centre de mon exploration) Je verais qu'il n'y es plus. Donc que j'ai
> fait le tour.
> C'est clair ou je comprend plus rien
>
C'est bon ...
Nicolas (en manque d'imagination)
Bien entendu, il y a plusieurs solution...
Philippe Poulard
une solution pragmatique :
je traverse les wagons un par un en écrivant un MD5 du numéro du wagon
s'il y a plus de 2^1024 wagons, le parcours est humainement
irréalisable, et le problème n'a pas de réponse
le nombre de wagon est donc à une échelle raisonnable pour qu'un humain
puisse faire le tour et retomber sur le premier wagon
dès qu'on tombe sur le MD5(1), on s'arrete et on connait donc le nombre
de wagons
cette méthode permet de connaître le nombre de wagons en ne faisant
qu'une seule fois le parcours
pour les puristes qui prétendraient qu'un taggeur puisse avoir la même
idée de tagger successivement des wagons par MD5(n), on peut faire une
variante en calculant MD5(n XOR timestamp)
et voilà
--
///
(. .)
-----ooO--(_)--Ooo-----
| Philippe Poulard |
-----------------------
Philippe Poulard
je fais ma signature sans utiliser ma craie, mais en faisant pipi...
...et je cours en comptant les wagons jusqu'à retomber sur ma signature
avant qu'elle ne s'évapore
j'ai bon ?
Arnaud
je compte les wagons...
oui je sais mais bon moi je sais pas lire alors une craie ne me sert à
rien...
"vacelet" <vac...@lifc.univ-fcomte.fr> a écrit dans le message de news:
3C8DD5BC...@lifc.univ-fcomte.fr...