10324 - Zeros and Ones
Moderator: Board moderators
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"
"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.
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?
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
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
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
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
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
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
| 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.
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.
[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)?
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.
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.
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
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]
[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]
-
- Experienced poster
- Posts: 192
- Joined: Sat Nov 30, 2002 5:14 am
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
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
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
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