×

Loading...
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。

有喜欢做题的吗?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.

本文发表在 rolia.net 枫下论坛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
Report

Replies, comments and Discussions:

  • 工作学习 / 学科技术 / 有喜欢做题的吗?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.
    本文发表在 rolia.net 枫下论坛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
    • 自己顶一下