|
|
Notice, that +1 and -1 mean not victory and defeat states. INPUT 2 L 1 +1 OUTPUT +1 var f,q,be:array[0..1000] of integer; n,x,a,b,c:integer; m:char; begin {assign(input,'1282.txt'); reset(input); } readln(n); for x:=1 to n do be[x]:=-3; for x:=2 to n do begin read(m); if m='L' then begin readln(a,b); if be[a]=-3 then begin inc(c); q[c]:=a; be[a]:=-1; end; if b=-1 then be[a]:=1; if (b=0) and (be[a]<0) then be[a]:=0; end else readln(f[x]); end; b:=1; while q[b]<>1 do begin if be[f[q[b]]]<-2 then begin inc(c); q[c]:=f[q[b]]; be[f[q[b]]]:=-1; end; if be[q[b]]=-1 then be[f[q[b]]]:=1; if (be[q[b]]=0) and (be[f[q[b]]]<0) then be[f[q[b]]]:=0; inc(b); end; if be[1]=1 then writeln('+1') else writeln(be[1]); end. {be[n]==the best value it then player play best f[n]==the father of n be[n]=-3===>it hasn't been visited } Read these sentences carefully: The leaf nodes of the tree of this game may have values equal to one of three numbers: “+1” – victory of the first competitor, “–1” – victory of the second competitor, “0” – draw. For example, Input 3 L 1 +1 L 1 +1 Output +1 Input 3 L 1 +1 L 1 -1 Output +1 Input 3 L 1 -1 L 1 -1 Output -1 Hope it can help:) Edited by author 29.12.2015 22:25 What is on 18 test? Why do you think it is "almost solved"? A problem may have arbitrary number of tests (sometimes 200+), so WA #18 doesn't mean "almost solved", it means "not solved". I don't understand the 2nd sample test. Is a player go on the path from where the othe player reach? Or are the players move on different path? Each player starts from the point that the other player selects. Here's an explanation for the 2nd test 1 / \ 2 3 / \ / \ 4 5 6 7 - + + 0 If the first player chooses the 2 node, the second player will choose the 4th and win. If the first player chooses the 3 node, the second player will choose the 7th node (he prefers to draw than to loose) So, the player will choose the 3rd node, as he prefers drawing rather than loosing. Edited by author 22.06.2012 16:52 Hint for you : int travel(int player,int node) { int value; if(isLeaf(node)) return getValue(node); // If the first player is at this node, he prefer getting the maximal value among -1, 0 and +1. if(player == 0) { value = MinValue(); for(int a=0;a<numberOfChild(node);a++) { int v = travel((player+1)%2,getChild(node,a)); if(value < v) value = v; } } // Get the minimal value. else { value = MaxValue(); for(int a=0;a<numberOfChild(node);a++) { int v = travel((player+1)%2,getChild(node,a)); if(value > v) value = v; } } return value; } Edited by author 24.02.2011 15:14 Edited by author 24.11.2010 23:13 I don't understand this problem. As I think, the third sample is the tree from the picture. But I can not understand why, for example, 'the number of the ancestor of this node' for the node #18 is 12? What does it mean, 'the number of the ancestor of this node'? THank you. As you can see in a picture, the node #18 connected with the #12 node, and - #18 is a child for #12; - #12 is a ancestor, farther (mother) of #18. In phrase "the number of the ancestor of this node" the word "number" should be understood ad index (the index of the node, which is an ancestor for target node). I get WA 10 and I'm really confused why??? I use simply algo: BFS of the tree and I make simulation of the right strategy. Can you help me? Can you give me some test data? Or a hint? In 1282 the image is empty (X). |
|
|