231 - Testing the CATCHER

[ferasferas]

hi all can anyone help me debugging this code
its a simple Dp problem and iam sure of my code but it gives WA???

Code: Select all

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int main(int argc, char**argv) {


    int cnt=0;
    int number;
    
    while(1)
    {
        if(cnt!=0)cout<<endl;

        scanf("%d",&number);
        
        if(number==-1)goto end;

        
    cnt++;
    vector<int> input;
    input.push_back(number);
    
    while(scanf("%d",&number)==1)
    {
        if(number==-1)break;
        input.push_back(number);
    }

    int n=input.size();
    int dp[n];
    int maximum=0;
    for(int i=0;i<input.size();i++)
    {
        dp[i]=1;

        for(int j=0;j<i;j++)
            if(input[i]<=input[j])dp[i]=max(dp[i],dp[j]+1);

        maximum=max(dp[i],maximum);
    }

    cout<<"Test #"<<cnt<<':'<<endl;
    cout<<"  maximum possible interceptions: "<<maximum;

    }

 
    end:
    return 0;
}

[toru]

Hi, i m repeatedly getting WA for this problem, nothing i can do.....................plzzzz any1 help me........................
even i checked the i/o posted here all works but WA.....................

Code: Select all

#include<stdio.h>

long height[10000], length[10000];

int main()
{
	long i, j, count, n, max;
    
	count=0;
	while(1)
	{
		scanf("%ld", &height[0]);

		length[0]=1;
		if(height[0]<0)
			break;

		n=1;
		while(scanf("%ld", &height[n])==1)
		{
			if(height[n]<0)
				break;

			length[n]=1;			
			for(j = n-1; j>=0; j--)
			{
				if(height[n] <= height[j] && (length[j] + 1) > length[n])
				{ 
					length[n]= 1+length[j]; 
				}
			}
			n++;
		}

		max=1;
		for(i=0; i<=n; i++)
		{
			if(max<length[i])
				max=length[i];
		}
		

		printf("Test #%ld:\n",++count);
		printf("  maximum possible interceptions: %ld\n\n",max);

		for(i=0; i<=n; i++)
			length[i]=height[i]=0;
	}
			
	return 0;
}

[Márcio]

Hi toru.
Note the '\n' in the last line.
"There must be at least one blank line between output for successive data sets."

[nisuh_w]

Code: Select all

#include<stdio.h>
int data[40000];
int main(){
	int cases=1;
	while(1){
		int n=0;
		while(scanf("%d",&data[n++])==1){
			if(data[n-1]==-1)break;
		}
		if(data[0]==-1)break;
		n--;
		int length[n],maxlen=1;
		for(int i=0;i<n;i++)
			length[i]=1;
		for(int i=0;i<n-1;i++){
			for(int j=i+1;j<n;j++){
				if(data[j]<=data[i]&&length[i]+1>length[j])
					length[j]=length[i]+1;
				if(length[j]>maxlen)
					maxlen=length[j];
			}
		}
		printf("Test #%d:\n",1);
		printf("  maximum possible interceptions: %d",maxlen);
		puts("\n");
	}
	return 0;
}

why WA??

[codeworrior]

i am getting WA for my code...can anyone tell what is the mistake in it...


#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
long int n=0,x,cases=0;
vector<long int> a;
a.reserve(1000);
here:
scanf("%ld",&x);
while(x!=-1){
a.push_back(x);
scanf("%ld",&x);}
n=a.size();
long int ls[n];
for(long int i=0;i<n;i++)
ls=1;
for(long int i=0;i<n;i++)
{
for(long int j=0;j<i;j++)
{if(a<=a[j] && ls[j]>=ls)
ls=ls[j]+1;
}}
long int largest=0;

for(long int i=0;i<n;i++)
{if(largest<ls)
largest=ls;
}
cases++;
printf("Test #%ld:\n",cases);
printf(" ");
printf("maximum possible interceptions: ");
printf("%ld\n",largest);
printf("\n");
a.resize(0);
scanf("%ld",&n);
if(n!=-1)
goto here;
return 0;

}


also provide some good test cases for the problem...

[codeworrior]

i am getting WA for my code...can anyone tell what is the mistake in it...


#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
long int n=0,x,cases=0;
vector<long int> a;
a.reserve(1000);
here:
scanf("%ld",&x);
while(x!=-1){
a.push_back(x);
scanf("%ld",&x);}
n=a.size();
long int ls[n];
for(long int i=0;i<n;i++)
ls=1;
for(long int i=0;i<n;i++)
{
for(long int j=0;j<i;j++)
{if(a<=a[j] && ls[j]>=ls)
ls=ls[j]+1;
}}
long int largest=0;

