497 - Strategic Defense Initiative

All about problems in Volume 4. 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
willy
New poster
Posts: 11
Joined: Fri Aug 01, 2003 2:20 pm
Location: Singapore

497 RTE

Post by 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
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by 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
New poster
Posts: 11
Joined: Fri Aug 01, 2003 2:20 pm
Location: Singapore

Post by willy »

It stops, isn't it supposed to?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by 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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

willy
New poster
Posts: 11
Joined: Fri Aug 01, 2003 2:20 pm
Location: Singapore

Post by 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.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

497 - wrong input maybe?

Post by 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
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by 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
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by 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.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by 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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

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

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. »

thanks
got acc :wink:

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Post by 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]
...I was born to code...

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by 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
kiha

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

About VAL

Post by 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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by 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
"Everything should be made simple, but not always simpler"

Post Reply

Return to “Volume 4 (400-499)”