首页 > 代码库 > poj 2356 抽屉问题

poj 2356 抽屉问题

  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <assert.h>
  4. #include <string.h>
  5. #define MAX 10001
  6. //[(物体数-1)÷抽屉数]+1
  7. //给出N 个数,在其中找出m个数,使得m个数的和是N的倍数,输出m以及任意顺序这m个数,只要输出一种情况。
  8. /*
  9. 可以把和求出来,然后对n取余,因为有n个和,对n取余,如果余数中没有出现0,
  10. 根据鸽巢原理,一定有两个数的余数相同,两个和想减就是n的倍数。如果余数出现0,自然就是n的倍数。
  11. 也就是说,n个数中一定存在一些数的和是n的倍数。求余输出即可。
  12. */
  13. int num[MAX],locker[MAX];
  14. int main()
  15. {
  16. int n;
  17. while(~scanf("%d", &n) ) //number : n;
  18. {
  19. for(int i=1; i<=n; i++) //input number
  20. scanf("%d", &num[i] );
  21. int sum=0;
  22. memset(locker, 0, sizeof(locker) ); //set 0 of 抽屉
  23. int begin=0, end=0; //set start and end
  24. for(int i=1; i<=n; i++)
  25. {
  26. sum = (sum+num[i]) % n; //前n个数求余
  27. if(sum == 0) //是0就是从头开始到尾
  28. {
  29. begin=1;
  30. end=i;
  31. break;
  32. }
  33. else if( !locker[sum]) //不是件以余数为下标保存在抽屉中,抽屉内为该元素在在数组中地址
  34. {
  35. locker[sum]=i;
  36. }
  37. else //是,即sum[i]==sum[j],取i+1到j个数,所以begin要加一
  38. {
  39. begin=locker[sum]+1;
  40. end=i;
  41. break;
  42. }
  43. }
  44. printf("%d\n", end-begin+1); //多少个数,注意加一
  45. for(int i=begin; i<=end; i++) //输出
  46. printf("%d\n", num[i] );
  47. }
  48. return 0;
  49. }
  50. /*
  51. Description
  52. The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k).
  53. Input
  54. The first line of the input contains the single number N. Each of next N lines contains one number from the given set.
  55. Output
  56. In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order.
  57. If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them.
  58. Sample Input
  59. 5
  60. 1
  61. 2
  62. 3
  63. 4
  64. 1
  65. Sample Output
  66. 2
  67. 2
  68. 3
  69. */



来自为知笔记(Wiz)


附件列表

     

    poj 2356 抽屉问题