fork(2) download
copy 
  1. #include<stdio.h>
  2. int swap(int *a,int *b)
  3. 	{
  4. 		int temp;
  5. 		temp=*a;
  6. 		*a=*b;
  7. 		*b=temp;
  8. 	}
  9. int partition(int array[], int size)
  10. {
  11. int k;
  12. int mid = size/2;
  13. int index = 0;
  14. swap(array, array+mid);
  15. for (k = 1; k < size; k++){
  16. if (array[k] < array[0]){
  17. index++;
  18. swap(array+k, array+index);
  19. }
  20. }
  21. swap(array, array+index);
  22. return index;
  23. }
  24.  
  25. void sort(int array[], int size)
  26. {
  27. int index;
  28. if (size > 1)
  29. {
  30. index = partition(array, size);
  31. sort(array, index);
  32. sort(array+index+1, size - index-1);
  33. }
  34. }
  35. int search(int a[],int n,int value)
  36. 	{
  37. 		int i,f,l,mid;
  38. 		f=0;
  39. 		l=n-1;
  40. 		while(f<=l)
  41. 			{
  42. 				mid=(f+l)/2;
  43. 				if(value==a[mid])
  44. 				{
  45. 					return mid;
  46. 				}	
  47. 				else if(value>a[mid])
  48. 					f=mid+1;
  49. 				else
  50. 				  	l=mid-1;
  51. 			}
  52. 		return -1;
  53. 	}
  54.  
  55. int find(int a[],int n,int value)
  56. 	{
  57. 		int i,k,finds,j=0,count[21]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},l;
  58. 		int sum=0;
  59. 		for(i=0;i<n;++i)
  60. 			{
  61. 				//printf("%d ",a[i]);
  62. 				if(a[i]!=0)
  63. 					break;
  64. 			}
  65. 		if(a[i]==value)
  66. 			{
  67. 				a[i]=0;
  68. 				return 1;
  69. 			}
  70. 		else if(a[i]>value)
  71. 			return 0;
  72. 		else 
  73. 			{
  74. 				a[i]=a[i]-2;
  75. 				finds=search(a,n,value-a[i]);
  76. 				if(finds!=-1)
  77. 					{
  78. 						a[finds]=0;
  79. 						a[i]=0;
  80. 						return 1;
  81. 					}
  82. 				a[i]=a[i]+2;
  83. 			}
  84. 		for(i=0;i<n;++i)
  85. 			{
  86. 				sum+=a[i];
  87. 			    //printf(" %d ",sum);
  88. 				count[j]=i;
  89. 				++j;
  90. 				k=0;
  91. 				if(sum==value)
  92. 					{
  93. 						while(--j>=0)
  94. 							{
  95. 								if(count[j]!=-1)
  96. 								a[count[j]]=0;
  97. 							}
  98. 						return 1;
  99. 					}
  100. 				else if(sum>value)
  101. 					{
  102. 						finds=search(a,n,sum-value);//error can be here
  103. 						//printf("%d",a[finds]);
  104. 						if(finds!=-1)
  105. 							{
  106. 								l=j;
  107. 								while(--j>=0)
  108. 									{	
  109. 										if(count[j]!=finds)	
  110. 											a[count[j]]=0;
  111.  
  112. 									}
  113. 										return 1;
  114. 							}
  115. 						else
  116. 						{
  117. 						while(sum>value)
  118. 							{
  119. 								sum=sum-a[count[k]];
  120. 								count[k]=-1;
  121. 								++k;	
  122. 							}
  123. 						if(sum==0)	
  124. 							{
  125. 								return 0;
  126. 							}
  127. 						}
  128. 					}
  129. 			}
  130. 	}
  131. int main()
  132. 	{
  133. 		int m,i,t,n,k,x=0,sanskar,sum,diff,check=0;
  134. 		int a[50];
  135. 		scanf("%d",&t);
  136. 		int count;
  137. 		start:
  138. 		while(t-->0)
  139. 			{
  140. 				sum=0;
  141. 				count=0;
  142. 				scanf("%d%d",&n,&k);
  143. 				for(i=0;i<n;++i)
  144. 					{
  145. 						scanf("%d",&a[i]);
  146. 						sum+=a[i];
  147. 					}
  148. 				sort(a,n);
  149. 				if(sum%k!=0)
  150. 					printf("no\n");
  151. 				else if(sum==0)
  152. 					{
  153. 						printf("yes");
  154. 						goto start;
  155. 					}
  156. 				else
  157. 					{
  158. 						sanskar=sum/k;
  159. 						sort(a,n);
  160. 						while(k-->0)
  161. 							{
  162. 								check=find(a,n,sanskar);
  163. 								if(check==0)
  164. 									{
  165. 										printf("no\n");
  166. 										goto start;
  167. 									}
  168. 								sort(a,n);
  169.  
  170. 								//printf(" %d\n",a[n-1]);
  171. 							}
  172. 						//printf("%d",a[n-1]);
  173. 						if(a[n-1]==0)
  174. 							{
  175. 								printf("yes\n");
  176. 							}
  177. 						else
  178. 							printf("no\n");	
  179. 					}
  180.  
  181. 			}
  182. 	}
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
1
6 2
4 5 8 9 6 4
stdout
copy 
no
https://ideone.com/V8i72N
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!