Editorial for COCI '11 Contest 6 #2 Prozori

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

After reading in $5M+1$ ~5M+1~ rows and $5N+1$ ~5N+1~ columns of the input, we can notice that only some fields are of importance to us. More specifically:

for the 1st column of windows, it's enough to analyze the 2nd column of the input matrix,
for the 2nd column of windows, it's enough to analyze the 7th column of the input matrix,
for the 3rd column of windows, it's enough to analyze the 12th column of the input matrix…

In general:

for the $K^\text{th}$ ~K^\text{th}~ column of windows, it's enough to analyze the $(5K-3)^\text{rd}$ ~(5K-3)^\text{rd}~ column of the input matrix.

Inside each of the selected columns, the next four fields after each boundary # are of interest to us: the number of asterisks in those four fields will determine the type for that window.

While traversing columns, we must keep track of the number of windows found so far for each type. The best way to do this is to have a small array with five integers, and increase the number at the corresponding index as we come across different types of windows. At the end, we just output the numbers from that array.

Comments

There are no comments at the moment.