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 + 4 + 4 + 4 + 4 + 4$ , $40 = 4 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5$ $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 \leq N \leq 10$	None
$2$ $2$ marks	$1 \le N \le 100\,000$ $1 \leq N \leq 100 000$	$N$ $N$ is a multiple of $4$ $4$
$2$ $2$ marks	$1 \le N \le 100\,000$ $1 \leq N \leq 100 000$	$N$ $N$ is a multiple of $5$ $5$
$8$ $8$ marks	$1 \le N \le 1\,000\,000$ $1 \leq N \leq 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

Copy

Output for Sample Input 1

Copy

Explanation of Output for Sample Input 1

This is one of the examples in the problem description.

Sample Input 2

Copy

Output for Sample Input 2

Copy

Explanation of Output for Sample Input 2

This is one of the examples in the problem description.

Sample Input 3

Copy

Output for Sample Input 3

Copy

Explanation of Output for Sample Input 3

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

Comments

-3

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

4

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

why 1gb memory limit?

4

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

CCC gives you a large memory limit for most problems.