10592 - Freedom Fighter
Moderator: Board moderators
10592 - Freedom Fighter
Could someone give some tricky inputs or outputs?
"It is granted that a freedom fighter group can fight only one opponent group at a time."
Means that we should calc how many freedom fighter connected to oppoent?
Am I right?
"It is granted that a freedom fighter group can fight only one opponent group at a time."
Means that we should calc how many freedom fighter connected to oppoent?
Am I right?
I calculated the number of groups of freedom fighters that are connected to the enemies. Then simply I multiply that amout by 2 to get the total.
I think the judge data does not contain severely technical inputs. And any general approach should get AC.
Try this
................................
.............B.................
........BBBB................
***..***P..................
................................
................................
................................
I think the judge data does not contain severely technical inputs. And any general approach should get AC.
Try this
................................
.............B.................
........BBBB................
***..***P..................
................................
................................
................................
Yes, I thought my method is the same as yours.sohel wrote:I calculated the number of groups of freedom fighters that are connected to the enemies. Then simply I multiply that amout by 2 to get the total.
The graph should be n*n, the input looks strange.I think the judge data does not contain severely technical inputs. And any general approach should get AC.
Try this
................................
.............B.................
........BBBB................
***..***P..................
................................
................................
................................
Have another tricky input/output? Thx
-
- Learning poster
- Posts: 67
- Joined: Sun Sep 22, 2002 5:40 am
- Location: Taiwan
-
- Experienced poster
- Posts: 187
- Joined: Wed Dec 11, 2002 2:03 pm
- Location: Mount Papandayan, Garut
-
- Learning poster
- Posts: 67
- Joined: Sun Sep 22, 2002 5:40 am
- Location: Taiwan
Sorry, I find my program have some bugs.
3
BBB
PPP
BBB
3
PPP
BBB
PPP
the last answer of mine are also equal to 4
(I don't know why I still got Accepted, maybe only simple connection will
occur.)
Some other sample
4
BB..
.PP.
B..P
BBBB
Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
Sector #2: contain 1 freedom fighter group(s) & 1 enemy group(s)
Total 4 group(s) are in fighting position.
5
B.B..
.P.P.
.PP.B
BB.P.
B...P
Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #2: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #3: contain 1 freedom fighter group(s) & 1 enemy group(s)
Sector #4: contain 0 freedom fighter group(s) & 1 enemy group(s)
Sector #5: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #6: contain 0 freedom fighter group(s) & 1 enemy group(s)
Sector #7: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 2 group(s) are in fighting position.
Good Luck
I check all Yours tests, and i had correct answers. I dont't know what's wrong with my code. Can You look at source, or give more inputs?
Thanks in advance.
[pascal]
type
flist=record
a,b:integer;
end;
var
se,t:array[0..115,0..155]of char;
fft,ent:array[1..2501]of integer;
out:array[1..5221,1..5541]of integer;
fl:array[1..5500]of flist;
spr:array[1..5500]of boolean;
spr2:array[1..5500]of integer;
bb,aa,zz,qq,f,reg,enc,ffc,n,m,bi,bk,z,i,j,d,s,k:longint;
label start;
procedure region(x,y:longint); forward;
procedure freef(x,y,z:longint);forward;
procedure ocup(x,y,z:longint);
begin
t[x,y]:='.';
if (t[x+1,y]='P') then ocup(x+1,y,0);
if (t[x-1,y]='P') then ocup(x-1,y,0);
if (t[x,y+1]='P') then ocup(x,y+1,0);
if (t[x,y-1]='P') then ocup(x,y-1,0);
if (t[x+1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x+1,y,1); end;
if (t[x-1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end; freef(x-1,y,1); end;
if (t[x,y+1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y+1,1); end;
if (t[x,y-1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y-1,1); end;
if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;
end;
procedure freef;
begin
t[x,y]:='.';
if (t[x+1,y]='B') then freef(x+1,y,0);
if (t[x-1,y]='B') then freef(x-1,y,0);
if (t[x,y+1]='B') then freef(x,y+1,0);
if (t[x,y-1]='B') then freef(x,y-1,0);
if (t[x+1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]); end; ocup(x+1,y,1); end;
if (t[x-1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x-1,y,1); end;
if (t[x,y+1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y+1,1); end;
if (t[x,y-1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y-1,1); end;
if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;
end;
procedure region;
begin
if t[x,y]= 'B' then
begin
inc(ffc);
freef(x,y,0);
end
else if t[x,y]= 'P' then
begin
inc(enc);
ocup(x,y,0);
end
else
begin
t[x,y]:='.';
if t[x+1,y]<>'.' then region(x+1,y);
if t[x-1,y]<>'.' then region(x-1,y);
if t[x,y+1]<>'.' then region(x,y+1);
if t[x,y-1]<>'.' then region(x,y-1);
end;
end;
begin
start:
{}{}{}{}{}{}{}{}{}{ read & clean }{}{}{}{}{}{}
for i:=0 to 51 do
for j:=0 to 51 do
begin
t[i,j]:='.';
se[i,j]:='.';
end;
k:=0;
n:=0;
m:=0;
readln(d);
if d=0 then exit;
for i:=1 to d do
begin
for j:=1 to d do
begin
read(t[i,j]);
end;
readln;
end;
m:=1;
{}{}{}{}{}{}{}{}{}{}{}{}{}{}{ EOF read }{}{}{}{}{}{}{}{}
{}{}{}{}{}{}{}{}{}{}{ seek }{}{}{}{}{}{}{}
for i:=1 to d do
begin
for j:=1 to d do
begin
if (t[i,j]='*')or (t[i,j]='B')or (t[i,j]='P') then
begin
inc(reg);
region(i,j);
for bb:=1 to aa do
begin
if t[fl[bb].a,fl[bb].b]<>'.' then region(fl[bb].a,fl[bb].a);
end;
for qq:=1 to 100 do
begin
if spr2[qq]<>0 then
begin
f:=1+f+spr2[qq];
spr2[qq]:=0;
end;
end;
for qq:=1 to ffc do
begin
spr[qq]:=false;
end;
f:=f+zz;
fft[reg]:=ffc;
ent[reg]:=enc;
ffc:=0;
enc:=0;
aa:=0;
bb:=0;
end;
end;
end;
{}{}{}{}{}{}{}{}{}{}{ EOF seek }{}{}{}{}{}{}{}
{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}
for i:=1 to reg do
begin
writeln('Sector #',i,': contain ', fft ,' freedom fighter group(s) & ', ent ,' enemy group(s)');
end;
writeln('Total ', f,' group(s) are in fighting position.');
Writeln('');
reg:=0;
f:=0;
{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}
goto start;
end.
[/pascal]
Thanks in advance.
[pascal]
type
flist=record
a,b:integer;
end;
var
se,t:array[0..115,0..155]of char;
fft,ent:array[1..2501]of integer;
out:array[1..5221,1..5541]of integer;
fl:array[1..5500]of flist;
spr:array[1..5500]of boolean;
spr2:array[1..5500]of integer;
bb,aa,zz,qq,f,reg,enc,ffc,n,m,bi,bk,z,i,j,d,s,k:longint;
label start;
procedure region(x,y:longint); forward;
procedure freef(x,y,z:longint);forward;
procedure ocup(x,y,z:longint);
begin
t[x,y]:='.';
if (t[x+1,y]='P') then ocup(x+1,y,0);
if (t[x-1,y]='P') then ocup(x-1,y,0);
if (t[x,y+1]='P') then ocup(x,y+1,0);
if (t[x,y-1]='P') then ocup(x,y-1,0);
if (t[x+1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x+1,y,1); end;
if (t[x-1,y]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end; freef(x-1,y,1); end;
if (t[x,y+1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y+1,1); end;
if (t[x,y-1]='B') then begin inc(ffc); if spr[ffc]=false then
begin spr[ffc]:=true; inc(spr2[enc]);end;freef(x,y-1,1); end;
if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;
end;
procedure freef;
begin
t[x,y]:='.';
if (t[x+1,y]='B') then freef(x+1,y,0);
if (t[x-1,y]='B') then freef(x-1,y,0);
if (t[x,y+1]='B') then freef(x,y+1,0);
if (t[x,y-1]='B') then freef(x,y-1,0);
if (t[x+1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]); end; ocup(x+1,y,1); end;
if (t[x-1,y]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x-1,y,1); end;
if (t[x,y+1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y+1,1); end;
if (t[x,y-1]='P') then begin inc(enc); if spr[ffc]=false then
begin spr[ffc]:=true;
inc(spr2[enc]);
end; ocup(x,y-1,1); end;
if (t[x+1,y]='*') then begin inc(aa); fl[aa].a:=x+1; fl[aa].b:=y; end;
if (t[x-1,y]='*') then begin inc(aa); fl[aa].a:=x-1; fl[aa].b:=y; end;
if (t[x,y+1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y+1; end;
if (t[x,y-1]='*') then begin inc(aa); fl[aa].a:=x; fl[aa].b:=y-1; end;
end;
procedure region;
begin
if t[x,y]= 'B' then
begin
inc(ffc);
freef(x,y,0);
end
else if t[x,y]= 'P' then
begin
inc(enc);
ocup(x,y,0);
end
else
begin
t[x,y]:='.';
if t[x+1,y]<>'.' then region(x+1,y);
if t[x-1,y]<>'.' then region(x-1,y);
if t[x,y+1]<>'.' then region(x,y+1);
if t[x,y-1]<>'.' then region(x,y-1);
end;
end;
begin
start:
{}{}{}{}{}{}{}{}{}{ read & clean }{}{}{}{}{}{}
for i:=0 to 51 do
for j:=0 to 51 do
begin
t[i,j]:='.';
se[i,j]:='.';
end;
k:=0;
n:=0;
m:=0;
readln(d);
if d=0 then exit;
for i:=1 to d do
begin
for j:=1 to d do
begin
read(t[i,j]);
end;
readln;
end;
m:=1;
{}{}{}{}{}{}{}{}{}{}{}{}{}{}{ EOF read }{}{}{}{}{}{}{}{}
{}{}{}{}{}{}{}{}{}{}{ seek }{}{}{}{}{}{}{}
for i:=1 to d do
begin
for j:=1 to d do
begin
if (t[i,j]='*')or (t[i,j]='B')or (t[i,j]='P') then
begin
inc(reg);
region(i,j);
for bb:=1 to aa do
begin
if t[fl[bb].a,fl[bb].b]<>'.' then region(fl[bb].a,fl[bb].a);
end;
for qq:=1 to 100 do
begin
if spr2[qq]<>0 then
begin
f:=1+f+spr2[qq];
spr2[qq]:=0;
end;
end;
for qq:=1 to ffc do
begin
spr[qq]:=false;
end;
f:=f+zz;
fft[reg]:=ffc;
ent[reg]:=enc;
ffc:=0;
enc:=0;
aa:=0;
bb:=0;
end;
end;
end;
{}{}{}{}{}{}{}{}{}{}{ EOF seek }{}{}{}{}{}{}{}
{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}
for i:=1 to reg do
begin
writeln('Sector #',i,': contain ', fft ,' freedom fighter group(s) & ', ent ,' enemy group(s)');
end;
writeln('Total ', f,' group(s) are in fighting position.');
Writeln('');
reg:=0;
f:=0;
{}{}{}{}{}{}{}{}{}{}{ output }{}{}{}{}{}{}{}
goto start;
end.
[/pascal]
About The Judge Input Data Set
In the judge input data set of this problem, it is clear that there is no such an input set that contain the data of four connected groups. Like..
PPPP
BBBB
PPPP
BBBB
Or,
BBBB
PPPP
BBBB
PPPP
You can consider that highest three groups are connected or in fighting
position.
Here I gave a sample input and output:
Input:
10
......****
.***.*BBBB
PPPP*.BPPP
BBBB*..BBB
PPPP*.***B
******....
B**BB*....
B**BB**..*
***BB**..P
P**BBBB..P
Output:
Sector #1: contain 2 freedom fighter group(s) & 1 enemy group(s)
Sector #2: contain 3 freedom fighter group(s) & 3 enemy group(s)
Sector #3: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 5 group(s) are in fighting position.
I think this will remove all confusions.
Mahmud
PPPP
BBBB
PPPP
BBBB
Or,
BBBB
PPPP
BBBB
PPPP
You can consider that highest three groups are connected or in fighting
position.
Here I gave a sample input and output:
Input:
10
......****
.***.*BBBB
PPPP*.BPPP
BBBB*..BBB
PPPP*.***B
******....
B**BB*....
B**BB**..*
***BB**..P
P**BBBB..P
Output:
Sector #1: contain 2 freedom fighter group(s) & 1 enemy group(s)
Sector #2: contain 3 freedom fighter group(s) & 3 enemy group(s)
Sector #3: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 5 group(s) are in fighting position.
I think this will remove all confusions.
Mahmud
10592(Freedom Fighter): WA
When I got WA for the first time in this problem, I visited the previous discussions on this one. Some tricky input-output were given there and my solution code was right for them. But I still can't understand what wrong is with my code. I couldn't find out the bug in my code though I tried couple of hours. Anyone can help me please? Or give some other tricky input-output? Here's my code:
Code: Select all
deleted later......
Last edited by Faisal_Bd on Sat Sep 04, 2004 10:45 am, edited 1 time in total.
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact:
Thanks a lot, Raiyan Kamal. I managed to handle the error and fixed the code and got AC .
The answers for your test cases follow:
PPP
BBB
PPP
In this case, total 2 groups are fighting according to the problem description and my code gives wrong solution(3 groups). However, I shall try to fix it.
Another point, it is stated:
The answers for your test cases follow:
- Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #2: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 0 group(s) are in fighting position.
Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
Total 0 group(s) are in fighting position.
Sector #1: contain 0 freedom fighter group(s) & 1 enemy group(s)
Total 0 group(s) are in fighting position.
Sector #1: contain 2 freedom fighter group(s) & 2 enemy group(s)
Total 4 group(s) are in fighting position.
Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
Total 2 group(s) are in fighting position.
Sector #1: contain 1 freedom fighter group(s) & 1 enemy group(s)
Total 2 group(s) are in fighting position.
Sector #1: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #2: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #3: contain 0 freedom fighter group(s) & 1 enemy group(s)
Sector #4: contain 1 freedom fighter group(s) & 0 enemy group(s)
Sector #5: contain 1 freedom fighter group(s) & 0 enemy group(s)
Total 0 group(s) are in fighting position.
PPP
BBB
PPP
In this case, total 2 groups are fighting according to the problem description and my code gives wrong solution(3 groups). However, I shall try to fix it.
Another point, it is stated:
Does it mean that there will not be any case given above? I don't think so.It is granted that a freedom fighter group can fight only one opponent group at a time.
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact:
Dear Faisal,
for the line
If you assume that a Freedom Fighter group can fight only one Enemy group at a time and vice versa, then there will be no cases like
PPP
BBB
PPP
then you can solve the problem easily ( like you have already done ). But, if that line in the statement bears some special meaning which we have failed to understand, ( i.e. Enemies can fight more than one Freedom Fighter groups simultaneously ) then that code will surely get rejected if they add any case like
BBB
PPP
BBB
and then rejudge it.
Anyways, since a lot of programmers got AC assuming the same, therefore, we can also feel safe to assume this.
for the line
I think it means that there will be no such cases where there is a Freedom Fighter group adjacent to more than on enemy groups. But what about enemy groups ? Can they fight more than one Freedom Fighter groups simultaneously ? Its confusing!!It is granted that a freedom fighter group can fight only one opponent group at a time.
If you assume that a Freedom Fighter group can fight only one Enemy group at a time and vice versa, then there will be no cases like
PPP
BBB
PPP
then you can solve the problem easily ( like you have already done ). But, if that line in the statement bears some special meaning which we have failed to understand, ( i.e. Enemies can fight more than one Freedom Fighter groups simultaneously ) then that code will surely get rejected if they add any case like
BBB
PPP
BBB
and then rejudge it.
Anyways, since a lot of programmers got AC assuming the same, therefore, we can also feel safe to assume this.
-
- Experienced poster
- Posts: 106
- Joined: Thu Jan 29, 2004 12:07 pm
- Location: Bangladesh
- Contact: