Page 3 of 12

Posted: Fri Jul 19, 2002 1:19 pm
by dh3014
I think you may try enlarge your buf[] array size to:
[c]
char buf[1000002];
[/c]
instead of 1000000, the reason we need two more space is because you need one char to store the ending char '\0', and the other one, since you use fgets, will store the end line char '\n'

Re: about acm 10324

Posted: Sat Jul 20, 2002 2:50 pm
by dh3014
Homeway Liu wrote:[c]
c = num - num[a];
if( c == 0 || c == b - a)
printf("Yes\n");
[/c]

sorry I didn't look your code carefully first time.
I found the above statement is absolutely incorrect...
try the following input:
01
1
0 1
You'll found your program output "Yes"

Posted: Wed Jul 24, 2002 10:28 am
by ..
"Each query is given by two non-negative integers, i and j. "
Did you handle if i > j?

And there are two possible ways for the end of input:
1. "The input ends with an empty string that is a line containing only the new line character, this string should not be processed. "
2. "The input may also with end of file."
Did you handle them correctly?

I think these two are the possible source of WA.

How long can a Pascal string be?

Posted: Mon Jul 29, 2002 12:42 pm
by sweko
I'm trying to solve 10324, using a string to read in the characters.
Using my compiler (Delphi 5) i can get it right using 1000000 characters,
but i keep getting WA from the judge.

Are Pascal strings limited to 255B (1 byte string lenght) or 2GB (2 byte string lenght - ANSI String)?

[pascal]
program P10324;

type TArray = array[1..1000000] of Boolean;

var Niza:TArray;
i,Dim,Jen,Dva,n:Integer;
NizaLen:Integer;
Go:Boolean;
Line:string;

procedure ReadArray(Line:string;var ANiza:TArray;var Len:Integer);
var i:Integer;
begin
FillChar(ANiza,SizeOf(ANiza),False);
for i:=2 to Length(Line) do begin
if Line<>Line[i-1] then ANiza[i-1]:=True;
end;
Len:=Length(Line)-1;
end;

function IsSame(Niza:TArray;Len,Start,Kraj:Integer):string;
var i,tmp:Integer;
rez:Boolean;
begin
if Start>Kraj then begin
tmp:=Start;
Start:=Kraj;
Kraj:=tmp;
end;
if Kraj>Len then Kraj:=Len;
if Kraj<0 then Kraj:=0;
if Start>Len then Start:=Len;
if Start<0 then Start:=0;
i:=Start+1;
rez:=True;
while (i<=Kraj) and rez do begin
if Niza then rez:=False;
Inc(i);
end;
if rez then IsSame:='Yes' else IsSame:='No';
end;

begin
n:=1;Go:=True;
while (not Eof) and (Go) do begin
Readln(Line);
Go:=(Line<>'');
if Go then begin
ReadArray(Line,Niza,NizaLen);
Writeln('Case ',n,':');
Inc(n);
Readln(Dim);
for i:=1 to Dim do begin
Readln(Jen,Dva);
Writeln(IsSame(Niza,NizaLen,Jen,Dva));
end;
end;
end;
end.
[/pascal]

Btw, in the program I (think I) check for both eof and blank line - it's in the problem description, so i guess that's not the problem

How long can a Pascal string be?

Posted: Mon Jul 29, 2002 1:54 pm
by sweko
I'm using a string to read in the characters.
Using my compiler (Delphi 5) i can get it right using 1000000 characters,
but i keep getting WA from the judge.

Are Pascal strings limited to 255B (1 byte string lenght) or 2GB (2 byte string lenght - ANSI String)?

Here's my Program
[pascal]
program P10324;

type TArray = array[1..1000000] of Boolean;

var Niza:TArray;
i,Dim,Jen,Dva,n:Integer;
NizaLen:Integer;
Go:Boolean;
Line:string;

procedure ReadArray(Line:string;var ANiza:TArray;var Len:Integer);
var i:Integer;
begin
FillChar(ANiza,SizeOf(ANiza),False);
for i:=2 to Length(Line) do begin
if Line<>Line[i-1] then ANiza[i-1]:=True;
end;
Len:=Length(Line)-1;
end;

function IsSame(Niza:TArray;Len,Start,Kraj:Integer):string;
var i,tmp:Integer;
rez:Boolean;
begin
if Start>Kraj then begin
tmp:=Start;
Start:=Kraj;
Kraj:=tmp;
end;
if Kraj>Len then Kraj:=Len;
if Kraj<0 then Kraj:=0;
if Start>Len then Start:=Len;
if Start<0 then Start:=0;
i:=Start+1;
rez:=True;
while (i<=Kraj) and rez do begin
if Niza then rez:=False;
Inc(i);
end;
if rez then IsSame:='Yes' else IsSame:='No';
end;

begin
n:=1;Go:=True;
while (not Eof) and (Go) do begin
Readln(Line);
Go:=(Line<>'');
if Go then begin
ReadArray(Line,Niza,NizaLen);
Writeln('Case ',n,':');
Inc(n);
Readln(Dim);
for i:=1 to Dim do begin
Readln(Jen,Dva);
Writeln(IsSame(Niza,NizaLen,Jen,Dva));
end;
end;
end;
end.
[/pascal]

For a input of 999995 0's and 5 1's and the following queries:
5
0 100
0 1000000
999991 999994
999991 999995
999997 999999

i get:
Yes
No
Yes
No
Yes

which should be corre.ct

