Advertisement
Guest User

googol

a guest
Apr 7th, 2015
468
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.94 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5. public class googol{
  6.     static Map<BigInteger,BigInteger> id = new HashMap<BigInteger, BigInteger>();
  7.     static BigInteger two = new BigInteger("2");
  8.     static BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
  9.     public static void main (String [] args) throws IOException {
  10.         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("googol.out")));
  11.         String trash;
  12.         int count1 = 1;
  13.         int count2 = 1;
  14.         System.out.println(1);
  15.         id.put(new BigInteger("1"), new BigInteger("1"));
  16.         StringTokenizer st0 = new StringTokenizer(f.readLine());
  17.         id.put(new BigInteger("2"),new BigInteger(st0.nextToken()));
  18.         id.put(new BigInteger("3"), new BigInteger(st0.nextToken()));
  19.         BigInteger node = new BigInteger("1");
  20.         System.out.println(1);
  21.         while(true){
  22.             StringTokenizer st1 = new StringTokenizer(f.readLine());
  23.             trash = st1.nextToken();
  24.             id.put(node.multiply(two),new BigInteger(trash));
  25.             trash=st1.nextToken();
  26.             id.put(node.multiply(two).add(BigInteger.ONE),new BigInteger(trash));
  27.             if(trash.equals("0")){
  28.                 break;
  29.             }
  30.             node=node.multiply(two);
  31.             count1++;
  32.             System.out.println(id.get(node));
  33.         }
  34.         System.out.println(1);
  35.         BigInteger node2 = new BigInteger("1");
  36.         while(true){
  37.             StringTokenizer st2 = new StringTokenizer(f.readLine());
  38.             trash=st2.nextToken();
  39.             id.put(node2.multiply(two),new BigInteger(trash));
  40.             trash = st2.nextToken();
  41.             id.put(node2.multiply(two).add(BigInteger.ONE),new BigInteger(trash));
  42.             if(trash.equals("0")){
  43.                 break;
  44.             }
  45.             node2=node2.multiply(two).add(BigInteger.ONE);
  46.             count2++;
  47.             System.out.println(trash);
  48.         }
  49.         if(count1 ==count2){
  50.             BigInteger answer = BigInteger.ZERO;
  51.             for(int i = 0;i<count1;i++){
  52.                 answer=answer.multiply(two).add(BigInteger.ONE);
  53.             }
  54.             System.out.println("Answer " + answer);
  55.         }
  56.         else{
  57.             BigInteger search = node;
  58.             BigInteger power = BigInteger.ONE;
  59.             for(int i = 1;i<count1;i++){
  60.                 if(id.get(search.add(power))==null){
  61.                     Queue<BigInteger> fat = new LinkedList<BigInteger>();
  62.                     BigInteger bad = search.add(power);
  63.                     while(id.get(bad)==null){
  64.                         fat.add(bad.mod(two));
  65.                         bad=bad.divide(two);
  66.                     }
  67.                     while(fat.size()>0){
  68.                         System.out.println(id.get(bad));
  69.                         StringTokenizer st7 = new StringTokenizer(f.readLine());
  70.                         id.put(bad.multiply(two),new BigInteger(st7.nextToken()));
  71.                         id.put(bad.multiply(two).add(BigInteger.ONE),new BigInteger(st7.nextToken()));
  72.                         bad=bad.multiply(two).add(fat.poll());
  73.                     }
  74.                 }
  75.                 if(!id.get(search.add(power)).equals(new BigInteger("0"))){
  76.                     search=search.add(power);
  77.                 }
  78.                 power=power.multiply(two);
  79.             }
  80.             BigInteger answer = BigInteger.ONE;
  81.             for(int i = 1;i<count1;i++){
  82.                 answer=answer.multiply(two).add(search.mod(two));
  83.                 search=search.divide(two);
  84.             }
  85.             System.out.println("Answer " + answer);
  86.         }
  87.         System.out.close();
  88.         System.exit(0);
  89.     }
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement