알고리즘 기반 조합 문제 IMO 스타일 [중복]

Question

문제는 그림에 설명되어 있으며 솔루션은 건설적인 증거라고 가정하므로 실행 시간과 같은 항목에 관계없이 작동하는 알고리즘을 찾아야합니다. 어떤 도움이 될 것입니다. 나는 이것을 해결할 수 없으며 잠시 노력했습니다.

편집 : 내 주된 방향은 음수 합계로 모든 원시의 기호를 변경하는 것이 었습니다. 이제 모든 원시가 완료되고 모든 항목의 합계가 음이 아닙니다 (모든 원시의 합계가 이제 음이 아니기 때문에)

Answer 1

행이나 열에 음수 합계가 있으면 하나를 선택하고 부호를 반대로하십시오.

프로세스를 반복하십시오.

각 전환 후 매트릭스에있는 모든 항목의 합계가 증가합니다.

그러나 항목의 절대 값은 변경되지 않으므로 총 합계에 대한 가능성은 제한적으로 많습니다.

프로세스가 결국 종료됩니다.

Answer 2

다음과 같은 간단한 알고리즘을 사용하십시오. 매 턴마다 음의 합이있는 임의의 행 또는 열의 부호를 뒤집어이 절차가 유한 이동으로 끝남을 증명할 것입니다.이 알고리즘을 사용하여 모든 숫자의 합을 보드는 항상 증가하고이 합계는 위에서 제한되고 또한이 합계에 대한 유한 한 가능성이 있기 때문에 알고리즘은 어딘가에서 멈추고 모든 행과 열의 합계가 음이 아닌 지점이 있습니다.