Btw, in the program I (think I) check for both eof and blank line so i guess that's not the problem

Posted: Mon Jul 29, 2002 6:00 pm
by Ivor
If I remeber correctly, Pascal's string was of structure:
| 1 byte | up to 255 bytes |
The first byte is used for string length.

Delphi's string length was determined by first 4 bytes giving you 2GB strings at max. I remeber reading about it some long time ago.

Ivor

Posted: Mon Jul 29, 2002 11:36 pm
by xenon
You can use longstrings too by specifying the length:
[pascal]type longstring=string(1000000);[/pascal]
The default is string(255), but I don't know if it's a standard pascal shortstring (i.e. with the length in byte 0).

Since this is quite not-standard, most compilers will not know what to do with this. My Free Pascal compiler uses square brackets, so I use the clause:
[pascal]{$IFNDEF ONLINE_JUDGE}
type longstring=string[1000000];
{$ELSE}
type longstring=string(1000000);
{$ENDIF}
[/pascal]
so it works on both compilers.

10324 Did anybody solve this problem (got accepted)?

Posted: Wed Jul 31, 2002 1:17 pm
by medv
10324 Is there anybody who solved this problem (got accepted)?

I am tired to look for mistakes in my program. It seems to me work right.
Please, if you got accepted this problem, send your solution for me to medv@roller.ukma.kiev.ua

My program says WA:

(* @JUDGE_ID: 4406RA 10324 PASCAL "string processing" *)

program Zeroes_and_Ones_10324;
const mx = 1000002;
var
flag:boolean;
m:array[0..mx] of longint;
cs,a,b,t,n,i,j:longint;
mptr:longint;

function gstr:boolean;
var
c,cprev:char;
begin
read(c);
if (not (c in ['0','1'])) then
begin
gstr := false; mptr := 0; Exit;
end;
mptr:= 1; m[0] := 1; cprev := c;
while (c in ['0','1']) do
begin
if (c = cprev) then m[mptr] := m[mptr-1]
else m[mptr] := m[mptr-1] + 1;
Inc(mptr);
cprev := c;
read(c);
end;
gstr := True;
mptr := mptr - 2;
end;

begin
cs:=1;
flag := gstr;
while( flag ) do
begin
writeln('Case ',cs,':');
readln(n);
for i:=1 to n do
begin
readln(a,b);
if ((a < 0) or (b < 0) or (a > mptr) or (b > mptr)) then
begin
writeln('No'); continue;
end;
Inc(a); Inc(b);
if (a > b) then
begin
t := a; a := b; b := t;
end;
if (m[a] = m[b]) then writeln('Yes')
else writeln('No');
end;
Inc(cs);
flag := gstr;
end;
end.

Posted: Mon Aug 05, 2002 4:36 pm
by gawry
Maybe you should check if you've reached end of file:

if eof(input) then
c:='#'
else
read(input,c);

10324 wa

Posted: Wed Nov 13, 2002 4:14 pm
by lowai
what's wrong with this code?
[pascal]
var
a : array[0..1000000] of longint;
ch : char;
m, n, p, q : longint;
caseno : integer;

begin
caseno := 0;
while not eof do
begin
fillchar(a, sizeof(a), 0);
n := -1;
while not eoln do
begin
read(ch);
if (ch = '1') or (ch = '0') then
begin
inc(n); a[n] := a[n-1];
if ch = '1' then inc(a[n]);
end;
end;

if n = -1 then break;

inc(caseno);

writeln('Case ', caseno, ':');
readln(m);
while m > 0 do
begin
dec(m);
readln(p, q);
if (a[p] = a[q]) or (abs(a[p]-a[q]) = abs(p-q)) then writeln('Yes') else writeln('No');
end;

end;
end.
[/pascal]

Posted: Sat Feb 08, 2003 8:37 am
by Red Scorpion
Try This test case:
Input:

000011111
5
0 3
0 4
4 5
2 4
9 11

RIGHT OUPUT:
Case 1:
Yes
No
Yes
No
No

Your Ouput:
Case 1:
Yes
No
Yes
No
Yes

Posted: Fri Mar 28, 2003 7:44 pm
by saiqbal
your problem seems so simple!! :)
declare a character array of size 1000001 and just read an string. following code wud work:
[cpp]char str[1000001];
int main()
{
cin>>str;
return 0;
}
[/cpp]

good luck
-sohel

ps- always declare such large arrays global.

Posted: Sat Mar 29, 2003 12:03 am
by turuthok
Probably it's time to move on and use 32-bit compilers. I used gcc from cygwin.

-turuthok-

Posted: Sat Mar 29, 2003 6:11 pm
by saiqbal
no, its not. the idea is, you implement your algorithm with lower limits (which can be supported by your compiler) and increase the limits when you submit. if your algorithm is right you should get AC.

its only a trick to use older compilers for this kind of problem. but i guess using a 32-bit compiler (ie. VC, gcc, etc.) instead is better idea.

thanx
-sohel

Posted: Sun Mar 30, 2003 8:44 pm
by saiqbal
i found several mistakes in your code:
1. it seems that you did a mistake declaring the char array. it should be at least 1000001.
2. you don't need to store all the queries which you did using a huge array!!
3. i once gave an advice to declare large arrays global. declaring large arrays local might cause segmentation fault.
4. finally, the approach you took to solve this problem is simply bruteforce which implies that you'll definitely get a TLE :wink:

good luck
-sohel