Editorial for CCC '22 S1 - Good Fours and Good Fives - Olympiads Online Judge

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.

$N$ ~N~	$1$ ~1~	$2$ ~2~	$3$ ~3~	$4$ ~4~	$5$ ~5~	$6$ ~6~	$7$ ~7~	$8$ ~8~	$9$ ~9~	$10$ ~10~
Output	$0$ ~0~	$0$ ~0~	$0$ ~0~	$1$ ~1~	$1$ ~1~	$0$ ~0~	$0$ ~0~	$1$ ~1~	$1$ ~1~	$1$ ~1~

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

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

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

Comments

There are no comments at the moment.