All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
ferasferas
New poster
Posts: 1 Joined: Tue Jul 21, 2009 3:49 am
Post
by ferasferas » Tue Jul 21, 2009 3:54 am
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
New poster
Posts: 17 Joined: Tue Dec 30, 2008 10:38 am
Post
by toru » Tue Jul 21, 2009 8:08 pm
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
New poster
Posts: 1 Joined: Sat Aug 15, 2009 11:38 pm
Post
by Márcio » Sat Aug 15, 2009 11:44 pm
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
New poster
Posts: 1 Joined: Thu May 21, 2009 12:02 pm
Post
by nisuh_w » Thu Sep 03, 2009 10:49 am
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
New poster
Posts: 14 Joined: Wed Oct 21, 2009 11:04 am
Post
by codeworrior » Fri Nov 06, 2009 7:44 am
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
New poster
Posts: 14 Joined: Wed Oct 21, 2009 11:04 am
Post
by codeworrior » Wed Nov 11, 2009 9:43 am
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
New poster
Posts: 14 Joined: Wed Oct 21, 2009 11:04 am
Post
by codeworrior » Fri Nov 20, 2009 9:10 am
someone give the answer for my ques....thnx in advance..
codeworrior
New poster
Posts: 14 Joined: Wed Oct 21, 2009 11:04 am
Post
by codeworrior » Mon Dec 14, 2009 1:50 pm
//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...
Last edited by
codeworrior on Sun Jan 10, 2010 11:29 am, edited 1 time in total.
frank44
New poster
Posts: 6 Joined: Fri Jan 09, 2009 4:01 am
Post
by frank44 » Thu Dec 31, 2009 7:47 pm
If I recall correctly, there should be a blank line BETWEEN test cases, but not after the last one.
codeworrior
New poster
Posts: 14 Joined: Wed Oct 21, 2009 11:04 am
Post
by codeworrior » Sun Jan 10, 2010 11:24 am
//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??
Last edited by
codeworrior on Sun Jan 10, 2010 11:28 am, edited 1 time in total.
toru
New poster
Posts: 17 Joined: Tue Dec 30, 2008 10:38 am
Post
by toru » Tue Jan 26, 2010 1:28 pm
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
New poster
Posts: 3 Joined: Mon Apr 05, 2010 8:09 pm
Post
by Sadasidha08 » Fri Jun 18, 2010 8:24 pm
#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
New poster
Posts: 2 Joined: Mon Dec 20, 2010 2:50 pm
Post
by simp1eton » Mon Dec 20, 2010 4:33 pm
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
New poster
Posts: 1 Joined: Fri Mar 16, 2012 4:44 am
Post
by MoustafaGad » Fri Mar 16, 2012 4:48 am
You are printing an extra new line after the last test result