497 - Strategic Defense Initiative

[willy]

I edited my program many times but still dunno why i get invalid memory reference all the time, can anyone tell me?
#include <stdio.h>
#include <string.h>

int main()
{
int n,data[100000],best[100000],a,b,now,max,pre[100000],last,show[100000],count;

scanf("%d",&n);
while (n > 0)
{
for (a = 0; a < 100000; a++)
{
best[a] = 1;
pre[a] = 0;
}
now = 0;
while(scanf("%d",&data[now])==1)
now++;
max = 1;
for (a = 0; a < now-1; a++)
{
for (b = a+1; b < now; b++)
if (data > data[a])
if (best[a]+1>best)
{
best=best[a]+1;
if (best > max)
{
last = b;
max = best;
}
pre = a;
}
}
printf("Max hits: %d",max);
count = 0;
show[count] = last;
count++;
now = last;
max--;
while(max)
{
show[count] = pre[now];
now = pre[now];
count++;
max--;
}
for (a = count -1; a >= 0;a--)
printf("\n%d",data[show[a]]);
printf("\n");
n--;
if (n > 0)
printf("\n");
}

return 0;
}

[UFP2161]

[cpp]while (scanf ("%d", &data[now]) == 1)
now++;[/cpp]
Q: Does this actually stop when you encounter a blank line between input blocks?

[willy]

It stops, isn't it supposed to?

[Dominik Michniewski]

It doesn't stop, because scanf() ignore all whitespaces:
so for input:
1
<CR>
<CR>
<CR>
2
scanf() reads 1 first time .... and 2 second time ...

Best regards
DM

[willy]

I modified my code to detect empty lines, but now i get WA.... I dunno whats wrong....
[cpp]
#include <stdio.h>
#include <string.h>

int main()
{
int n,data[10000],best[10000],a,b,now,max,pre[10000],last,show[10000],count;
char abc[255];

scanf("%d\n\n",&n);
while (n > 0)
{

memset(pre,0,sizeof(pre));
now = 0;
do
{
if(gets(abc)==NULL||strlen(abc)<1)
break;
sscanf(abc,"%d",&data[now]);
now++;
}while (abc[0]!=' ');
for (a = 0; a < now; a++)
best[a] = 1;
max = 1;
for (a = 0; a < now-1; a++)
{
for (b = a+1; b < now; b++)
{
if (best == 0)
best = 1;
if (data > data[a])
if (best[a]+1>best)
{
best=best[a]+1;
if (best > max)
{
last = b;
max = best;
}
pre = a;
}
}
}
printf("Max hits: %d",max);
count = 0;
show[count] = last;
count++;
now = last;
max--;
while(max)
{
show[count] = pre[now];
now = pre[now];
count++;
max--;
}
for (a = count -1; a >= 0;a--)
printf("\n%d",data[show[a]]);
printf("\n");
n--;
if (n > 0)
printf("\n");
}

return 0;
}[/cpp]

[r.z.]

I have tested my code using various kinds of sample inputs but it still WA

but then I look the problem is multiple input type

so do I have to input the number of test case first?
and if I do, what input that shows the end of input for one test case?

thanks before

[deddy one]

yes you must take the test case number first

for each of the input block it will ended with
a blank line, except for the last input
block which will be ended with
the end of file marker.

don't use scanf in problem like this.

just use gets to scan all the input
than convert it to int.


hope this helps.

[deddy one]

I almost forget that after you take the test
case number, there is a blank line also.

make sure you take care of that too.

[r.z.]

still generating the wrong output

it generates

Max hits: 0
-858993460

Max hits: 4
1
2
3
5

Max hits: 3
7
18
45

Max hits: 2
1
2

Max hits: 4
1
4
5
6

instead of

Max hits: 4
1
2
3
5

Max hits: 3
7
18
45

Max hits: 2
1
2

Max hits: 4
1
4
5
6

Max hits: 3
1
3
5

I still have problem with the multiple input.....

[Hisoka]

[c]int main()
{
scanf("%d\n",&testcase);
while(testcase--)
{
your_input ...
Process();
your_output ...
if(testcase) puts("");
}
return 0;
}[/c]

[r.z.]

thanks
got acc

[aakash_mandhar]

There seems to be a problem with my code.. cant find out what.. Plz Help me out.
Thx in advance

I guess problem is with accepting blank lines.... Please help can anyone compare answers with his ac and lemme know .. Thx..
[cpp]
# include<stdio.h>
# include<string.h>

int a[1000],count;
int sol[1000];
int v[1000],vc;
char str[1000];
int i,hit,max;

void solve(int x)
{
if(x>=count) return;
v[hit++]=a[x];
if(hit>max) {max=hit;for(int y1=0;y1<max;y1++) sol[y1]=v[y1];}
for(int y=x+1;y<count;y++)
if(a[y]>a[x]) {solve(y);}
hit--;
}

int main()
{
int nt;
scanf("%d",&nt);
fflush(stdin);
gets(str);
fflush(stdin);
gets(str);

while(nt--)
{
max=0;
count=0;

while(1)
{
fflush(stdin);
gets(str);
if(strcmp(str,"")==0) break;
sscanf(str,"%d",&a[count++]);
}

for(i=0;i<count;i++) {hit=0;solve(i);}

printf("Max hits: %d\n",max);
for(i=0;i<max;i++) printf("%d\n",sol);
if(nt) printf("\n");
}
return 1;
}
[/cpp]

[kiha]

Er ... I don't know what's wrong with your program , but ... :>

I don't understand the algorithm which you use in your program . If somebody can explain it to me , I'd be very pleased ... I know it isn't a difficult problem , but I can't invent the proper method :/ Maybe if I understood the algorithm , I would understand the reason why you were given P.E.

And - one more thing . I write in Pascal , but I've never heard about VAL command . [ Although when I copied your program to Free Pascal it compiled it and in Turbo Pascal it didn't compile it :/ ] Please tell me what does this command mean

[pavelph]

Val(s: string, n: integer, code: integer) is procedure that do:
n:=integer(s).
Example: If s='123' then n -> 123;
If s -- integer than code = 0
else code = position where were error.
n can be also byte, longint, real etc

[anupam]

It's probably because you haven't print a blank line separating two outoput cases. And/or you have put an extra blank line at the end of he output.
--
check it(I don't know pascal) so can't help you checking the src.
--
Anupam