#P6586. Great Set Completion
Great Set Completion
Great Set Completion
Given a set S of n distinct integers and an initial subset G of S consisting of m integers, the set G is required to satisfy the following closure condition with respect to a fixed integer (a):
- If \(x \in G\), then if \(x+a\) belongs to S, it must also be in G.
- If \(x+a\) is not in S, then no action is needed.
- A set \(G\) is considered complete (or "perfect") if no additional element needs to be added according to the rule above.
Your task is to determine whether the given set G is already complete. If it is, print Great Set!
. Otherwise, determine the minimum number of elements that need to be added to G (following the rule) to make it complete, and output that number.
inputFormat
The input consists of three lines:
-
The first line contains three integers (n), (m) and (a) ((1 \le m \le n)) where (n) is the number of distinct integers in S, (m) is the number of integers initially in G, and (a) is the fixed increment.
-
The second line contains (n) space-separated integers representing the set S.
-
The third line contains (m) space-separated integers representing the initial subset G. All numbers in G are guaranteed to be in S.
outputFormat
If the given set G is already complete (i.e. no additional numbers need to be added to satisfy the closure rule), output:
Great Set!
Otherwise, output a single integer representing the minimum number of additional elements that must be added to G to make it complete.
sample
5 2 2
1 3 5 7 9
1 5
3