è permesso parlarne? credo di sì visto che i problemi adesso sono praticamente pubblici ma non si sa mai
Problema 1: lwf
Dato un numero in input (N < 10^6 mi pare), il problema consisteva nel tradurlo in una serie di bit, dove ogni bit indica un numero di fibonacci, se il bit è a uno il numero va considerato, altrimenti no.
La somma dei numeri considerati deve essere equivalente al numero in input, quindi per esempio, se in input si ha 19 la sequenza di bit:
0 1 0 0 1 0 1
1 1 2 3 5 8 13
indica che bisogna sommare 13 + 5 + 1 = 19.
Questo era molto semplice, la mia soluzione costruiva la serie di fibonacci fino al numero direttamente più piccolo di quello un input, poi iteravo la serie costruita al contrario, sottraendo i numeri a quello in input qualora fossero minori e mettendo il relativo bit a 1, altrimenti a 0, finchè il risultato della sottrazione non diventava 0.
Problema 2: scommessa (scommesse?)
In input si aveva una sequenza di N numeri (N era sempre un numero dispari < 100 se non sbaglio). I numeri andavano da a N - 1 in ordine casuale.
Era possibile a ogni iterazione eliminare una coppia qualsiasi di numeri consecutivi qualora la loro somma fosse un numero dispari, continuando così finchè non era più possibile eliminarne.
In output bisognava scrivere quanti erano e quali erano i numeri che potevano rimanere sul tavolo dopo una certa sequenza di mosse.
Casi di esempio:
3
1 2 0
Output:
1
0
11
1 0 2 6 4 5 3 9 8 10 7
Output:
2
2 8
Al momento non mi viene in mente altra soluzione che una brute force ricorsiva, ma dovrebbe essere comunque sufficiente per le territoriali, forse si può anche risolvere in DP.
Problema 3: tecla
In input veniva dato un grafo con N nodi ed M archi (1 <= N,M <= 30) non pesati.
La storiella diceva che al nodo 0 c’erano un ragno ed un’ ape, ma il ragno era in stato di “BLEAH (diciamo rappresentato con 0)” e quindi non aveva voglia di mangiare l’ape.
Spostarsi su un arco cambiava il ragno da uno stato di “BLEAH” a “SLURP” (rappresentato con 1) ed il problema consisteva nel trovare un percorso che partiva dal nodo 0 e ci riportava lì in stato di “SLURP” (quindi un ciclo di lunghezza dispari) e poi scrivere in output il numero di spostamenti e gli archi attraversati, uno per riga.
Casi di esempio:
Il primo era un triangolo, l’altro era un po’ più complesso e non ho voglia di scriverlo .
Con solo 30 archi e nodi una brute force poteva bastare anche qui, anche se avevo pensato a una soluzione basata sulla dfs implementata con stack.
Spero di essermi ricordato tutto.