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

2016-9-17 -05:00

Page address has been copied.

To share, click to copy page address.
Share Online by QR Code