10324 - Zeros and Ones

[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'

[dh3014]

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

[..]

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

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]

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

[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

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

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

[gawry]

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

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

[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]

[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

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

[turuthok]

Probably it's time to move on and use 32-bit compilers. I used gcc from cygwin.

-turuthok-

[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

[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

good luck
-sohel