fork download
copy 
  1. #include<stdio.h>
  2. char stack[100];
  3. long long int st[100];
  4. long long int top=-1;
  5. long long int g,kk;
  6. int priority(char c)
  7. {
  8. 	if(c=='+'||c=='-')
  9. 	 return 3;
  10. 	 if(c=='*')
  11. 	 return 4;
  12.  
  13. }
  14. void evaluate(char *post)
  15. {
  16.    int i,val1,val2;
  17. 	top=-1;
  18. 	for(i=0;post[i];i++)
  19. 	{
  20. 		if(post[i]>='0'&&post[i]<='9')
  21. 		 st[++top]=post[i]-48;
  22. 		 else
  23.          	{
  24.          		val1=st[top];
  25.          		top--;
  26.          		val2=st[top];
  27.          		top--;
  28.          		switch (post[i])
  29.                 {
  30.                   case '+': st[++top]= val2 + val1; break;
  31.                   case '-': st[++top]= val2 - val1; break;
  32.                   case '*': st[++top]= val2 * val1; break;
  33.                 }
  34.  
  35. 		   }	 
  36.  
  37. 	}
  38. 	if(st[top]==kk)
  39. 	{
  40.  // printf("\ntrueeeeeeeeee  %s\n",post);
  41. 	g=1;
  42. }
  43. }
  44.  
  45. void converintopostfix(char *p)
  46. {
  47. 	int i,k=0;char post[50];
  48. 	for(i=0;p[i];i++)
  49. 	{
  50. 		if(p[i]>='0'&&p[i]<='9')
  51. 		post[k++]=p[i];
  52. 		else 
  53. 		{
  54. 			while(top!=-1&&(priority(stack[top])>=priority(p[i])))
  55. 			{
  56. 				post[k++]=stack[top];
  57. 				top--;
  58. 			}
  59. 			stack[++top]=p[i];
  60. 		}
  61. 		//printf("%c",p[i]);
  62. 	}
  63. 	while(top!=-1)
  64. 	{
  65. 		post[k++]=stack[top];
  66. 				top--;
  67.  
  68. 	}
  69. 	post[k]='\0';
  70. 	evaluate(post);
  71. 	//printf("  %s\n",post);
  72. }
  73.  
  74. int permute(long long int *arr,char *str,char *ch,long long int n,long long int k,long long int j)
  75. {
  76. 	long long int i;
  77. 	//printf("hi");
  78. 	if(j==n)
  79. 	{//printf("hii");
  80. 		ch[k-1]='\0';
  81. 		//printf("%s\n",ch);
  82. 		top=-1;
  83. 		converintopostfix(ch);
  84. 		return 0;
  85. 	}
  86. 	for(i=0;i<3;i++)
  87. 	{
  88. 		ch[k]=arr[j]+48;
  89. 		ch[k+1]=str[i];
  90. 		if(!permute(arr,str,ch,n,k+2,j+1))
  91. 		return 1;
  92. 	}
  93. 	return 1;
  94. }
  95. int main()
  96. {
  97. 	long long int t,n,arr[15],i;
  98. 	char ch[50],str[5]={'+','-','*'};
  99. 	scanf("%lld",&t);
  100. 	while(t--)
  101. 	{   g=0;
  102. 		scanf("%lld%lld",&n,&kk);
  103.  
  104. 		for(i=0;i<n;i++)
  105. 		scanf("%lld",&arr[i]);
  106.                if(n==1&&arr[0]==kk)
  107. 		{
  108. 			printf("YES\n");
  109. 			continue;
  110. 		}
  111. 		else if(n==1)
  112. 		{
  113. 			printf("NO\n");
  114. 			continue;
  115. 		}
  116. 		permute(arr,str,ch,n,0,0);
  117. 		if(g)
  118. 		printf("YES\n");
  119. 		else
  120. 		printf("NO\n");
  121. 	   }
  122. return 0;
  123. }
  124.  
Success #stdin #stdout 0s 2172KB
comments (?)
stdin
copy 
1
5 14
2 3 4 5 5
stdout
copy 
YES
https://ideone.com/9JqTiE
language:
C (gcc 8.3)
created:
7 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!