## 12455 - Bars

Moderator: Board moderators

ioi
New poster
Posts: 8
Joined: Sat May 05, 2012 10:44 pm

### 12455 - Bars

pls help me out.. what's wrong with this one ????
I got WA

Code: Select all

``````#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MM 200008

int inp[25],track[MM];

int solve(int sum,int n,int val)
{
int i,j,k,l,inx;
track[0]=1;
for(i=1;i<=sum;i++)
{
track[i]=0;
}
for(i=0;i<n;i++)
{
for(j=sum;j>=0;j--)
{
if(track[j]==1)
{
inx=j+inp[i];
if(track[inx]!=1 && inx<=sum)
{
track[inx]=1;
}
}
}
}
return track[val];
}

int main()
{
int test,t,i,j,blen,nbar,sum,res;
scanf("%d",&test);
for(t=0;t<test;t++)
{
scanf("%d",&blen);
scanf("%d",&nbar);
sum=0;
for(i=0;i<nbar;i++)
{
scanf("%d",&inp[i]);
sum+=inp[i];
}
res=solve(sum,nbar,blen);
if(res)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
memset(inp,0,sizeof(inp));
}
return 0;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12455 Bars

If blen>sum print NO.
Check input and AC output for thousands of problems on uDebug!

shuvrothpol1
New poster
Posts: 17
Joined: Wed Aug 15, 2012 12:37 pm

### Re: 12455 Bars

wa.>>>>

Code: Select all

``````#include <stdio.h>
int a[20];
void sort_des(int p);
int result (int n,int p,int a[]);

int main ()

{
int t,n,p,i,j,x;

scanf ("%d",&t);
for (j=0;j<t;j++)
{
scanf ("%d%d",&n,&p);

for (i=0;i<p;i++)
scanf ("%d",&a[i]);
if (n!=0){
sort_des(p);
x=result(n,p,a);

if (x==1)
printf ("NO\n");
}
else
printf ("YES\n");
}
return 0;
}

void sort_des(int p)

{
int i,j,temp;

for (i=0;i<p-1;i++)
{
for (j=0;j<p-i;j++)
{
if (a[j]<a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}

int result (int n,int p,int a[])
{
int cal=0,i;
for (i=0;i<p;i++)
{
if (cal+a[i]<=n)
{
cal+=a[i];
if (cal==n)
{
printf ("YES\n");
return 0;
}
}
}
return 1;
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12455 Bars

Try input:
1
5
3
4 3 2
Check input and AC output for thousands of problems on uDebug!

prokawsar
New poster
Posts: 7
Joined: Tue Aug 04, 2015 5:01 pm

### Re: 12455 - Bars

Code: Select all

``````/*Date: 25.11.15
Problem: 12455 Bars
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int compare(const void *a, const void *b){
return ( *(int*) a - *(int*) b);
}

int main()
{
int t, i, j, l, m;
int num[22];
int x, c, n;

scanf("%d", &t);

while(t--){

scanf("%d", &c);
scanf("%d", &n);
x=1;

for(i=0; i<n; i++){
scanf("%d", &num[i]);
}
if(c==0) {
printf("YES\n");
continue;
}
qsort(num, n, sizeof(int), compare);

for(i=n-1; i>=0; i--){
if(num[i]==c){
printf("YES\n");
x=0;
break;
}
else if(num[i]> c){
continue;
}

for(j=i-1; j>=0; j--){
if((num[i]+num[j])>c){
continue;
}
else if(num[i]+num[j]==c){
printf("YES\n");
x=0;
break;
}
else num[i]+=num[j];
if(num[i]==c){
printf("YES\n");
x=0;
break;
}

}
if(x==0) break;
}
if(x==1) printf("N0\n");
}

return 0;
}

``````