Salve a tutti ragazzi, cercando su internet mi sono imbattuto in questo problema delle olimpiadi di informatica(allego link) ma che purtroppo, nonostante ci abbia sbattuto la testa a lungo,proprio non riesco a risolvere. Il problema infatti non è la scrittura del codice in se, ma pensare ad un algoritmo che faccia quanto richiesto. In particolare ho pensato due considerazioni(che magari possono tornare utili):
1) L'unico stato che ci consente di spegnere tutte le luci, è quello in cui tutte le luci sono accese, consentendoci così di cambiare ricerca, da un modo in cui spegnere tutte le luci ad un modo in cui accenderle tutte, ma forse non è il massimo visto che sarebbe lo stesso risultato speculare.
2) Possiamo ridurre il problema al suo sottoproblema di base, e cioè quando solo una luce è accesa, cercando quindi un algoritmo per spegnere quell'unica luce(e poi magari, per induzione, dimostrare l'algoritmo sui vari casi).
3) utilizzando un approccio Greedy invece, possiamo massimizzare il numero di luci accese, semplicemente accendendo le colonne/righe che hanno un numero di luci spente >= alla metà+1.

Purtroppo come già detto non sono riuscito ad arrivare alla soluzione, e ricordo che non c'è bisogno che perdiate tempo prezioso a scrivere il codice, sarei più che altro interessato semplicemente ad arrivare ad un intuizione della soluzione.Detto ciò,ancora una volta, grazie a tutti.

http://www.valcon.it/c/luci-al-pirellone/