So the 2020 South African Programming Olympiad was yesterday, and someone thought it would be a good idea to put an output-only problem in the exam.

I thought the problem was quite interesting, although I could only get 52 points during the contest. The problem statement can be found here and the input files can be found at https://saco-evaluator.org.za/cms/sapo2020z

I think it's similar to Nowruz from IOI 2017, although BFS only achieves ~5 points instead of ~80... I heard that there's a relatively simple greedy algorithm that scores 60 points though (but no contestants found it during the contest).

Do any of you have any ideas about how to solve this problem? I'd love to hear them in the comments below.