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:

Post by dh3014 » Fri Jul 19, 2002 1:19 pm

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

Post by dh3014 » Sat Jul 20, 2002 2:50 pm

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

Post by .. » Wed Jul 24, 2002 10:28 am

"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?

Post by sweko » Mon Jul 29, 2002 12:42 pm

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
SWeko has spoken

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

How long can a Pascal string be?

Post by sweko » Mon Jul 29, 2002 1:54 pm

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
SWeko has spoken

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Mon Jul 29, 2002 6:00 pm

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

Post by xenon » Mon Jul 29, 2002 11:36 pm

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)?

Post by medv » Wed Jul 31, 2002 1:17 pm

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.

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm

Post by gawry » Mon Aug 05, 2002 4:36 pm

Maybe you should check if you've reached end of file:

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

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

10324 wa

Post by lowai » Wed Nov 13, 2002 4:14 pm

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]

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Sat Feb 08, 2003 8:37 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

Your Ouput:
Case 1:
Yes
No
Yes
No
Yes

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Fri Mar 28, 2003 7:44 pm

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:

Post by turuthok » Sat Mar 29, 2003 12:03 am

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).

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Sat Mar 29, 2003 6:11 pm

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

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Sun Mar 30, 2003 8:44 pm

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

Post Reply

Return to “Volume 103 (10300-10399)”