Esercizio 2 homework1 non passa ultimi test con 1 sec

Question

Buongiorno, ragazzi. Sto eseguendo i test dell'esercizio 2 hw1. Lanciando il commando pytest test_02.py -v --timeout 3 --durations 0 passo correttamente tutti i test e vedo 2 test che vanno oltre 1 secondo che non mi permettono di superare il test lanciando il comando pytest test_02.py -v --timeout 1 --durations 0. Questi due test sono N = 10000 e lampadine tutte spente o accese a meta. Algoritmo che sto usando e' il seguente : inizio con ultimo pulsante p[N-1] e ne calcolo i divisori, con algoritmo che va da 1 a radice di N. Dopo unisco insieme delle lampadine gia accese con divisori di p[N-1], se l'insieme ottenuto e uguale all'insieme {1,...,N} allora risultato trovato, altrimenti rifaccio lo stesso lavoro per p[N-1] e cosi via finche non trovo risultato. Dopo aver perso alcune giornate non riesco proprio a vedere altro modo per sviluppare algoritmo che vada sotto 1 secondo in esecuzione. Chiedo aiuto se qualcuno mi puo dare consiglio. Grazie P.S. Per eliminare elementi comuni utilizzo set(a)^set(b)

Answer 1

Io calcolerei i divisori solo se la lampadina relativa al pulsante è spenta li inserirei o li rimuoverei da insieme lampadine accese...

Comments

M infatti faccio cosi. Salto quelle gia accese

Answer 2

i divisori fino a sqrt di n non basta perche così non hai tutti i divisori ,segui questa logica : parti dall'ultima lampadina e accendi quelle spente aggiungi il suo numero ai bottoni da premere e poi cambi lo stato dei divisori fino a quando non finiscono le lampadine .

Comments

Potresti spiegare ancora? Non riesco a capire la logica. Inizio con ultimo pulsante, se lampadina relativa e' spenta allora premo questo pulsante e tutti i suoi divisori. E cosi via finche tuttle le lampadine risultino accese. Questo volevi dire

---

In realtà x ogni divisore più piccolo di rad quad ne esiste uno più grande ottenuto da n/div

---

Penso che quello che intende sia proprio questo: ogni volta che trovi una lampadina spenta, la accendi ma devi cambiare lo stato anche dei suoi divisori, per cui accendi la lampadina corrente e inserisci il bottone nella lista risultato, ma devi anche accendere le lampadine divisori di quella corrente, se sono spente, e spegnerle se sono accese.