Buona sera, durante le gare ho provato a svolgere questo esercizio senza riuscire a totalizzare più di 40 punti, in poche parole il programma mi da un output sbagliato per N > 10 (Quindi Subtask 3 e 4), il metodo risolutivo che stavo approcciando è una cosa molto banale, e anche per questo penso non riesca a risolvere tutti i subtask:
Fino a quando N è diverso da 0 Se N è uguale a 1, decremento Altrimenti se N è divisibile per una potenza del 3 (3, 9, 27, ..., 4782969), eseguo la divisione, Altrimenti se N-1 è divisibile per una potenza del 3, sottraggo ed eseguo la divisione, Altrimenti se N+1 è divisibile per una potenza del 3, aggiungo ed eseguo la divisione, Altrimenti moltiplico il numero per 2
Questo algoritmo riuscirà sempre a portare N = 0, ma gli output dati sono errati, e non ne capisco il motivo, forse l’ordine in cui dovrebbe eseguire le operazioni è sbagliato? (Se può essere utile sto scrivendo un codice iterativo, non ricorsivo, ma penso si fosse capito).
(Riesco a risolvere solo 1 testcase del Subtask 3 e 1 testcase del Subtask 4 (017 e 020) oltre a Subtask 1 e 2)
Se qualcuno ha un’idea o un suggerimento per il quale il mio metodo risolutivo sia errato/non funzionante in certi casi mi aiuterebbe molto. Grazie
Sei sicuro che il tuo codice non porti mai ad andare oltre il miliardo?
Ad esempio, dando in ingresso 4782971, l’algoritmo che hai descritto moltiplica sempre per due senza mai arrivare a zero (a parte l’overflow, che però possiamo ignorare per analizzare questo algoritmo e dire semplicemente che moltiplica sempre per due).
Forse ho letto male io, ma da quello che ho capito questo algoritmo non arriverà mai a moltiplicare N per 2.
Mi spiego meglio, dato un numero N, tu controlli se N, N+1 o N-1 sono divisibili per una potenza del 3 (quindi primo fra tutti il 3). Il problema è che se N non è divisibile per 3, allora sicuramente uno dei due tra N+1 e N-1 lo sarà.
Spero di esserti stato d’aiuto.
Questo non è vero, ipotizzando di avere un numero N uguale a 13 come nel caso di esempio, e come potenze del 3: {3, 9, 27, 81, …} il programma farà la seguente:
13 == 1 [false]
13 è divisibile per 3 o per 9 [false]
12 è divisibile per 3 o per 9 [false]
14 è divisible per 3 o per 9 [false]
allora moltiplica 13 * 2 = 26, qui sarà soddisfatto nel caso N+1/potenza_di_3 e quindi arriverà correttamente alla soluzione, perché il problema dice che la divisione per una potenza di 3 può essere fatta solo se diviso N in modo esatto
divide by a power of 3 (which divides exactly the stored number).
Rispondendo a @dp_1 no, in effetti il mio codice non controlla se supero il limite di 10^9, ma se non può moltiplicare per 2, e non può dividere neanche per una potenza di 3, dovrei per forza farlo incrementare o decrementare secondo un qualche criterio a me ignoto, giusto?
Comunque grazie mille per l’aiuto, domani provo a modificare il codice per introdurre il limite di 10^9 e vi farò sapere
divide by a power of 3 (which divides exactly the stored number).
otteniamo: divide per una potenza del 3 (che divide esattamente il numero conservato). quindi 12 non viene considerato, gli unici numeri per cui può essere diviso N sono:
perché poi supera il limite posto dall’assunzione: N <= 10’000’000.
Quindi il problema non penso si ponga qui, ma nel fatto che il numero N possa andare overflow causa un numero di moltiplicazioni per due tale che N superi il limite di 10^9. In ogni caso appena ho tempo do un’occhiata, avevo pensato di controllare che se la moltiplicazione superi 10^9 decrementi o incrementi X volte fino ad arrivare alla potenza più vicina (Che alla fine sarà quasi sicuramente 4782696, quindi basterebbe eseguire una sottrazione).
Rieccomi qui, ho provato un bel po di soluzioni cambiando qualche parte di codice, ma non riesco comunque a superare i 40 punti, sto davvero pensando che il mio metodo risolutivo non sia il migliore per questo esercizio anche perché con una soluzione simili alle mie precedenti ho notato che il 1° esempio dove N è uguale a 13, non viene risolto correttamente, invece che 4 step (13->26->27->1->0) ne compie 5 (13->12->4->3->1->0) questo perché controlla prima se sia possibile eseguire la divisione su N-1, quindi sto davvero uscendo pazzo senza trovare una soluzione efficace. Qualcuno che sia riuscito a risolverlo potremme darmi qualche dritta? Perché seriamente, mi sto mettendo le mani nei capelli ahaha
Per risolverlo non c’è bisogno di fare nessun algoritmo molto difficile basta che provi ogni caso finche arrivi a 0.
puoi usare una deque dove inserisci delle struct formate da due int(valore e passaggi per arrivare al valore) ed ogni volta fai:
è divisibile per una potenza di 3(se si lo 0 aggiungi in coda)
aggiungi uno e lo aggiungi in coda
togli uno e aggiungi in coda
moltiplichi per due aggiungi in coda.
e cancelli il valore appena preso in esame.
basta inserire questi passaggi in un while (anche un while 1 va bene) e quando trova il valore 0 all inizio fai l output dei passaggi e poi finire il ciclo.
Anche se puo sembrare molto lungo in realta fa 100 perche questo algoritmo lo devi fare per un solo e valore
Si ottengono risultati migliori se si usa un set ordinato in base alla distanza di ogni ‘nodo’ anzichè una queue o una deque, poichè non ammette ripetizioni
)