Editorial for CCC '22 S1 - Good Fours and Good Fives


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.

The first problem is designed to be accessible with some insight required to obtain full marks.

The first subtask can be hard-coded. That is, the following table can be calculated by hand and a solution can mimic looking up the correct output in the table.

N12345678910
Output0001100111

For the second and third subtasks, we can notice that we need N = 4a + 5b for non-negative integers a and b where a \le \frac{n}{4} and b \le \frac{n}{5}. This means we can try all possible values for a and b using two nested loops.

For a full solution, we can loop through only all possible values of a to determine if there is a corresponding value of b. For each of these values i, this is equivalent to checking if N - 4i is divisible by 5. Alternatively, we take a similar approach but loop through only all possible values of b.

There is also a clever extremely quick solution that involves extending the table listed above for the first subtask to N = 20 and considering the quotient and remainder when N is divided by 20.


Comments

There are no comments at the moment.