10324 - Zeros and Ones

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:
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'

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Re: about acm 10324

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"

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
"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.

sweko
New poster
Posts: 7
Joined: Fri Apr 19, 2002 4:05 pm

How long can a Pascal string be?

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
Go:=(Line<>'');
if Go then begin
Writeln('Case ',n,':');
Inc(n);
for i:=1 to Dim do begin
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
SWeko has spoken

sweko
New poster
Posts: 7
Joined: Fri Apr 19, 2002 4:05 pm

How long can a Pascal string be?

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
Go:=(Line<>'');
if Go then begin
Writeln('Case ',n,':');
Inc(n);
for i:=1 to Dim do begin
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
SWeko has spoken

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
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.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10324 Did anybody solve this problem (got accepted)?

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
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;
end;
gstr := True;
mptr := mptr - 2;
end;

begin
cs:=1;
flag := gstr;
while( flag ) do
begin
writeln('Case ',cs,':');
for i:=1 to n do
begin
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.

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm
Maybe you should check if you've reached end of file:

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

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

10324 wa

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
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, ':');
while m > 0 do
begin
dec(m);
if (a[p] = a[q]) or (abs(a[p]-a[q]) = abs(p-q)) then writeln('Yes') else writeln('No');
end;

end;
end.
[/pascal]

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
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

Case 1:
Yes
No
Yes
No
Yes

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
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.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Probably it's time to move on and use 32-bit compilers. I used gcc from cygwin.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
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

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm