Easy Sum Set Problem

3.6

195 votes
Algorithms, Easy, Searching
Problem

In this problem, we define "set" is a collection of distinct numbers. For two sets A and B, we define their sum set is a set S(A,B)={a+b|aA,bB}. In other word,  set S(A,B) contains all elements which can be represented as sum of an element in A and an element in B. Given two sets A,C, your task is to find set B of positive integers less than or equals 100 with maximum size such that S(A,B)=C. It is guaranteed that there is unique such set.

Input Format

The first line contains N denoting the number of elements in set A, the following line contains N space-separated integers ai denoting the elements of set A.

The third line contains M denoting the number of elements in set C, the following line contains M space-separated integers ci denoting the elements of set C.

Output Format

Print all elements of B in increasing order in a single line, separated by space.

Constraints

  • 1N,M100
  • 1ai,ci100

 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

If e is an element of set B, then e+2 is an element of set C, so we must have e3. Clearly, e cannot be 1 because 1+1=2 is not an element of set C. Therefore, B={2,3}.

Editor Image

?