CodeChef/SPOJ: un doute m'habite (problème "ORDERS")
Comme je le disais hier, afin de me libérer un peu la tête des considérations mathématiques un peu trop empreintes de considérations sur les grands ensembles, je me distrais plutôt du côté des problèmes de SPOJ/CodeChef, qui ont un aspect plus "vraie vie" plutôt amusant. Oui bon, je me suis pas mal distrait du côté d'OpenTTD, mais ceci est une autre histoire, comme disait le fabricant de sacs.
Dans la catégorie des entraînements "difficiles" (comme "à l'heure à laquelle je tape ceci, la seule solution correcte proposée à ce problème-ci vient d'un certain 'Directi Admin', mais on voit beaucoup de propositions rejetées chaque minute"), on trouve le problème "ORDERS", ou "Ordering the Soldiers".
Le problème est sympa, est pourrait se résumer par: sachant quels ont été les déplacements effectués au cours d'un tri, comment retrouver quelle était la situation initiale?
J'ai donc concocté une solution qui me semblait sympathique, en Python parce que ce langage m'est sympathique. Je la teste sur les exemples donnés, je constate qu'elle fonctionne effectivement comme prévu, je la propose en ligne, et là bardaf! NZEC! Comme "non-zero exit code". Comme "pendant l'exécution, une exception a été soulevée".
Et là j'avoue que je reste pantois, parce que j'ai beau lire et relire mon code, je ne vois absolument pas où ça pourrait échouer.
Quelqu'un a une idée?
#! /usr/bin/env python
# 2009/02/27 - spoj0227.py
# Solution au Probleme 227 de SPOJ
# http://www.spoj.pl/problems/ORDERS/
# Jean Karim Bockstael - jkb@jkbockstael.be
def swap(ary,idx1,idx2):
tmp = ary[idx1]
ary[idx1] = ary[idx2]
ary[idx2] = tmp
def mkranks(size):
tmp = []
for i in range(1, size + 1):
tmp = tmp + [i]
return tmp
def permutations(ordered, movements):
size = len(ordered)
for i in range(1, size): # The leftmost one never moves
for j in range(0, int(movements[i])):
swap(ordered, i-j, i-j-1)
return ordered
numberofcases = input()
for i in range(0, numberofcases):
sizeofcase = input()
tmp = raw_input()
movements = ""
for i in range(0, len(tmp)):
if i % 2 != 1:
movements = movements + tmp[i]
ordered = mkranks(sizeofcase)
ordered = permutations(ordered, movements)
output = ""
for i in range(0, sizeofcase - 1):
output = output + str(ordered[i]) + " "
output = output + str(ordered[sizeofcase - 1])
print output