Показать все сообщения Спрятать все сообщенияProgram t1156;
Const MaxN=100;
Type Info=array[1..MaxN]of integer;
Var Task :Info;
G :array[1..MaxN,1..MaxN]of byte;
N,M,i,j,k :integer;
t1,t2,c :integer;
k1,k2 :integer;
label er;
Procedure WriteNo;
begin
Writeln('IMPOSSIBLE');
Halt(0);
end;
Procedure WriteIt;
Var i :integer;
begin
for i:=1 to 2*N do
if Task[i]=1 then
write(i,' ');
writeln;
for i:=1 to 2*N do
if Task[i]=2 then
write(i,' ');
writeln;
Halt(0);
end;
Function Check2:boolean;
Var t1,t2,i :integer;
begin
t1:=0;t2:=0;
for i:=1 to 2*N do
if Task[i]=1 then t1:=t1+1;
for i:=1 to 2*N do
if Task[i]=2 then t2:=t2+1;
Check2:= t1=t2;
end;
Function Check:boolean;
Var t :integer;
begin
for t:=1 to 2*N do
if Task[t]>2 then begin
Check:=false;
exit;
end;
Check:=true;
end;
Procedure Rec;
var i,r :integer;
p :info;
t1,t2,k1,k2 :integer;
begin
if Check then
if Check2 then
WriteIt else
exit;
c:=c+2;
t1:=0;t2:=0;
for i:=1 to 2*N do
if Task[i]=1 then t1:=t1+1;
for i:=1 to 2*N do
if Task[i]=2 then t2:=t2+1;
k1:=0;k2:=0;
for i:=1 to 2*N do
if Task[i]=c then k1:=k1+1;
for i:=1 to 2*N do
if Task[i]=c+1 then k2:=k2+1;
if ( (t2>=t1)and(k1>=k2) ) or
( (t2<=t1)and(k1<=k2) ) then begin
p:=task;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=1;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=2;
Rec;
task:=p;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=2;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=1;
Rec;
end else begin
p:=task;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=2;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=1;
Rec;
task:=p;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=1;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=2;
Rec;
end;
c:=c-2;
end;
begin
for i:=1 to 100 do Task[i]:=-1;
Read(N,M);
FillChar(G,SizeOf(G),0);
for i:=1 to M do begin
read(t1,t2);
G[t1,t2]:=1;
G[t2,t1]:=1;
end;
Task[1]:=1;
c:=1;
for i:=1 to 2*N do begin
if task[i]=-1 then begin c:=c+2;task[i]:=c; end;
er:
for j:=i to 2*N do
if G[i,j]=1 then
if ((task[j]=task[i]+1)and(task[i] mod 2=1))or
((task[j]=task[i]-1)and(task[i] mod 2=0)) then begin
if (task[i]=task[j])and(task[j]<>-1) then WriteNo;
if task[j]=-1 then begin
task[j]:=task[i]+1;
if task[j] mod 2=1 then task[j]:=task[j]-2;
end else begin
task[i]:=task[j]+1;
if task[i] mod 2=1 then task[i]:=task[i]-2;
for k:=1 to j do
if G[i,k]=1 then
task[k]:=-1;
goto er;
end;
end;
end;
c:=1;
Rec;
WriteNo;
end. Try this test case:
2 3
1 2
1 3
1 4
The answer should be IMPOSSIBLE. My program:
Program t1156;
Const MaxN=100;
Type Info=array[1..MaxN]of integer;
Var Task :Info;
G :array[1..MaxN,1..MaxN]of byte;
N,M,i,j,k :integer;
t1,t2,c :integer;
k1,k2 :integer;
count :longint;
label er;
Procedure WriteNo;
begin
Writeln('IMPOSSIBLE');
Halt(0);
end;
Procedure WriteIt;
Var i :integer;
begin
for i:=1 to 2*N do
if Task[i]=1 then
write(i,' ');
writeln;
for i:=1 to 2*N do
if Task[i]=2 then
write(i,' ');
writeln;
Halt(0);
end;
Function Check2:boolean;
Var t1,t2,i :integer;
begin
t1:=0;t2:=0;
for i:=1 to 2*N do
if Task[i]=1 then t1:=t1+1;
for i:=1 to 2*N do
if Task[i]=2 then t2:=t2+1;
Check2:= t1=t2;
end;
Function Check:boolean;
Var t :integer;
begin
for t:=1 to 2*N do
if Task[t]>2 then begin
Check:=false;
exit;
end;
Check:=true;
end;
Procedure Rec;
var i,r :integer;
p :info;
t1,t2,k1,k2 :integer;
begin
count:=count+1;
if count>1000000 then WriteNo;
if Check then
if Check2 then
WriteIt else
exit;
c:=c+2;
t1:=0;t2:=0;
for i:=1 to 2*N do
if Task[i]=1 then t1:=t1+1;
for i:=1 to 2*N do
if Task[i]=2 then t2:=t2+1;
k1:=0;k2:=0;
for i:=1 to 2*N do
if Task[i]=c then k1:=k1+1;
for i:=1 to 2*N do
if Task[i]=c+1 then k2:=k2+1;
if ( (t2>=t1)and(k1>=k2) ) or
( (t2<=t1)and(k1<=k2) ) then begin
p:=task;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=1;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=2;
Rec;
task:=p;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=2;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=1;
Rec;
end else begin
p:=task;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=2;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=1;
Rec;
task:=p;
for i:=1 to 2*N do
if Task[i]=c then Task[i]:=1;
for i:=1 to 2*N do
if Task[i]=c+1 then Task[i]:=2;
Rec;
end;
c:=c-2;
end;
begin
for i:=1 to 100 do Task[i]:=-1;
Read(N,M);
FillChar(G,SizeOf(G),0);
for i:=1 to M do begin
read(t1,t2);
G[t1,t2]:=1;
G[t2,t1]:=1;
end;
Task[1]:=1;
c:=1;
for i:=1 to 2*N do begin
if task[i]=-1 then begin c:=c+2;task[i]:=c; end;
er:
for j:=i to 2*N do
if G[i,j]=1 then
if ((task[i]+1 div 2)<>(task[j]+1) div 2) then begin
if (task[i]=task[j])and(task[j]<>-1) then WriteNo;
if task[j]=-1 then begin
task[j]:=task[i]+1;
if task[j] mod 2=1 then task[j]:=task[j]-2;
end else begin
task[i]:=task[j]+1;
if task[i] mod 2=1 then task[i]:=task[i]-2;
for k:=1 to j do
if G[i,k]=1 then
task[k]:=-1;
goto er;
end;
end;
end;
c:=1;
count:=0;
Rec;
WriteNo;
end. Email me if you need explanation of the algorythm or the program
itself. Could you tell me some hints about your solution (here or my email)? i use it
but I still get WA My program can solve the test case corectly, but it gets wrong
answer. Below is my algo, can someone tell me why it is wrong?
First, treat the problem as a graph. Two nodes are connected if they
cannot be on the same day. Then, I "color" the nodes with either
black or white so that no two directly connected nodes have the same
color. If that is not possible then IMPOSSIBLE. Else I count the
number of problems in day 1 and make sure it is equal to n. If not
then IMPOSSIBLE, else I print the nodes.
What's the problem? First, I'd like to note that there may be several connectivity components in the input graph. If anything is still unclear, proceed reading further.
There is really _only one_ way to color the nodes of a _connected_ graph with two colors so that “no two directly connected nodes have the same color”. Don’t take this on trust, but prove it (-:
To proceed consider a connected graph. Take for example the graph that is built from the following input for timus1156 problem:
3 6
1 6
5 2
2 3
3 4
4 6
6 2
Any single note (we may choose it randomly, let it be node #6) will be painted in exactly one color, let’s paint it black. After we’ve done it, it becomes obvious, that all #6 neighbors (#1, #4 and #2) should be white. And all their neighbors (#3 and #5) will be black. In such a way, painting a certain node in a certain color unambiguously determines how the whole connectivity component of that node will be painted. If I had painted the initial node in the opposite color, I would have got just the inverted coloring (#6, #3 and #5 are white and #1, #2, #4 are black). If I had chosen another initial node, I would have got once again just one of the colorings mentioned above. (Try it for nodes #1, #3. See, what happens).
It is also possible, that there is no valid coloring. For example, it happens when there are cycles of odd length in the input graph. Consider the following input:
2 3
1 3
1 2
2 3
Of course, in this case the right output would be ‘IMPOSSIBLE’.
So, if there is only one connectivity component in a graph, there are two opposite ways to color that graph (they are indistinguishable in terms of right answer) or there is no valid coloring for that graph.
Consider the following input:
3 4
1 2
1 3
4 5
4 6
The corresponding graph consists of two connectivity components - (#1, #2, #3) vs. (#4, #5, #6). Please, recall, that there are two ways to color every component (2 black nodes and 1 white node and vice versa in this case), so, there are 2*2=4 ways to color this graph, two of them being valid solutions.
So, if there are Ncc connectivity components in the graph, then there are 2^Ncc ways to color its nodes in two colors so that “no two directly connected nodes have the same color”, only some of then (or none) having equal count of black & white vertices. Exhaustive search is not obligatory in this case … I used a kind of DP (dynamic programming) to find the optimal coloring or to make sure, that it doesn’t exist.
BTW, does anybody mind me explaining my solutions? |
