🍕 test round solution by GDG Bologna
the following text is in Italian because is targeted to an italian community, if you're an english reader and needs a translation please create an issue
Abbiamo da dividere una pizza rettangolare in diversi pezzi. La pizza è divisa in celle, ogni cella può contenere un pomodorino un fungo. Bisogno massimizzare il numero di pezzi tenendo conto di vincoli sul numero di pomodorini e funghi minimi per ogni pezzo ma anche su una dimensione massima del pezzo.
Il file di input del problema ha la seguente sintassi:
3 5 1 6
TTTTT
TMMMT
TTTTT
Cioè una pizza di 3 righe x 5 colonne. Bisogna che in ogni pezzo di sia almeno 1 pomodorino e un fungo. E l'area massima del pezzo è di 6 celle.
Il file di output deve avere la seguente sintassi:
3
0 0 2 1
0 2 2 2
0 3 2 4
Che in pratica dice:
- sono riuscito a creare 3 pezzi il primo pezzo è un rettangolo dalla cella (0,0) alla cella (2,1) oppure in altre parole è un rettangolo che comprende le righe dalla 0 alla 2 (3 righe) e le colonne dalla 0 alla 1 (2 colonne) le altre righe sono gli altri pezzi
Visualizzata la soluzione è la seguente:
Il problema può essere visto anche come la minimizzazione del numero di celle che non vanno a finire in pezzi tagliati e scritti nel file di output.
Per provare la soluzione è necessario utilizzare python 3+ ed eseguire il seguente comando
python3 pizza.py filename
che eseguirà lo script pizza.py prendendo come input in/filename.in e generando l'output in out/filename.out