Allora per esercitarmi per il 16 stavo rifacendo le vecchie prove, ma ci sono due quesiti che non mi vengono e non trovo la soluzione commentata da nessuna parte quindi chiedo qui (il topic è unico perchè l’algoritmo risolutivo penso sia lo stesso).
Selezioni scolastiche OII 2014/15, es. 15:
Quattro gondole A,B,C,D sono ormeggiate sulla riva sinistra di un canale. Un gondoliere deve portare le quattro gondole sulla riva destra.
Essendo di differente grandezza, le gondole impiegano tempi diversi per attraversare il canale: la gondola A impiega 2 minuti, la gondola B 4 minuti, la gondola C 8 minuti e la gondola D 16 minuti.
Il condoliere può condurre una sola gondola alla volta, ma può agganciare alla gondola su cui si trova una seconda gondola e trainarla, impiegando in questo caso il tempo di quella più lenta.
Qual è il tempo minimo necessario al gondoliere per trasferire le 4 gondole da una riva all’altra?
[30 minuti]
Selezioni scolastiche OII 2015/16, es 18:
C’era una volta un boschetto vicino al castello della regina cattiva, dove vivevano otto simpatici nani: Dotto, Brontolo, Gongolo, Pisolo, Mammolo, Eolo, Cucciolo e Occhiolo. Ebbene sì, erano otto un tempo e l’ultimo era il più bello (per gli standard dei nani, s’intende). Occhiolo infatti aveva due immensi occhioni azzurri, con i quali incantava tutte le ninfe del bosco.
Occhiolo però amava fare il funambolo e questo, come tutti sanno, è un hobby pericoloso. Una volta decise di percorrere con Mammolo, Gongolo ed Eolo un lungo ramo di edera, che collegava la loro casetta con una grotta incantata. Per percorrere l’intero tragitto Mammolo ci mise 2 minuti, Eolo 5, Gongolo 10 e Occhiolo (naturalmente) uno solo.
Arrivati alla grotta incantata, però, trovarono la regina cattiva che li aspettava per un’imboscata. La megera decise di rendere il percorso di ritorno più difficile, stregando il ramo con il seguente maleficio: i nani avrebbero potuto riperclrrere il ramo solo portando con sé la mela avvelenata (data loro dalla regina per Biancaneve): il ramo non avrebbe retto più di due rami per volta, e si sarebbe rotto immediatamente se i nani avessero tentato di percorrerlo senza mela.
È chiaro che quando due nani attraversano il ramo insieme con la mela, gli stessi procedono alla velocità del più lento dei due. L’attraversamento del ramo diventa quindi complicato: due nani possono passare con la mela, ma poi uno dei nani che ha già passato il ramo dovrà tornare indietro con la mela, per consentire il passaggio di un’altra coppia.
Qual è, in minuti, il minimo tempo necessario perchè i 4 nani possano percorrere il ramo e tornare a casa?
[17]