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

CCC '22 S1 - Good Fours and Good Fives

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 1G

Problem types

Canadian Computing Competition: 2022 Stage 1, Senior #1

Finn loves Fours and Fives. In fact, he loves them so much that he wants to know the number of ways a number can be formed by using a sum of fours and fives, where the order of the fours and fives does not matter. If Finn wants to form the number $14$ ~14~, there is one way to do this which is $14 = 4 + 5 + 5$ ~14 = 4 + 5 + 5~. As another example, if Finn wants to form the number $20$ ~20~, this can be done two ways, which are $20 = 4 + 4 + 4 + 4 + 4$ ~20 = 4 + 4 + 4 + 4 + 4~ and $20 = 5 + 5 + 5 + 5$ ~20 = 5 + 5 + 5 + 5~. As a final example, Finn can form the number $40$ ~40~ in three ways: $40 = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4$ , $40 = 4 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5$ , and $40 = 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5$ ~40 = 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5~.

Your task is to help Finn determine the number of ways that a number can be written as a sum of fours and fives.

Input Specification

The input consists of one line containing a number $N$ ~N~.

The following table shows how the available $15$ ~15~ marks are distributed.

Marks Awarded	Bounds on $N$ ~N~	Additional Constraints
$3$ ~3~ marks	$1 \le N \le 10$ ~1 \le N \le 10~	None
$2$ ~2~ marks	$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~	$N$ ~N~ is a multiple of $4$ ~4~
$2$ ~2~ marks	$1 \le N \le 100\,000$ ~1 \le N \le 100\,000~	$N$ ~N~ is a multiple of $5$ ~5~
$8$ ~8~ marks	$1 \le N \le 1\,000\,000$ ~1 \le N \le 1\,000\,000~	None

Output Specification

Output the number of unordered sums of fours and fives which form the number $N$ ~N~. Output $0$ ~0~ if there are no such sums of fours and fives.

Sample Input 1

Output for Sample Input 1

Explanation of Output for Sample Input 1

This is one of the examples in the problem description.

Sample Input 2

Output for Sample Input 2

Explanation of Output for Sample Input 2

This is one of the examples in the problem description.

Sample Input 3

Output for Sample Input 3

Explanation of Output for Sample Input 3

There is no way to use a sum of fours and fives to get $6$ ~6~.

Comments

15

rocket commented on Nov. 5, 2025, 8:36 p.m.

probably would have been Good Sixes and Good Sevens if it was made in 2026.

4

do_ur_homwork commented on Nov. 6, 2025, 11:42 p.m.

Six Seven

-5

Rouri commented on Feb. 20, 2024, 11:41 p.m.

use the combination of 4 and 5 to do this https://dmoj.ca/src/6228667

This comment is hidden due to too much negative feedback. Show it anyway.

7

savirsingh commented on July 30, 2022, 4:30 p.m.

why 1gb memory limit?

8

Kirito commented on July 30, 2022, 4:55 p.m.

CCC gives you a large memory limit for most problems.