for(long int i=0;i<n;i++)
{if(largest<ls)
largest=ls;
}
cases++;
printf("Test #%ld:\n",cases);
printf(" ");
printf("maximum possible interceptions: ");
printf("%ld\n",largest);
printf("\n");
a.resize(0);
scanf("%ld",&n);
if(n!=-1)
goto here;
return 0;

}


also provide some good test cases for the problem...

[codeworrior]

someone give the answer for my ques....thnx in advance..

[codeworrior]

//code removed after ac.


this is my code & its working fine for all the test cases i can think for....bt getting WA...any help...

[frank44]

If I recall correctly, there should be a blank line BETWEEN test cases, but not after the last one.

[codeworrior]

//code removed after ac.



got presentation error for this...does it mean that my ans is correct jst the formatting is wrong????
and where is the error??

[codeworrior]

got acc..thanks buddy..

[toru]

Hi all i m repeatedly getting WA in these problem, i did problem 497(strategic defense......) using the same algo i used here, even i guess my algo works just fine, bt i cant get where my mistake is, i checked many i/o and didnt find any of these going wrong, can any1 help me on this.... thankz... in advance.....

Code: Select all

#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;

#define MAX 10000

long c[MAX][MAX], N;
long sorted[MAX], unsort[MAX];

long LCS_LENGTH()
{
	long i, j;

	for(i=0; i<=N; i++)
		c[i][0]=0;
	for(j=0; j<=N; j++)
		c[0][j]=0;

	for(i=1; i<=N; i++)
		for(j=1; j<=N; j++)
			if(sorted[i-1]==unsort[j-1])
			{
				c[i][j]=c[i-1][j-1]+1;
			}
			else if(c[i-1][j]>=c[i][j-1])
			{
				c[i][j]=c[i-1][j];
			}
			else
			{
				c[i][j]=c[i][j-1];
			}

	return c[N][N];
}

int fun_name(  const void *a, const void *b )
{
	long *p = (long *)a;  
	long *q = (long *)b;  
	
	return *q - *p ;   
}

int main()
{
	long n, ii, height, testcase=1;

	while(1)
	{
		scanf("%ld", &n);
		if(n<0)
			break;
		else
		{
			unsort[0]=n;
			sorted[0]=n;

			ii=1;
			while(1)
			{
				scanf("%ld", &n);
				if(n<0)
					break;
				else
				{
					sorted[ii]=n;
					unsort[ii]=n;
					ii++;
				}
			}
		}

		N=ii;

		qsort( sorted, N, sizeof(long), fun_name );
		height=LCS_LENGTH();

		printf("Test #%ld:\n",testcase);
		printf("  maximum possible interceptions: %ld\n\n",height);
		testcase++;
	}
	return 0;
}

[Sadasidha08]

#include<iostream.h>
#include<stdlib.h>

#define MAX 100000

void swap(long& x,long& y)
{
int t=x;
x=y;
y=t;
}
int max(int x,int y)
{
if(x>y)
return x;
else
return y;
}

long arry[MAX][MAX]={0,};
int main()
{
long ar1[MAX],ar2[MAX];

long n,t=0,i,j,k;

while(1)
{
t++;
cin>>n;
if(n==-1)
break;
j=0;
while(1)
{
ar2[j]=ar1[j]=n;
for(k=j;k>0;k--)
{
if(ar2[k]>ar2[k-1])
swap(ar2[k],ar2[k-1]);
}
cin>>n;
j++;
if(n==-1)
break;


}


int m=j;

for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
{
if(ar1[i-1]==ar2[j-1])
arry[j]=arry[i-1][j-1]+1;
else
arry[j]=max(arry[j-1],arry[i-1][j]);
}
}


if(t!=1)
cout<<"\n";

cout<<"Test #"<<t<<":\n";
cout<<" maximum possible interceptions: "<<arry[m][m];

}


return 0;
}

[simp1eton]

I still get WA . I passed all the 11 cases given by Nick and got the same answers as Larry. Can someone help me? Is my output format wrong (I copied directly from problem statement) ?

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>
#include <algorithm>
using namespace std;

int t,N,L,S[3000005],T;
vector <int> V;
bool flag;

int main(){
	while(scanf("%d",&t) == 1){
		if(t != -1) V.push_back(t);
		else{
			if(V.empty()) break;
			N = V.size();
			reverse(V.begin(),V.end());
			L = 0;
			for(int i=0;i<N;++i){
				if(!L){
					S[0] = V[i];
					L = 1;
				}
				else{
					t = upper_bound(S,S+L,V[i])-S;
					S[t] = V[i];
					L = max(t+1,L);
				}
			}
			printf("Test #%d:\n",++T);
			printf("  maximum possible interceptions: %d\n",L);
			V.clear();
		}
	}
}
   

[MoustafaGad]

You are printing an extra new line after the last test result