È San Valentino, e Giacopo deve conquistare la bellissima Alecsandra: quale regalo è più romantico e meno banale di una (o più...) scatole di cioccolatini?
In pasticceria, Giacopo si trova di fronte a una stringa apparentemente infinita di scatole di cioccolatini, e a causa di una speciale offerta "San Valentino" può acquistarne qualunque numero al prezzo di una; il nostro eroe intende piazzare le scatole in alcuni luoghi strategicamente scelti, ma per conoscere più in dettaglio il suo piano è necessario un breve excursus metereotopologico su Bucarest.
Bucarest è composta da $n\ge3$ piazze e da alcune strade che le collegano: nessuna strada collega una piazza a se stessa, né due piazze che sono già collegate da un'altra strada. Ogni 14 febbraio, ormai da tempo immemore, spira su Bucarest una brezza leggera, che allieta la festa degli innamorati. In ciascuna strada, il vento soffia in una direzione ben precisa: o dalla prima piazza alla seconda, o viceversa. Una scatola di cioccolatini collocata in una qualunque piazza fa sentire il suo piacevole profumo in ogni piazza che il vento può raggiungere percorrendo al più $k$ strade (quindi in particolare anche nella piazza stessa).
Giacopo vuole far sì che Alecsandra, in qualunque piazza si trovi, possa godere del profumo dei cioccolatini da lui collocati; tuttavia, un odore troppo forte può risultare sgradevole. Di conseguenza, Giacopo collocherà scatole di cioccolatini in alcune piazze di Bucarest, in modo che:
- ogni piazza sia raggiunta dal profumo di cioccolatini
- se due piazze contengono entrambe cioccolatini, allora non deve esistere una strada che le collega (altrimenti in una delle due l'odore sarà troppo forte per la povera Alecsandra)