Comment écrire hors ligne en temps réel 14 (28 septembre) http://atnd.org/events/43076 Problème de référence "Traversée sur la circonférence" http://nabetani.sakura.ne.jp/hena/ord14crosscircle/ Exemple de mise en œuvre.
Avec python inconnu.
Exemples de réponses dans d'autres langues http://qiita.com/Nabetani/items/66806c9dc14a96f2fd42 Vous pouvez suivre de.
alors.
#coding:utf-8
#tested with Python 2.7.5 and Python 3.3.2
import re
def solve( src ):
return str(len(
[ 0
for a in range( 0, len(src) )
for b in range( 0, a )
for c in range( 0, b ) if src[a]==src[c]
for d in range( 0, c ) if src[b]==src[d] ] ))
def test( samples ) :
for line in samples.splitlines():
a=re.split( "\s+", line ) # num, input, expected
if len(a) <3:
continue
actual = solve( a[1] )
ok=actual==a[2]
print( [ "ok" if ok else "***NG***", a[1:3], actual ] )
test( """
0 aabbca1bcb 14
1 111ZZZ 0
2 v 0
""")
Comme d'habitude, la plupart des données de test sont omises.
Une mise en œuvre terriblement naïve. Le pire est O (N ** 4), mais cela suffit pour ce problème.
Choisissez 4 points. Si le premier et le troisième ont le même nom et le deuxième et le dernier ont le même nom, il y a une intersection. Essayez-les tous et vous avez terminé.
Je ne pense pas que ce devrait être le cas d'utiliser la notation d'inclusion de liste, mais je veux l'utiliser, donc je l'utilise sans hésitation. J'ai décidé de l'utiliser, mais je n'étais pas intéressé par le contenu de la liste, alors j'ai décidé de le remplir avec 0, ce qui m'a fait me sentir un peu étrange (j'en ai envie, mais ce n'est pas Pythonista, alors je me demande si c'est vraiment étrange. Je ne suis pas sûr).
Si vous modifiez l'ordre, le cas typique sera plus rapide, mais le pire des cas ne sera pas plus rapide, alors je l'ai laissé tel quel.
Recommended Posts