[Python] Google Code Jam - Round 1B (2013)
Inviato: dom mag 05, 2013 8:57 pm
È un piacere per me inaugurare questa nuova categoria! Ma ora comincio ad esporvi il mio problema.
Nel caso non lo sapeste, ieri si è svolto il round 1B di Google Code Jam, una competizione targata Google, in cui i partecipanti devono risolvere nel loro tempo limite alcuni problemi di natura algoritmica.
Io ho provato ad affrontare questo problema (leggetelo attentamente), scrivendo il seguente codice:
Codice: Seleziona tutto
f = open("input.in", "r")
fout = open("output.out", "w")
tot = f.readlines()
T = int(tot[0]) # numero totale di casi
ind = 1
for x in range(len(tot)):
tot[x] = tot[x][:-1] # rimuovo il maledetto "\n" alla fine di ogni riga
I=0 # mi serve per segnare il "Case #.."
for line in range(T):
I+=1
count = 0
A, N = tot[ind].split(" ")
A = int(A) # A -> dimensione Armin iniziale
N = int(N) # N -> numero delle altre particelle
ind+=1
Ntot = (tot[ind].split(" ")) # contiene tutte le dimensioni delle altre
# particelle
for x in range(len(Ntot)):
Ntot[x] = int(Ntot[x])
ind+=1
Ntot.sort()
print("Ntot: " + str(Ntot) + " A: " + str(A))
while(len(Ntot)>0):
if (A<=int(Ntot[0]) and (2*A-1)>int(Ntot[0])):
# se A e' piu' piccolo della particella piu' piccola della lista,
# e se aggiungendo un altra particella di grandezza A-1 risolverei
# la cosa, fallo
print(str(Ntot[0]) + " è troppo grande per " + str(A)+ ".")
count+=1
A+=A-1
elif ((2*A-1)<=int(Ntot[0])):
# se invece A rimarrebbe piu' piccolo comunque, anche con l'aggiunta
# di una particella A-1 ...
Atemp = A
for x in range(len(Ntot)):
Atemp += Atemp-1 # calcola quanto si ingrandirebbe aggiungendo
# len(Ntot) volte ad A->A-1
if(Atemp > Ntot[0]): # se diventerebbe piu' grande, A+=A-1
count+=1
print(str(A) + " raddoppia per " + str(Ntot[0]) + ".")
A+=A-1
else: # altrimenti rimuovo l'elemento
print(str(Ntot[0]) + " è stato rimosso.")
Ntot.remove(Ntot[0])
count+=1
else:
# se A e' piu' grande, mangia senza problemi
print(str(Ntot[0]) + " è stato mangiato da " + str(A) + ".")
A+=int(Ntot[0])
Ntot.remove(Ntot[0])
print("=== Risolto con: " + str(count) + " modifiche. ===")
fout.write("Case #" + str(I) + ": " + str(count) + "\n")
f.close()
fout.close()EDIT: è Python 3.x
