fork download
copy 
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <list>
  6. #include <vector>
  7. #include <map>
  8. using namespace std;
  9.  
  10. #define MAX 202
  11. #define MOD 1000000007
  12. #define PB push_back 
  13. const int INF = 1000005;
  14. typedef long long int LL;
  15. typedef vector <int> vi;
  16.  
  17. vi *v;
  18. int a[100];
  19.  
  20. int main()
  21. {
  22. 	int t,i,j,k,n,m;
  23. 	int x,v,cur,best;
  24. 	scanf("%d",&t);
  25. 	while(t--)
  26. 	{
  27. 		scanf("%d",&n);
  28. 		for(i=0;i<n;i++)	scanf("%d",&a[i]);
  29. 		sort(a,a+n);
  30. 		best=INF;
  31. 		for(i=0;i<n;i++)		
  32. 		{
  33. 			bool h[5005];
  34. 			memset(h,0,sizeof(h));
  35. 			cur=0, h[0]=1;
  36. 			for(j=0;j<n;j++)
  37. 			{
  38. 				if(i==j)	continue;
  39. 				cur= cur+a[j];
  40. 				for(k=cur;k>=a[j];k--)
  41. 					if(h[k-a[j]])		h[k]=1;
  42. 			}
  43. 			x=cur/2;	
  44. 			while(!h[x])	x--;
  45. 			m=abs(cur-x-x);
  46. 			if(m < best)	best=m, v=a[i];
  47. 		}
  48. 		printf("%d %d\n",best,v);
  49. 	}
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
3
2
100 5
3
1 2 1
5
5 3 1 2 4
stdout
copy 
5 100
0 2
0 1
https://ideone.com/sF2Eoo
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!