cousins/cousins_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to Count your Cousins
  8  * 
  9  * @author vanb
 10  */
 11 public class cousins_vanb
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15     
 16     /**
 17      * A Node of the tree.
 18      * records the level, the number of kids, and a link to the parent node.
 19      * 
 20      * @author vanb
 21      */
 22     public class Node
 23     {
 24         public int kids, grandkids;
 25         public Node parent;
 26        
 27         /**
 28          * Create a Node, specifying its parent.
 29          * @param parent The Parent of this Node
 30          */
 31         public Node( Node parent )
 32         {            
 33             // We don't know about any kids yet.
 34             kids = grandkids = 0;
 35             
 36             // This is pretty self-explanatory.
 37             this.parent = parent;
 38         }
 39     }
 40         
 41     /**
 42      * Driver.
 43      * @throws Exception
 44      */
 45     public void doit() throws Exception
 46     {
 47         sc = new Scanner( new File( "cousins.judge" ) );
 48         ps = new PrintStream( new FileOutputStream( "cousins.solution" ) );
 49         
 50         // We'll use this to match up node numbers with Node objects.
 51         HashMap<Integer,Node> nodes = new HashMap<Integer,Node>();
 52         Node tree[] = new Node[1000];
 53 
 54         for(;;)
 55         {
 56             int n = sc.nextInt();
 57             int k = sc.nextInt();
 58             if( n==0 ) break;
 59             
 60             // Start with a fresh tree
 61             Arrays.fill( tree, null );
 62             
 63             // The first one is the root.
 64             int root = sc.nextInt();
 65             tree[0] = new Node(null);
 66             nodes.clear();
 67             nodes.put( root, tree[0] );
 68             
 69             // The root is the first parent. We'll also need to know the last node number.
 70             int parent = -1;
 71             int last = -1;
 72             for( int i=1; i<n; i++ )
 73             {
 74                 // Get the next node number. If it's not sequential (i.e. one more than the last),
 75                 // then we've moved on to the next node as a parent.
 76                 int nodenum = sc.nextInt();
 77                 if( nodenum>last+1 ) ++parent;
 78                 
 79                 // Create the node, map its node number to it
 80                 tree[i] = new Node( tree[parent] );
 81                 nodes.put( nodenum, tree[i] );
 82                 
 83                 // The parent now has one more kid
 84                 tree[parent].kids++;
 85 
 86                 // And the grandparent has one more grandkid
 87                 if( tree[parent].parent!=null ) tree[parent].parent.grandkids++;
 88                                
 89                 // This is now the last node number
 90                 last = nodenum;
 91             }
 92             
 93             // Find the target node
 94             Node node = nodes.get( k );
 95             
 96             // if it isn't there, the judge data is bad!!
 97             if( node==null )
 98             {
 99                 System.err.println( "PANIC!! Node " + k + " isn't in the tree! " + nodes );
100             }
101             else if( node.parent==null || node.parent.parent==null )
102             {
103                 // Parent is null? Grandparent is null?
104                 // Then this is the root, or a child of the root, so it has no cousins.
105                 ps.println(0);
106             }
107             else 
108             {
109                 // The number of cousins is the number of nodes which share a grandparent, but not a parent.
110                 ps.println( node.parent.parent.grandkids - node.parent.kids );
111             }
112         }
113     }
114     
115     /**
116      * @param args
117      */
118     public static void main( String[] args ) throws Exception
119     {
120         new cousins_vanb().doit();
121         
122 //        PrintStream ps = new PrintStream( new FileOutputStream(  cousins.tmp  ) );
123 //        int tree[] = new int[1000];
124 //        
125 //        Random r = new Random();
126 //        int factor = r.nextInt(10)+2;
127 //        for( int k=0; k<1000; k++ )
128 //        {
129 //            int length = k+1;
130 //            tree[0] = r.nextInt(100) + 2;
131 //            tree[1] = tree[0] + r.nextInt(100)+ 2;
132 //            for( int i=2; i<length; i++ )
133 //            {
134 //                tree[i] = tree[i-1] + (r.nextInt( factor )==0 ? r.nextInt(100)+2 : 1);
135 //            }
136 //            
137 //            int target = tree[length==1 ? 0 : r.nextInt(length-1)+1];
138 //            
139 //            ps.println(    + length +     + target );
140 //            boolean first = true;
141 //            for( int i=0; i<length; i++ )
142 //            {
143 //                ps.print( (first?  :   ) + tree[i] );
144 //                first = false;
145 //            }
146 //            ps.println();
147 //        }
148     }   
149 }