Stile IMO problema combinatorio basato su algoritmo [duplicato]
Il problema è descritto nella figura, la soluzione dovrebbe essere una prova costruttiva, quindi è necessario trovare un algoritmo che funzioni indipendentemente da cose come il tempo di esecuzione. Qualsiasi aiuto sarebbe grato che non riesca a risolverlo e ci sto provando da un po '
EDIT: La mia direzione principale era cambiare il segno su ogni raw con somma negativa, ora ogni raw è completo e la somma di tutte le voci non è negativa (poiché la somma di tutti i raw è ora non negativa)
Risposte
Se una riga o una colonna ha una somma negativa, scegline una e inverti i segni.
Ripeti il processo.
Dopo ogni transizione, la somma di tutte le voci nella matrice viene aumentata.
Ma il valore assoluto delle voci rimane invariato, quindi ci sono solo molte possibilità per la somma totale.
Ne consegue che il processo alla fine terminerà.
Usa semplicemente il seguente semplice algoritmo: In ogni turno, inverti i segni di una riga o colonna casuale con somma negativa e dimostreremo che questa procedura termina con mosse finite: Nota che usando questo algoritmo la somma dei numeri in tutti i board aumenterà sempre e poiché questa somma è delimitata dall'alto e ci sono anche possibilità finite per questa somma, il nostro algoritmo si fermerà da qualche parte e c'è il punto che la somma di tutte le righe e le colonne non è negativa.