Advertisement
ghorardim

uva 562 - Dividing coins

May 20th, 2017
675
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.81 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<math.h>
  4. #include<ctype.h>
  5. #include<stdlib.h>
  6. #include<cstdio>
  7. #include<cstring>
  8. #include<string>
  9. #include<cmath>
  10. #include<iostream>
  11. #include<cctype>
  12. #include<map>
  13. #include<stack>
  14. #include<cstdlib>
  15. #include<queue>
  16. #include<vector>
  17. #include<algorithm>
  18. #include<bitset>
  19. #include<algorithm>
  20. #include<set>
  21. #include<limits.h>
  22. #include <sstream>
  23.  
  24.  
  25. using namespace std;
  26. typedef long int LD;
  27. typedef long long int LLD;
  28. typedef float F;
  29. typedef double LF;
  30. typedef unsigned int U;
  31. typedef unsigned long int LU;
  32. typedef unsigned long long int LLU;
  33. typedef char C;
  34.  
  35.  
  36. /*----------simple input section ------------ */
  37. #define sf scanf
  38. #define sfi(x) scanf("%d",&x)
  39. #define sfc(x) scanf("%c",&x)
  40. #define sfi2(x,y) scanf("%d%d",&x,&y)
  41. #define sfll2(x,y) scanf("%lld%lld",&x,&y)
  42. #define sfu2(x,y) scanf("%llu%llu",&x,&y)
  43. #define sfl(x) scanf("%ld",&x)
  44. #define sfll(x) scanf("%lld",&x)
  45. #define sfd(x) scanf("%lf",&x)
  46. #define sfu(x) scanf("%llu",&x)
  47. #define sfs(x) scanf("%s",x)
  48.  
  49.  
  50. /*----------simple input section ------------ */
  51. #define pf printf
  52. #define pfi(x) printf("%d\n",x)
  53. #define pfl(x) printf("%ld\n",x)
  54. #define pfll(x) printf("%lld\n",x)
  55. #define pfu(x) printf("%llu\n",x)
  56. #define pfs(x) printf("%s\n",x)
  57. #define pfc(x) printf("%c\n",x)
  58. #define pfd(x) printf("%lf\n",x)
  59.  
  60. /*----------file input section ------------ */
  61.  
  62. #define f_input  freopen("input.txt","r",stdin);
  63. #define f_output freopen("output.txt","w",stdout);
  64.  
  65. #define pb(x) push_back(x)
  66. #define PI acos(-1.0)
  67. #define sq(x) (x)*(x)
  68. #define mem(x,y) memset(x,y,sizeof(x))
  69. #define TEST int cs,T;sfi(T);getchar();for(cs=1;cs<=T;cs++)
  70. #define nn printf("\n")
  71. // xx-> diagonal -> 8 horizontal/vertical->4
  72.  
  73. const int xx[] = {0, 1, 0, -1, -1, 1, -1, 1};
  74. const int yy[] = {1, 0, -1, 0, 1, 1, -1, -1};
  75.  
  76. // KX-> Knight moves
  77. const int kx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
  78. const int ky[] = {1, 2, 2, 1, -1, -2, -2, -1};
  79.  
  80.  
  81. /******** debug **********/
  82. #define chk1 printf("hi......1  \n")
  83. #define chk2 printf("hi......2  \n")
  84.  
  85.  
  86.  
  87.  
  88. #define mod 1000000007
  89. #define eps 10e-8
  90. #define sz 100004
  91. #define sz1 102
  92. #define sz2 5
  93. /******* start my code ********/
  94. int arr[sz1];
  95. int knap(int i,int n,int sum,int limit)
  96. {
  97.     if(i==n)
  98.     {
  99.         return sum;
  100.     }
  101.     int q1,q2;
  102.     q1=q2=0;
  103.     if(sum+arr[i]<=limit)
  104.     q1=knap(i+1,n,sum+arr[i],limit);
  105.     if(sum<=limit)
  106.     q2=knap(i+1,n,sum,limit);
  107.     return max(q1,q2);
  108. }
  109. int main()
  110. {
  111.     int i,j,k,n,m,sum;
  112.     TEST                  /// taking input number of test case and run it.......
  113.     {
  114.         sfi(n);
  115.         sum=0;
  116.         for(i=0; i<n; i++)
  117.         {
  118.             sfi(arr[i]);
  119.             sum+=arr[i];
  120.         }
  121.         int ans = knap(0,n,0,(sum+1)/2);
  122.         pfi(abs((sum-ans)-ans));
  123.     }
  124.     return 0;
  125. }
  126. /*
  127.  
  128.  
  129. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement