Thanks! it was matter of bad English for such an Iranian Boy... Can you help me a little bit more? which algorithm i should use? DFS and BFS dont help... Brute Force doesn`t seem beauty ;)! Please Help Me Best Aidin_n7@hotmail.com
This proof incomplete and doesn't shed light to the point. We should add next: if person Q on the left side have >=2 enemy on the left then he don't have more than 1 enemies in persons on the right because in other case he would have >=4 enemies.
It is clear that if proposed algorithm terminates then we have found a solution. But does it allways terminate? I will try to add my 5 cents by giving a short yet complete proof of termination.
Let us first introduce the decreasing measure M. We define M to be equal to the number of edges of the graph on the same(!) side. Algorithm terminates if measure decreases with each iteration of algorithm. Let us consider 3 possible situations:
1) We change side of a child with 3 enemies on his side. Then M decreases by 3. 2a) We change side of a child with 2 enemies on his side and 0 enemies on other side. Then measure decreases by 2. 2b) We change side of a child with 2 enemies on his side and 1 enemy on other side. Then M decreases by 2 and increases by 1. 3) If child has only one enemy on his side, then we do nothing.
According to described cases M will decrease after each iteration. Hence, algorithm terminates.
I call it adjusting... First put them all into Group A Then if there exits a person who have two enemies, throw them into another group. It can be proved that you have to do this operation only twice. (from Group A to Group B, and then from Group B to Group A)
As description of question mentioned, we need to output the smaller group of children, which fits the restrictions. However, for sample output, we can also put 5 [without any adversary] into abitrary group, so, the smallest group should not be 1,2,5,6, that's 1,2,6. Am I right? and my program could produce another seemingly meanful answer: 3,6,7[1,2,4,8,5 another group]. yeah, a little bit lost! could someone help me out? Thank a lot in advance! ^_^
why I got wa in test 3? var f,num:array[1..10000]of longint; a:array[1..10000,1..3]of longint; w,i,n,j:longint; procedure print(a:longint); var i,w:longint; b:array[1..10000]of longint; begin w:=0; fillchar(b,sizeof(b),0); for i:=1 to n do if f[i]=a then begin inc(w); b[w]:=i; end; writeln(w); if w<>0 then begin for i:=1 to w-1 do write(b[i],' '); writeln(b[w]); end; end; begin assign(input,'a.in'); reset(input); assign(output,'a.out'); rewrite(output); readln(n); for i:=1 to n do begin read(num[i]); for j:=1 to num[i] do read(a[i,j]); end; fillchar(f,sizeof(f),0); for i:=1 to n do if f[i]=0 then begin w:=0; for j:=1 to num[i] do if f[a[i,j]]=0 then inc(w); if w>1 then f[i]:=1; end; for i:=1 to n do begin w:=0; for j:=1 to num[i] do if f[i]=f[a[i,j]] then inc(w); if w>1 then begin writeln('NO SOLUTION'); close(input); close(output); halt; end; end; w:=0; for i:=1 to n do w:=w+f[i]; if w>n/2 then print(0) else if w<n/2 then print(1) else print(f); close(input); close(output); end.
Try this: 4 1 3 2 3 4 3 1 2 4 2 2 3 Your output: 2 2 3 This answer is wrong. "If the groups are of the same size then you are to describe the group that contains the child number one" So possible answer is: 2 1 4
When n is negative - what to output?? And most intersting what output when N = 0, I think it's one test when NO SOLUTION? because it says that that when two teams are equal by size - output where 1? but there both teams have 0 members - so what out? coz 1 appears nowhere