[Python] Google Code Jam - Round 1B (2013)

"Null reference exception"? no, grazie, prendo un "unexpected T_VARIABLE"... Questo è il forum per imparare l'arte della programmazione o per chiedere un parere su una sessione di debug particolarmente ostica.
Regole del forum
Ricorda di indicare chiaramente nell'oggetto il linguaggio ([C#] oppure [PHP], [Java], [HTML], ...), se la discussione ne riguarda uno in particolare!
Rispondi
Avatar utente
Berga
Livello: DVD-ROM (5/15)
Livello: DVD-ROM (5/15)
Messaggi: 100
Iscritto il: sab mag 04, 2013 1:09 pm

[Python] Google Code Jam - Round 1B (2013)

Messaggio da Berga »

Buonasera a tutti! :mrgreen: È 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()
Purtroppo non è corretto... dove sbaglio?

EDIT: è Python 3.x ;)
~

Rispondi
  • Argomenti simili
    Risposte
    Visite
    Ultimo messaggio