12455 - Bars

All about problems in Volume 124. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

12455 - Bars

Post by ioi » Sat May 05, 2012 10:51 pm

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

Post by brianfry713 » Mon May 07, 2012 11:31 pm

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

Post by shuvrothpol1 » Tue Oct 16, 2012 5:07 pm

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

Post by brianfry713 » Wed Oct 17, 2012 1:08 am

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

Post by prokawsar » Wed Nov 25, 2015 7:04 am

Getting WA Please Help :(

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;
}


Post Reply

Return to “Volume 124 (12400-12499)”