×

Loading...

有喜欢做题的吗?Given a set, S , of n distinct integers, print the size of a maximal subset, S', of S where the sum of any numbers in S' are not evenly divisible by k.

sxffff (lookingforjob)
本文发表在 rolia.net/zh 相约加拿大网上社区枫下论坛
Given a set, S , of n distinct integers, print the size of a maximal subset, S', of S where the sum of any numbers in S' are not evenly divisible by k.

Input Format

The first line contains 2 space-separated integers, n and k, respectively.
The second line contains n space-separated integers (we'll refer to the i th value as a_i ) describing the unique values of the set.


All of the given numbers are distinct.
Output Format

Print the size of the largest possible subset (S').

Sample Input

4 3
1 7 2 4
Sample Output

3
Explanation

The largest possible subset of integers is S'={1,7,4}, because no two integers will have a sum that is evenly divisible by k=3:

1+7=8, and 8 is not evenly divisible by 3.
1+4=5, and 5 is not evenly divisible by 3.
7+4=11, and 11 is not evenly divisible by 3.
The number 2 cannot be included in our subset because it will produce an integer that is evenly divisible by when summed with any of the other integers in our set:

1+2=3, and 3/3=1.
4+2=6, and 6/3=2.
7+2=9, and 9/3=3.
Thus, we print the length of S' on a new line, which is 3.
更多精彩文章及讨论,请光临枫下论坛. 网址: rolia.net/zh
(#10308318@0)
2016-9-17 -05:00
Reply
Page address has been copied.
To share, click to copy page address.
Share Online by QR Code

Back To Topic: 有喜欢做题的吗?Given a set, S , of n distinct integers, print the size of a maximal subset, S', of S where the sum of any numbers in S' are not evenly divisible by k.

Back To Forum: HOME枫下论坛枫下论坛主坛工作学习学科技术