Aizu Online Judge 1221 Numoeba

■1221 Numoeba

制限時間・メモリ共に余裕があるので，あとは気合で書くだけ．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int k;  
17.  int m;  
18.  int mod=12345678;  
19.  boolean[] visited=new boolean[10000];  
20.   
21.  void run(){  
22.   for(;;){  
23.    k=sc.nextInt();  
24.    if(k==0){  
25.     break;  
26.    }  
27.    solve();  
28.   }  
29.  }  
30.   
31.  void solve(){  
32.   Cell leader=new Cell(k);  
33.   m=0;  
34.   int maxNum=1;  
35.   for(int k=1;; k++){  
36.    LinkedList<Cell> que=new LinkedList<Cell>();  
37.    que.offer(leader);  
38.    fill(visited, false);  
39.    visited[leader.v]=true;  
40.   
41.    for(; !que.isEmpty();){  
42.     Cell c=que.poll();  
43.     int n=c.n*3+1;  
44.     for(; n%2==0;){  
45.      n/=2;  
46.     }  
47.     n%=mod;  
48.     c.candidate=n>c.n&&(c.size()==0||(c.size()==1&&c!=leader));  
49.     c.n=n;  
50.     if(c.n==1){  
51.      if(c==leader){  
52.       println(k+" "+maxNum);  
53.       return;  
54.      }  
55.      Cell par=null;  
56.      for(Cell d : c){  
57.       if(visited[d.v]){  
58.        par=d;  
59.       }  
60.       d.remove(c);  
61.      }  
62.      c.remove(par);  
63.      if(c.size()==1){  
64.       Cell child=c.getFirst();  
65.       par.add(child);  
66.       child.add(par);  
67.       que.offer(child);  
68.       visited[child.v]=true;  
69.      }  
70.     }else{  
71.      for(Cell d : c){  
72.       if(!visited[d.v]){  
73.        que.offer(d);  
74.        visited[d.v]=true;  
75.       }  
76.      }  
77.     }  
78.    }  
79.    fill(visited, false);  
80.    Cell newLeader=new Cell(0);  
81.    boolean overlap=false;  
82.    int num=0;  
83.   
84.    que.offer(leader);  
85.    visited[leader.v]=true;  
86.    for(; !que.isEmpty();){  
87.     Cell c=que.poll();  
88.     num++;  
89.     for(Cell d : c){  
90.      if(!visited[d.v]){  
91.       que.offer(d);  
92.       visited[d.v]=true;  
93.      }  
94.     }  
95.     if(c.n>newLeader.n){  
96.      newLeader=c;  
97.      overlap=false;  
98.     }else if(c.n==newLeader.n){  
99.      overlap=true;  
100.     }  
101.     if(c.candidate&&((c.size()==1&&c!=leader)||c.size()==0)){  
102.      Cell d=new Cell(((c.n+1)/2)|1);  
103.      if(d.n!=1){  
104.       c.add(d);  
105.       d.add(c);  
106.       num++;  
107.      }  
108.     }  
109.    }  
110.   
111.    if(!overlap){  
112.     leader=newLeader;  
113.     Cell c=new Cell(((leader.n+1)/2-1)|1);  
114.     if(c.n!=1){  
115.      leader.add(c);  
116.      c.add(leader);  
117.      num++;  
118.     }  
119.    }  
120.    maxNum=max(maxNum, num);  
121.   }  
122.  }  
123.   
124.  void dfs(Cell leader){  
125.   fill(visited, false);  
126.   dfs(leader, "");  
127.  }  
128.   
129.  void dfs(Cell c, String tab){  
130.   debug(tab, c.n, c.size(), c.v);  
131.   visited[c.v]=true;  
132.   for(Cell d : c){  
133.    if(!visited[d.v]){  
134.     dfs(d, tab+"  ");  
135.    }  
136.   }  
137.  }  
138.   
139.  class Cell extends LinkedList<Cell>{  
140.   int n, v;  
141.   boolean candidate;  
142.   
143.   Cell(int n){  
144.    this.n=n;  
145.    this.v=m++;  
146.   }  
147.   
148.   @Override  
149.   public int hashCode(){  
150.    return v;  
151.   }  
152.   
153.   @Override  
154.   public boolean equals(Object o){  
155.    return hashCode()==((Cell)o).hashCode();  
156.   }  
157.  }  
158.   
159.  void debug(Object... os){  
160.   System.err.println(Arrays.deepToString(os));  
161.  }  
162.   
163.  void print(String s){  
164.   System.out.print(s);  
165.  }  
166.   
167.  void println(String s){  
168.   System.out.println(s);  
169.  }  
170.   
171.  public static void main(String[] args){  
172.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
173.   new Main().run();  
174.  }  
175. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int k;
 int m;
 int mod=12345678;
 boolean[] visited=new boolean[10000];

 void run(){
  for(;;){
   k=sc.nextInt();
   if(k==0){
    break;
   }
   solve();
  }
 }

 void solve(){
  Cell leader=new Cell(k);
  m=0;
  int maxNum=1;
  for(int k=1;; k++){
   LinkedList<Cell> que=new LinkedList<Cell>();
   que.offer(leader);
   fill(visited, false);
   visited[leader.v]=true;

   for(; !que.isEmpty();){
    Cell c=que.poll();
    int n=c.n*3+1;
    for(; n%2==0;){
     n/=2;
    }
    n%=mod;
    c.candidate=n>c.n&&(c.size()==0||(c.size()==1&&c!=leader));
    c.n=n;
    if(c.n==1){
     if(c==leader){
      println(k+" "+maxNum);
      return;
     }
     Cell par=null;
     for(Cell d : c){
      if(visited[d.v]){
       par=d;
      }
      d.remove(c);
     }
     c.remove(par);
     if(c.size()==1){
      Cell child=c.getFirst();
      par.add(child);
      child.add(par);
      que.offer(child);
      visited[child.v]=true;
     }
    }else{
     for(Cell d : c){
      if(!visited[d.v]){
       que.offer(d);
       visited[d.v]=true;
      }
     }
    }
   }
   fill(visited, false);
   Cell newLeader=new Cell(0);
   boolean overlap=false;
   int num=0;

   que.offer(leader);
   visited[leader.v]=true;
   for(; !que.isEmpty();){
    Cell c=que.poll();
    num++;
    for(Cell d : c){
     if(!visited[d.v]){
      que.offer(d);
      visited[d.v]=true;
     }
    }
    if(c.n>newLeader.n){
     newLeader=c;
     overlap=false;
    }else if(c.n==newLeader.n){
     overlap=true;
    }
    if(c.candidate&&((c.size()==1&&c!=leader)||c.size()==0)){
     Cell d=new Cell(((c.n+1)/2)|1);
     if(d.n!=1){
      c.add(d);
      d.add(c);
      num++;
     }
    }
   }

   if(!overlap){
    leader=newLeader;
    Cell c=new Cell(((leader.n+1)/2-1)|1);
    if(c.n!=1){
     leader.add(c);
     c.add(leader);
     num++;
    }
   }
   maxNum=max(maxNum, num);
  }
 }

 void dfs(Cell leader){
  fill(visited, false);
  dfs(leader, "");
 }

 void dfs(Cell c, String tab){
  debug(tab, c.n, c.size(), c.v);
  visited[c.v]=true;
  for(Cell d : c){
   if(!visited[d.v]){
    dfs(d, tab+"  ");
   }
  }
 }

 class Cell extends LinkedList<Cell>{
  int n, v;
  boolean candidate;

  Cell(int n){
   this.n=n;
   this.v=m++;
  }

  @Override
  public int hashCode(){
   return v;
  }

  @Override
  public boolean equals(Object o){
   return hashCode()==((Cell)o).hashCode();
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}