今月の〇〇(2011年4月)

■Aizu Online Judge

Solved:254/46th
Rating:203.75/50th
Ratingは目標通り200に到達しましたが，そのせいでSolvedの順位が下がってしまいました．5月は，Solvedの順位を30位以上，願わくば20位以上にしたいです．

■TopCoder/Codeforces

Codeforcesは，一旦Div.2に落ちたものの，再びDiv.1に復帰しました．
TopCoderは，Rating微増．

Aizu Online Judge 1202 Mobile Phone Coverage

■1202 Mobile Phone Coverage

面倒な問題．下の画像のような感じに分割した．区間をマージする処理が面倒だった．

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 n;  
17.  R[] rs;  
18.  int caze;  
19.   
20.  void run(){  
21.   for(caze=1;; caze++){  
22.    n=sc.nextInt();  
23.    if(n==0){  
24.     break;  
25.    }  
26.    rs=new R[n];  
27.    for(int i=0; i<n; i++){  
28.     double x=sc.nextDouble();  
29.     double y=sc.nextDouble();  
30.     double r=sc.nextDouble();  
31.     rs[i]=new R(x-r, y-r, x+r, y+r);  
32.    }  
33.    solve();  
34.   }  
35.  }  
36.   
37.  void solve(){  
38.   TreeSet<Double> setX=new TreeSet<Double>();  
39.   for(int i=0; i<n; i++){  
40.    setX.add(rs[i].x1);  
41.    setX.add(rs[i].x2);  
42.   }  
43.   Double[] xs=setX.toArray(new Double[0]);  
44.   sort(xs);  
45.   int m=xs.length;  
46.   @SuppressWarnings("unchecked")  
47.   TreeSet<R>[] setR=new TreeSet[m];  
48.   for(int i=0; i<m; i++){  
49.    setR[i]=new TreeSet<R>();  
50.   }  
51.   
52.   for(int j=0; j<m-1; j++){  
53.    for(int i=0; i<n; i++){  
54.     if(rs[i].x1<xs[j]+EPS&&xs[j]+EPS<rs[i].x2){  
55.      setR[j].add(rs[i]);  
56.     }  
57.    }  
58.   }  
59.   
60.   double sum=0;  
61.   for(int k=0; k<m-1; k++){  
62.    LinkedList<Double> seg=new LinkedList<Double>();  
63.    for(R r : setR[k]){  
64.     if(abs(r.y1-r.y2)<EPS){  
65.      continue;  
66.     }  
67.     int i=seg.size(), j=seg.size();  
68.     for(int p=seg.size()-1; p>=0; p--){  
69.      double y=seg.get(p);  
70.      if(y+EPS>r.y2){  
71.       j=p;  
72.      }  
73.      if(y+EPS>r.y1){  
74.       i=p;  
75.      }  
76.     }  
77.     for(int p=i; p<j; p++){  
78.      seg.remove(i);  
79.     }  
80.     if(j%2==0){  
81.      seg.add(i, r.y2);  
82.     }  
83.     if(i%2==0){  
84.      seg.add(i, r.y1);  
85.     }  
86.    }  
87.    double len=0;  
88.    for(int i=0; i<seg.size(); i+=2){  
89.     len+=seg.get(i+1)-seg.get(i);  
90.    }  
91.    sum+=len*(xs[k+1]-xs[k]);  
92.   }  
93.   println(String.format("%d %.2f", caze, sum+EPS));  
94.  }  
95.   
96.  class R implements Comparable<R>{  
97.   double x1, y1, x2, y2;  
98.   
99.   R(double x1, double y1, double x2, double y2){  
100.    this.x1=x1;  
101.    this.y1=y1;  
102.    this.x2=x2;  
103.    this.y2=y2;  
104.   }  
105.   
106.   @Override  
107.   public int compareTo(R arg0){  
108.    if(y1-y2+EPS<0){  
109.     return -1;  
110.    }else if(y1-y2>0+EPS){  
111.     return 1;  
112.    }else if(x1-x2+EPS<0){  
113.     return -1;  
114.    }else if(x1-x2>0+EPS){  
115.     return 1;  
116.    }else{  
117.     return 0;  
118.    }  
119.   }  
120.  }  
121.   
122.  void debug(Object... os){  
123.   // System.err.println(Arrays.deepToString(os));  
124.  }  
125.   
126.  void print(String s){  
127.   System.out.print(s);  
128.  }  
129.   
130.  void println(String s){  
131.   System.out.println(s);  
132.  }  
133.   
134.  public static void main(String[] args){  
135.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
136.   new Main().run();  
137.  }  
138. }  

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 n;
 R[] rs;
 int caze;

 void run(){
  for(caze=1;; caze++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   rs=new R[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double r=sc.nextDouble();
    rs[i]=new R(x-r, y-r, x+r, y+r);
   }
   solve();
  }
 }

 void solve(){
  TreeSet<Double> setX=new TreeSet<Double>();
  for(int i=0; i<n; i++){
   setX.add(rs[i].x1);
   setX.add(rs[i].x2);
  }
  Double[] xs=setX.toArray(new Double[0]);
  sort(xs);
  int m=xs.length;
  @SuppressWarnings("unchecked")
  TreeSet<R>[] setR=new TreeSet[m];
  for(int i=0; i<m; i++){
   setR[i]=new TreeSet<R>();
  }

  for(int j=0; j<m-1; j++){
   for(int i=0; i<n; i++){
    if(rs[i].x1<xs[j]+EPS&&xs[j]+EPS<rs[i].x2){
     setR[j].add(rs[i]);
    }
   }
  }

  double sum=0;
  for(int k=0; k<m-1; k++){
   LinkedList<Double> seg=new LinkedList<Double>();
   for(R r : setR[k]){
    if(abs(r.y1-r.y2)<EPS){
     continue;
    }
    int i=seg.size(), j=seg.size();
    for(int p=seg.size()-1; p>=0; p--){
     double y=seg.get(p);
     if(y+EPS>r.y2){
      j=p;
     }
     if(y+EPS>r.y1){
      i=p;
     }
    }
    for(int p=i; p<j; p++){
     seg.remove(i);
    }
    if(j%2==0){
     seg.add(i, r.y2);
    }
    if(i%2==0){
     seg.add(i, r.y1);
    }
   }
   double len=0;
   for(int i=0; i<seg.size(); i+=2){
    len+=seg.get(i+1)-seg.get(i);
   }
   sum+=len*(xs[k+1]-xs[k]);
  }
  println(String.format("%d %.2f", caze, sum+EPS));
 }

 class R implements Comparable<R>{
  double x1, y1, x2, y2;

  R(double x1, double y1, double x2, double y2){
   this.x1=x1;
   this.y1=y1;
   this.x2=x2;
   this.y2=y2;
  }

  @Override
  public int compareTo(R arg0){
   if(y1-y2+EPS<0){
    return -1;
   }else if(y1-y2>0+EPS){
    return 1;
   }else if(x1-x2+EPS<0){
    return -1;
   }else if(x1-x2>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }

 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();
 }
}

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();
 }
}

Aizu Online Judge 1215 Co-occurrence Search

■1215 Co-occurrence Search

しゃくとり法で解くことが出来る．入力がややこしく，無限ループによるTLEを連発してしまった．

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.  char[] s, key;  
17.   
18.  void run(){  
19.   for(;;){  
20.    StringBuffer lines=new StringBuffer();  
21.    for(;;){  
22.     String line=sc.nextLine();  
23.     if(line.equals("")){  
24.      break;  
25.     }  
26.     lines.append(line);  
27.    }  
28.    s=lines.toString().toCharArray();  
29.    key=sc.nextLine().toCharArray();  
30.    solve();  
31.    if(sc.hasNext()){  
32.     sc.nextLine();  
33.    }else{  
34.     break;  
35.    }  
36.   }  
37.   System.out.flush();  
38.  }  
39.   
40.  void solve(){  
41.   int i=0, j=0;  
42.   int num=0;  
43.   int n=s.length;  
44.   
45.   int min=INF;  
46.   int cMin=0, iMin=0, jMin=0;  
47.   
48.   int nKey=0;  
49.   boolean[] isKey=new boolean[256];  
50.   for(char c : key){  
51.    isKey[c]=true;  
52.   }  
53.   for(boolean b : isKey){  
54.    nKey+=b?1:0;  
55.   }  
56.   int[] count=new int[256];  
57.   
58.   for(;;){  
59.    for(; j<n&&num<nKey; j++){  
60.     if(isKey[s[j]]&&count[s[j]]++==0){  
61.      num++;  
62.     }  
63.    }  
64.   
65.    if(num<nKey){  
66.     break;  
67.    }  
68.   
69.    if(j-i<min){  
70.     iMin=i;  
71.     jMin=j;  
72.     min=j-i;  
73.     cMin=1;  
74.    }else if(j-i==min){  
75.     cMin++;  
76.    }  
77.   
78.    if(isKey[s[i]]&&--count[s[i]]==0){  
79.     num--;  
80.    }  
81.    i++;  
82.   }  
83.   
84.   println(cMin+"\n");  
85.   if(cMin>0){  
86.    String ans=new String(s, iMin, jMin-iMin);  
87.    for(int k=0; k<(ans.length()-1)/72+1; k++){  
88.     println(ans.substring(k*72, min((k+1)*72, ans.length())));  
89.    }  
90.    println("");  
91.   }  
92.  }  
93.   
94.  void debug(Object... os){  
95.   System.err.println(Arrays.deepToString(os));  
96.  }  
97.   
98.  void print(String s){  
99.   System.out.print(s);  
100.  }  
101.   
102.  void println(String s){  
103.   System.out.println(s);  
104.  }  
105.   
106.  public static void main(String[] args){  
107.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
108.   new Main().run();  
109.  }  
110. }  

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;

 char[] s, key;

 void run(){
  for(;;){
   StringBuffer lines=new StringBuffer();
   for(;;){
    String line=sc.nextLine();
    if(line.equals("")){
     break;
    }
    lines.append(line);
   }
   s=lines.toString().toCharArray();
   key=sc.nextLine().toCharArray();
   solve();
   if(sc.hasNext()){
    sc.nextLine();
   }else{
    break;
   }
  }
  System.out.flush();
 }

 void solve(){
  int i=0, j=0;
  int num=0;
  int n=s.length;

  int min=INF;
  int cMin=0, iMin=0, jMin=0;

  int nKey=0;
  boolean[] isKey=new boolean[256];
  for(char c : key){
   isKey[c]=true;
  }
  for(boolean b : isKey){
   nKey+=b?1:0;
  }
  int[] count=new int[256];

  for(;;){
   for(; j<n&&num<nKey; j++){
    if(isKey[s[j]]&&count[s[j]]++==0){
     num++;
    }
   }

   if(num<nKey){
    break;
   }

   if(j-i<min){
    iMin=i;
    jMin=j;
    min=j-i;
    cMin=1;
   }else if(j-i==min){
    cMin++;
   }

   if(isKey[s[i]]&&--count[s[i]]==0){
    num--;
   }
   i++;
  }

  println(cMin+"\n");
  if(cMin>0){
   String ans=new String(s, iMin, jMin-iMin);
   for(int k=0; k<(ans.length()-1)/72+1; k++){
    println(ans.substring(k*72, min((k+1)*72, ans.length())));
   }
   println("");
  }
 }

 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();
 }
}

Aizu Online Judge 1226 Fishnet

■1226 Fishnet

全通り試す．面積はヘロンの公式を使えば簡単．

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 n;  
17.  P[] a, b, c, d;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    if(n==0){  
23.     break;  
24.    }  
25.    n+=2;  
26.    a=new P[n];  
27.    b=new P[n];  
28.    c=new P[n];  
29.    d=new P[n];  
30.    a[0]=new P(0, 0);  
31.    b[0]=new P(0, 1);  
32.    c[0]=new P(0, 0);  
33.    d[0]=new P(1, 0);  
34.    for(int i=1; i<n-1; i++)  
35.     a[i]=new P(sc.nextDouble(), 0);  
36.    for(int i=1; i<n-1; i++)  
37.     b[i]=new P(sc.nextDouble(), 1);  
38.    for(int i=1; i<n-1; i++)  
39.     c[i]=new P(0, sc.nextDouble());  
40.    for(int i=1; i<n-1; i++)  
41.     d[i]=new P(1, sc.nextDouble());  
42.    a[n-1]=new P(1, 0);  
43.    b[n-1]=new P(1, 1);  
44.    c[n-1]=new P(0, 1);  
45.    d[n-1]=new P(1, 1);  
46.    solve();  
47.   }  
48.  }  
49.   
50.  void solve(){  
51.   double ans=0;  
52.   for(int j=0; j<n-1; j++){  
53.    for(int i=0; i<n-1; i++){  
54.     P p1=isLL(a[i], b[i], c[j], d[j]);  
55.     P p2=isLL(a[i+1], b[i+1], c[j], d[j]);  
56.     P p3=isLL(a[i+1], b[i+1], c[j+1], d[j+1]);  
57.     P p4=isLL(a[i], b[i], c[j+1], d[j+1]);  
58.     ans=max(ans, area(p1, p2, p3)+area(p3, p4, p1));  
59.    }  
60.   }  
61.   println(String.format("%.6f", ans+EPS));  
62.  }  
63.   
64.  double area(P p1, P p2, P p3){  
65.   double a=p1.sub(p2).abs();  
66.   double b=p2.sub(p3).abs();  
67.   double c=p3.sub(p1).abs();  
68.   double s=(a+b+c)/2;  
69.   return Math.sqrt(s*(s-a)*(s-b)*(s-c));  
70.  }  
71.   
72.  // 直線と直線の交点  
73.  P isLL(P p1, P p2, P q1, P q2){  
74.   double d=q2.sub(q1).det(p2.sub(p1));  
75.   if(abs(d)<EPS)  
76.    return null;  
77.   return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));  
78.  }  
79.   
80.  class P{  
81.   double x, y;  
82.   
83.   P(){  
84.    this(0, 0);  
85.   }  
86.   
87.   P(double x, double y){  
88.    this.x=x;  
89.    this.y=y;  
90.   }  
91.   
92.   P add(P p){  
93.    return new P(x+p.x, y+p.y);  
94.   }  
95.   
96.   P sub(P p){  
97.    return new P(x-p.x, y-p.y);  
98.   }  
99.   
100.   P mul(double m){  
101.    return new P(x*m, y*m);  
102.   }  
103.   
104.   P div(double d){  
105.    return new P(x/d, y/d);  
106.   }  
107.   
108.   double abs(){  
109.    return Math.sqrt(abs2());  
110.   }  
111.   
112.   double abs2(){  
113.    return x*x+y*y;  
114.   }  
115.   
116.   double arg(){  
117.    return Math.atan2(y, x);  
118.   }  
119.   
120.   // inner product  
121.   double dot(P p){  
122.    return x*p.x+y*p.y;  
123.   }  
124.   
125.   // outer product  
126.   double det(P p){  
127.    return x*p.y-y*p.x;  
128.   }  
129.   
130.   P rot90(){  
131.    return new P(-y, x);  
132.   }  
133.   
134.   // conjugation  
135.   P conj(){  
136.    return new P(x, -y);  
137.   }  
138.   
139.   @Override  
140.   public String toString(){  
141.    return "("+x+", "+y+")";  
142.   }  
143.  }  
144.   
145.  void debug(Object... os){  
146.   System.err.println(Arrays.deepToString(os));  
147.  }  
148.   
149.  void print(String s){  
150.   System.out.print(s);  
151.  }  
152.   
153.  void println(String s){  
154.   System.out.println(s);  
155.  }  
156.   
157.  public static void main(String[] args){  
158.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
159.   new Main().run();  
160.  }  
161. }  

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 n;
 P[] a, b, c, d;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   n+=2;
   a=new P[n];
   b=new P[n];
   c=new P[n];
   d=new P[n];
   a[0]=new P(0, 0);
   b[0]=new P(0, 1);
   c[0]=new P(0, 0);
   d[0]=new P(1, 0);
   for(int i=1; i<n-1; i++)
    a[i]=new P(sc.nextDouble(), 0);
   for(int i=1; i<n-1; i++)
    b[i]=new P(sc.nextDouble(), 1);
   for(int i=1; i<n-1; i++)
    c[i]=new P(0, sc.nextDouble());
   for(int i=1; i<n-1; i++)
    d[i]=new P(1, sc.nextDouble());
   a[n-1]=new P(1, 0);
   b[n-1]=new P(1, 1);
   c[n-1]=new P(0, 1);
   d[n-1]=new P(1, 1);
   solve();
  }
 }

 void solve(){
  double ans=0;
  for(int j=0; j<n-1; j++){
   for(int i=0; i<n-1; i++){
    P p1=isLL(a[i], b[i], c[j], d[j]);
    P p2=isLL(a[i+1], b[i+1], c[j], d[j]);
    P p3=isLL(a[i+1], b[i+1], c[j+1], d[j+1]);
    P p4=isLL(a[i], b[i], c[j+1], d[j+1]);
    ans=max(ans, area(p1, p2, p3)+area(p3, p4, p1));
   }
  }
  println(String.format("%.6f", ans+EPS));
 }

 double area(P p1, P p2, P p3){
  double a=p1.sub(p2).abs();
  double b=p2.sub(p3).abs();
  double c=p3.sub(p1).abs();
  double s=(a+b+c)/2;
  return Math.sqrt(s*(s-a)*(s-b)*(s-c));
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class P{
  double x, y;

  P(){
   this(0, 0);
  }

  P(double x, double y){
   this.x=x;
   this.y=y;
  }

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }

  @Override
  public String toString(){
   return "("+x+", "+y+")";
  }
 }

 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();
 }
}

Aizu Online Judge 1217 Family Tree

■ 1217 Family Tree

入力の解析が少し面倒．クエリに対する判定は，ある人の親さえ分かれば非常に簡単に出来る．
下記のコードではchildrenも記録していたけど全く必要なかった．

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 n, m;  
17.  HashMap<String, String> parent;  
18.  HashMap<String, LinkedList<String>> children;  
19.   
20.  void run(){  
21.   for(;;){  
22.    n=sc.nextInt();  
23.    m=sc.nextInt();  
24.    if((n|m)==0){  
25.     break;  
26.    }  
27.    parent=new HashMap<String, String>();  
28.    children=new HashMap<String, LinkedList<String>>();  
29.    sc.nextLine();  
30.    String p="", r=""; // 親, 1つ前  
31.    children.put(p, new LinkedList<String>());  
32.    int x=-1;  
33.    for(int j=0; j<n; j++){  
34.     String s=sc.nextLine();  
35.     int y=s.length()-s.replaceAll(" ", "").length();  
36.     s=s.replaceAll(" ", "");  
37.     // debug(s, r, p);  
38.     if(y>x){  
39.      p=r;  
40.     }else if(y<x){  
41.      for(int i=y; i<x; i++){  
42.       p=parent.get(p);  
43.      }  
44.     }  
45.     parent.put(s, p);  
46.     children.get(p).add(s);  
47.     children.put(s, new LinkedList<String>());  
48.     x=y;  
49.     r=s;  
50.    }  
51.    // dfs("", "");  
52.    for(int i=0; i<m; i++){  
53.     String s=sc.next();  
54.     sc.next();  
55.     sc.next();  
56.     char c=sc.next().charAt(0);  
57.     sc.next();  
58.     String t=sc.next();  
59.     t=t.substring(0, t.length()-1);  
60.     boolean f=false;  
61.     switch(c){  
62.     case 'c':  
63.      f=parent.containsKey(s)&&parent.get(s).equals(t);  
64.      break;  
65.     case 'p':  
66.      f=parent.containsKey(t)&&parent.get(t).equals(s);  
67.      break;  
68.     case 's':  
69.      f=parent.containsKey(s)&&parent.containsKey(t)  
70.        &&parent.get(s).equals(parent.get(t));  
71.      break;  
72.     case 'd':  
73.      for(s=parent.get(s); s!=null; s=parent.get(s)){  
74.       f|=s.equals(t);  
75.      }  
76.      break;  
77.     case 'a':  
78.      for(t=parent.get(t); t!=null; t=parent.get(t)){  
79.       f|=t.equals(s);  
80.      }  
81.      break;  
82.     }  
83.     println(f?"True":"False");  
84.    }  
85.    println("");  
86.   }  
87.  }  
88.   
89.  void dfs(String s, String tab){  
90.   for(String t : children.get(s)){  
91.    debug(tab, t, parent.get(t));  
92.    dfs(t, tab+"\t");  
93.   }  
94.  }  
95.   
96.  void debug(Object... os){  
97.   // System.err.println(Arrays.deepToString(os));  
98.  }  
99.   
100.  void print(String s){  
101.   System.out.print(s);  
102.  }  
103.   
104.  void println(String s){  
105.   System.out.println(s);  
106.  }  
107.   
108.  public static void main(String[] args){  
109.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
110.   new Main().run();  
111.  }  
112. }  

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 n, m;
 HashMap<String, String> parent;
 HashMap<String, LinkedList<String>> children;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   parent=new HashMap<String, String>();
   children=new HashMap<String, LinkedList<String>>();
   sc.nextLine();
   String p="", r=""; // 親, 1つ前
   children.put(p, new LinkedList<String>());
   int x=-1;
   for(int j=0; j<n; j++){
    String s=sc.nextLine();
    int y=s.length()-s.replaceAll(" ", "").length();
    s=s.replaceAll(" ", "");
    // debug(s, r, p);
    if(y>x){
     p=r;
    }else if(y<x){
     for(int i=y; i<x; i++){
      p=parent.get(p);
     }
    }
    parent.put(s, p);
    children.get(p).add(s);
    children.put(s, new LinkedList<String>());
    x=y;
    r=s;
   }
   // dfs("", "");
   for(int i=0; i<m; i++){
    String s=sc.next();
    sc.next();
    sc.next();
    char c=sc.next().charAt(0);
    sc.next();
    String t=sc.next();
    t=t.substring(0, t.length()-1);
    boolean f=false;
    switch(c){
    case 'c':
     f=parent.containsKey(s)&&parent.get(s).equals(t);
     break;
    case 'p':
     f=parent.containsKey(t)&&parent.get(t).equals(s);
     break;
    case 's':
     f=parent.containsKey(s)&&parent.containsKey(t)
       &&parent.get(s).equals(parent.get(t));
     break;
    case 'd':
     for(s=parent.get(s); s!=null; s=parent.get(s)){
      f|=s.equals(t);
     }
     break;
    case 'a':
     for(t=parent.get(t); t!=null; t=parent.get(t)){
      f|=t.equals(s);
     }
     break;
    }
    println(f?"True":"False");
   }
   println("");
  }
 }

 void dfs(String s, String tab){
  for(String t : children.get(s)){
   debug(tab, t, parent.get(t));
   dfs(t, tab+"\t");
  }
 }

 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();
 }
}

Codeforces Beta Round #69 (Div. 2 Only)

Codeforces Beta Round #69 (Div. 2 Only)

Div. 1復帰が目標でした．

A. Panoramixs Prediction

値が小さいので愚直に一つずつ試行．

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 A{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int m, n;  
16.   
17.  void run(){  
18.   m=sc.nextInt();  
19.   n=sc.nextInt();  
20.   boolean f=true;  
21.   for(int i=m+1; i<n; i++){  
22.    f&=!isP(i);  
23.   }  
24.   f&=isP(n);  
25.   println(f?"YES":"NO");  
26.  }  
27.   
28.  boolean isP(int n){  
29.   for(int i=2; i*i<=n; i++){  
30.    if(n%i==0){  
31.     return false;  
32.    }  
33.   }  
34.   return n!=1;  
35.  }  
36.   
37.  void println(String s){  
38.   System.out.println(s);  
39.  }  
40.   
41.  void print(String s){  
42.   System.out.print(s);  
43.  }  
44.   
45.  void debug(Object... os){  
46.   System.err.println(Arrays.deepToString(os));  
47.  }  
48.   
49.  public static void main(String[] args){  
50.   new A().run();  
51.  }  
52. }  

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

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

public class A{
 Scanner sc=new Scanner(System.in);

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

 int m, n;

 void run(){
  m=sc.nextInt();
  n=sc.nextInt();
  boolean f=true;
  for(int i=m+1; i<n; i++){
   f&=!isP(i);
  }
  f&=isP(n);
  println(f?"YES":"NO");
 }

 boolean isP(int n){
  for(int i=2; i*i<=n; i++){
   if(n%i==0){
    return false;
   }
  }
  return n!=1;
 }

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

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

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

 public static void main(String[] args){
  new A().run();
 }
}

B. Depression

%12を忘れないように気をつけるだけ．

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 B{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  void run(){  
16.   String[] ss=sc.next().split(":");  
17.   double h=Integer.parseInt(ss[0]);  
18.   double m=Integer.parseInt(ss[1]);  
19.   h=(h%12)/12.0*360;  
20.   m=m/60.0*360;  
21.   h=(h+m/12)%360;  
22.   println(h+" "+m);  
23.  }  
24.   
25.  void println(String s){  
26.   System.out.println(s);  
27.  }  
28.   
29.  void print(String s){  
30.   System.out.print(s);  
31.  }  
32.   
33.  void debug(Object... os){  
34.   System.err.println(Arrays.deepToString(os));  
35.  }  
36.   
37.  public static void main(String[] args){  
38.   new B().run();  
39.  }  
40. }  

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

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

public class B{
 Scanner sc=new Scanner(System.in);

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

 void run(){
  String[] ss=sc.next().split(":");
  double h=Integer.parseInt(ss[0]);
  double m=Integer.parseInt(ss[1]);
  h=(h%12)/12.0*360;
  m=m/60.0*360;
  h=(h+m/12)%360;
  println(h+" "+m);
 }

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

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

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

 public static void main(String[] args){
  new B().run();
 }
}

C. Heroes

全探索で解くことが出来るが，ちょっとしたミスをしたためSystem Test落ち．下は修正版．

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 C{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int n, a, b, c;  
16.  int[] p, q;  
17.  HashMap<String, Integer> map;  
18.   
19.  void run(){  
20.   int m=7;  
21.   
22.   map=new HashMap<String, Integer>();  
23.   map.put("Anka", 0);  
24.   map.put("Chapay", 1);  
25.   map.put("Cleo", 2);  
26.   map.put("Troll", 3);  
27.   map.put("Dracul", 4);  
28.   map.put("Snowy", 5);  
29.   map.put("Hexadecimal", 6);  
30.   
31.   n=sc.nextInt();  
32.   p=new int[n];  
33.   q=new int[n];  
34.   for(int i=0; i<n; i++){  
35.    p[i]=map.get(sc.next());  
36.    sc.next();  
37.    q[i]=map.get(sc.next());  
38.   }  
39.   a=sc.nextInt();  
40.   b=sc.nextInt();  
41.   c=sc.nextInt();  
42.   
43.   long dmin=1L<<32;  
44.   int lmax=0;  
45.   for(int k=1; k<1<<m; k++){  
46.    for(int j=1; j<1<<m; j++){  
47.     int i=((1<<m)-1)&~(k^j);  
48.     if((k^j)==(k|j)&&i>0){  
49.      int x=a/Integer.bitCount(i);  
50.      int y=b/Integer.bitCount(j);  
51.      int z=c/Integer.bitCount(k);  
52.      int d=max(abs(x-y), max(abs(y-z), abs(z-x)));  
53.   
54.      int l=0;  
55.      for(int e=0; e<n; e++){  
56.       if(((k>>p[e])&1)!=0&&((k>>q[e])&1)!=0)  
57.        l++;  
58.       else if(((j>>p[e])&1)!=0&&((j>>q[e])&1)!=0)  
59.        l++;  
60.       else if(((i>>p[e])&1)!=0&&((i>>q[e])&1)!=0)  
61.        l++;  
62.      }  
63.      if(d<dmin){  
64.       dmin=d;  
65.       lmax=l;  
66.      }else if(d==dmin){  
67.       lmax=max(lmax, l);  
68.      }  
69.     }  
70.    }  
71.   }  
72.   println(dmin+" "+lmax);  
73.  }  
74.   
75.  void println(String s){  
76.   System.out.println(s);  
77.  }  
78.   
79.  void print(String s){  
80.   System.out.print(s);  
81.  }  
82.   
83.  void debug(Object... os){  
84.   System.err.println(Arrays.deepToString(os));  
85.  }  
86.   
87.  public static void main(String[] args){  
88.   new C().run();  
89.  }  
90. }  

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

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

public class C{
 Scanner sc=new Scanner(System.in);

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

 int n, a, b, c;
 int[] p, q;
 HashMap<String, Integer> map;

 void run(){
  int m=7;

  map=new HashMap<String, Integer>();
  map.put("Anka", 0);
  map.put("Chapay", 1);
  map.put("Cleo", 2);
  map.put("Troll", 3);
  map.put("Dracul", 4);
  map.put("Snowy", 5);
  map.put("Hexadecimal", 6);

  n=sc.nextInt();
  p=new int[n];
  q=new int[n];
  for(int i=0; i<n; i++){
   p[i]=map.get(sc.next());
   sc.next();
   q[i]=map.get(sc.next());
  }
  a=sc.nextInt();
  b=sc.nextInt();
  c=sc.nextInt();

  long dmin=1L<<32;
  int lmax=0;
  for(int k=1; k<1<<m; k++){
   for(int j=1; j<1<<m; j++){
    int i=((1<<m)-1)&~(k^j);
    if((k^j)==(k|j)&&i>0){
     int x=a/Integer.bitCount(i);
     int y=b/Integer.bitCount(j);
     int z=c/Integer.bitCount(k);
     int d=max(abs(x-y), max(abs(y-z), abs(z-x)));

     int l=0;
     for(int e=0; e<n; e++){
      if(((k>>p[e])&1)!=0&&((k>>q[e])&1)!=0)
       l++;
      else if(((j>>p[e])&1)!=0&&((j>>q[e])&1)!=0)
       l++;
      else if(((i>>p[e])&1)!=0&&((i>>q[e])&1)!=0)
       l++;
     }
     if(d<dmin){
      dmin=d;
      lmax=l;
     }else if(d==dmin){
      lmax=max(lmax, l);
     }
    }
   }
  }
  println(dmin+" "+lmax);
 }

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

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

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

 public static void main(String[] args){
  new C().run();
 }
}

D. Falling Anvils

x²+√px+q=0は，p≧4qならば実解が存在する．
つまり，(p,q)∈[0,a]×[-b,b]の長方形内においてp≧4qを満たす領域の面積を計算し，それを長方形の面積で割った値が，実解が存在する確率．a=0やb=0の時は，0除算を避けるために例外処理を追加する必要がある．

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 D{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int t;  
16.  double a, b;  
17.   
18.  void run(){  
19.   t=sc.nextInt();  
20.   for(int i=0; i<t; i++){  
21.    a=sc.nextInt();  
22.    b=sc.nextInt();  
23.    double area;  
24.    if(4*b<a+EPS){  
25.     area=2*b*(a-b);  
26.    }else{  
27.     area=a*(b+a/8);  
28.    }  
29.    if(abs(b)<EPS){  
30.     println("1");  
31.    }else if(abs(a)<EPS){  
32.     println("0.5");  
33.    }else{  
34.     println(area/(2*a*b)+"");  
35.    }  
36.   }  
37.  }  
38.   
39.  void println(String s){  
40.   System.out.println(s);  
41.  }  
42.   
43.  void print(String s){  
44.   System.out.print(s);  
45.  }  
46.   
47.  void debug(Object... os){  
48.   System.err.println(Arrays.deepToString(os));  
49.  }  
50.   
51.  public static void main(String[] args){  
52.   new D().run();  
53.  }  
54. }  

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

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

public class D{
 Scanner sc=new Scanner(System.in);

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

 int t;
 double a, b;

 void run(){
  t=sc.nextInt();
  for(int i=0; i<t; i++){
   a=sc.nextInt();
   b=sc.nextInt();
   double area;
   if(4*b<a+EPS){
    area=2*b*(a-b);
   }else{
    area=a*(b+a/8);
   }
   if(abs(b)<EPS){
    println("1");
   }else if(abs(a)<EPS){
    println("0.5");
   }else{
    println(area/(2*a*b)+"");
   }
  }
 }

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

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

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

 public static void main(String[] args){
  new D().run();
 }
}

ooxo- 2726p 46位
1624 -> 1654
復帰完了…というところです．

Aizu Online Judge 1218 Push!!

■1218 Push!!

人の座標と荷物の座標を状態とし，距離を荷物を押した回数としたダイクストラで解ける．

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 m, n;  
17.  int[][] a;  
18.  int mx0, my0, cx0, cy0, gx, gy;  
19.   
20.  void run(){  
21.   for(;;){  
22.    m=sc.nextInt();  
23.    n=sc.nextInt();  
24.    if((m|n)==0){  
25.     break;  
26.    }  
27.    a=new int[n][m];  
28.    for(int j=0; j<n; j++){  
29.     for(int i=0; i<m; i++){  
30.      a[j][i]=sc.nextInt();  
31.      if(a[j][i]==2){  
32.       cx0=i;  
33.       cy0=j;  
34.       a[j][i]=0;  
35.      }else if(a[j][i]==3){  
36.       gx=i;  
37.       gy=j;  
38.       a[j][i]=0;  
39.      }else if(a[j][i]==4){  
40.       mx0=i;  
41.       my0=j;  
42.       a[j][i]=0;  
43.      }  
44.     }  
45.    }  
46.    solve();  
47.   }  
48.  }  
49.   
50.  void solve(){  
51.   PriorityQueue<P> que=new PriorityQueue<P>();  
52.   boolean[][][][] visited=new boolean[m][n][m][n];  
53.   int[][][][] d=new int[m][n][m][n];  
54.   
55.   for(int k=0; k<m; k++){  
56.    for(int j=0; j<n; j++){  
57.     for(int i=0; i<m; i++){  
58.      fill(d[k][j][i], INF);  
59.     }  
60.    }  
61.   }  
62.   
63.   que.add(new P(mx0, my0, cx0, cy0));  
64.   visited[mx0][my0][cx0][cy0]=true;  
65.   d[mx0][my0][cx0][cy0]=0;  
66.   
67.   int[] dx={0, 0, -1, 1};  
68.   int[] dy={1, -1, 0, 0};  
69.   
70.   for(; !que.isEmpty();){  
71.    P p=que.poll();  
72.    if(d[p.mx][p.my][p.cx][p.cy]<p.d){  
73.     continue;  
74.    }  
75.    for(int i=0; i<4; i++){  
76.     P q=new P(p.mx+dx[i], p.my+dy[i], p.cx, p.cy);  
77.     int push=0;  
78.     // 人が画面外or移動不可  
79.     if(q.mx<0||q.mx>=m||q.my<0||q.my>=n||a[q.my][q.mx]==1){  
80.      continue;  
81.     }  
82.     // 人の移動先がブロック  
83.     if(q.mx==q.cx&&q.my==q.cy){  
84.      q.cx+=dx[i];  
85.      q.cy+=dy[i];  
86.      push=1;  
87.     }  
88.     // ブロックが画面外or配置不可  
89.     if(q.cx<0||q.cx>=m||q.cy<0||q.cy>=n||a[q.cy][q.cx]==1){  
90.      continue;  
91.     }  
92.     // 訪問していない  
93.     if(!visited[q.mx][q.my][q.cx][q.cy]){  
94.      q.d=d[q.mx][q.my][q.cx][q.cy]=d[p.mx][p.my][p.cx][p.cy]  
95.        +push;  
96.      visited[q.mx][q.my][q.cx][q.cy]=true;  
97.      que.offer(q);  
98.     }  
99.    }  
100.   }  
101.   
102.   int min=INF;  
103.   for(int j=0; j<n; j++){  
104.    for(int i=0; i<m; i++){  
105.     min=min(min, d[i][j][gx][gy]);  
106.    }  
107.   }  
108.   
109.   println(""+(min==INF?-1:min));  
110.   
111.  }  
112.   
113.  class P implements Comparable<P>{  
114.   int mx, my, cx, cy;  
115.   int d;  
116.   
117.   P(int mx, int my, int cx, int cy){  
118.    this.mx=mx;  
119.    this.my=my;  
120.    this.cx=cx;  
121.    this.cy=cy;  
122.   }  
123.   
124.   @Override  
125.   public int compareTo(P p){  
126.    return d-p.d;  
127.   }  
128.  }  
129.   
130.  void debug(Object... os){  
131.   System.err.println(Arrays.deepToString(os));  
132.  }  
133.   
134.  void print(String s){  
135.   System.out.print(s);  
136.  }  
137.   
138.  void println(String s){  
139.   System.out.println(s);  
140.  }  
141.   
142.  public static void main(String[] args){  
143.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
144.   new Main().run();  
145.  }  
146. }  

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 m, n;
 int[][] a;
 int mx0, my0, cx0, cy0, gx, gy;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
     if(a[j][i]==2){
      cx0=i;
      cy0=j;
      a[j][i]=0;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=0;
     }else if(a[j][i]==4){
      mx0=i;
      my0=j;
      a[j][i]=0;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  PriorityQueue<P> que=new PriorityQueue<P>();
  boolean[][][][] visited=new boolean[m][n][m][n];
  int[][][][] d=new int[m][n][m][n];

  for(int k=0; k<m; k++){
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     fill(d[k][j][i], INF);
    }
   }
  }

  que.add(new P(mx0, my0, cx0, cy0));
  visited[mx0][my0][cx0][cy0]=true;
  d[mx0][my0][cx0][cy0]=0;

  int[] dx={0, 0, -1, 1};
  int[] dy={1, -1, 0, 0};

  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.mx][p.my][p.cx][p.cy]<p.d){
    continue;
   }
   for(int i=0; i<4; i++){
    P q=new P(p.mx+dx[i], p.my+dy[i], p.cx, p.cy);
    int push=0;
    // 人が画面外or移動不可
    if(q.mx<0||q.mx>=m||q.my<0||q.my>=n||a[q.my][q.mx]==1){
     continue;
    }
    // 人の移動先がブロック
    if(q.mx==q.cx&&q.my==q.cy){
     q.cx+=dx[i];
     q.cy+=dy[i];
     push=1;
    }
    // ブロックが画面外or配置不可
    if(q.cx<0||q.cx>=m||q.cy<0||q.cy>=n||a[q.cy][q.cx]==1){
     continue;
    }
    // 訪問していない
    if(!visited[q.mx][q.my][q.cx][q.cy]){
     q.d=d[q.mx][q.my][q.cx][q.cy]=d[p.mx][p.my][p.cx][p.cy]
       +push;
     visited[q.mx][q.my][q.cx][q.cy]=true;
     que.offer(q);
    }
   }
  }

  int min=INF;
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    min=min(min, d[i][j][gx][gy]);
   }
  }

  println(""+(min==INF?-1:min));

 }

 class P implements Comparable<P>{
  int mx, my, cx, cy;
  int d;

  P(int mx, int my, int cx, int cy){
   this.mx=mx;
   this.my=my;
   this.cx=cx;
   this.cy=cy;
  }

  @Override
  public int compareTo(P p){
   return d-p.d;
  }
 }

 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();
 }
}

Aizu Online Judge 1209 Square Coins

■1209 Square Coins

dp[i]を支払う金額がiの時のコインの組み合わせの数とする．
コインa[0],…,a[j-1]までのdp[i]が求められていれば，a[j]についてのdp[i]を以下の式で求めていけばよい．
dp[i]+=dp[i-a[j]]
初期値は，
dp[0]=1
dp[i]=0 (i≠0)

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.  void run(){  
17.   int n=17;  
18.   int[] a=new int[n];  
19.   for(int i=0; i<n; i++){  
20.    a[i]=(i+1)*(i+1);  
21.   }  
22.   int max=300;  
23.   int[] dp=new int[max];  
24.   dp[0]=1;  
25.   for(int j=0; j<n; j++){  
26.    for(int i=a[j]; i<max; i++){  
27.     dp[i]+=dp[i-a[j]];  
28.    }  
29.   }  
30.   for(;;){  
31.    int k=sc.nextInt();  
32.    if(k==0){  
33.     break;  
34.    }  
35.    println(""+dp[k]);  
36.   }  
37.  }  
38.   
39.  void debug(Object... os){  
40.   System.err.println(Arrays.deepToString(os));  
41.  }  
42.   
43.  void print(String s){  
44.   System.out.print(s);  
45.  }  
46.   
47.  void println(String s){  
48.   System.out.println(s);  
49.  }  
50.   
51.  public static void main(String[] args){  
52.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
53.   new Main().run();  
54.  }  
55. }  

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;

 void run(){
  int n=17;
  int[] a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=(i+1)*(i+1);
  }
  int max=300;
  int[] dp=new int[max];
  dp[0]=1;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<max; i++){
    dp[i]+=dp[i-a[j]];
   }
  }
  for(;;){
   int k=sc.nextInt();
   if(k==0){
    break;
   }
   println(""+dp[k]);
  }
 }

 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();
 }
}

Aizu Online Judge 1209 Square Coins

■1209 Square Coins

dp[i]を支払う金額がiの時のコインの組み合わせの数とする．
コインa[0],…,a[j-1]までのdp[i]が求められていれば，a[j]についてのdp[i]を以下の式で更新すれば良い．
dp[i]+=dp[i-a[j]]

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.  void run(){  
17.   int n=17;  
18.   int[] a=new int[n];  
19.   for(int i=0; i<n; i++){  
20.    a[i]=(i+1)*(i+1);  
21.   }  
22.   int max=300;  
23.   int[] dp=new int[max];  
24.   dp[0]=1;  
25.   for(int j=0; j<n; j++){  
26.    for(int i=a[j]; i<max; i++){  
27.     dp[i]+=dp[i-a[j]];  
28.    }  
29.   }  
30.   for(;;){  
31.    int k=sc.nextInt();  
32.    if(k==0){  
33.     break;  
34.    }  
35.    println(""+dp[k]);  
36.   }  
37.  }  
38.   
39.  void debug(Object... os){  
40.   System.err.println(Arrays.deepToString(os));  
41.  }  
42.   
43.  void print(String s){  
44.   System.out.print(s);  
45.  }  
46.   
47.  void println(String s){  
48.   System.out.println(s);  
49.  }  
50.   
51.  public static void main(String[] args){  
52.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
53.   new Main().run();  
54.  }  
55. }  

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;

 void run(){
  int n=17;
  int[] a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=(i+1)*(i+1);
  }
  int max=300;
  int[] dp=new int[max];
  dp[0]=1;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<max; i++){
    dp[i]+=dp[i-a[j]];
   }
  }
  for(;;){
   int k=sc.nextInt();
   if(k==0){
    break;
   }
   println(""+dp[k]);
  }
 }

 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();
 }
}

TopCoder Member SRM 503 Div1 Medium KingdomXCitiesandVillages

■KingdomXCitiesandVillages

問題・解説は，Match Editorial Archiveを参考に．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. public class KingdomXCitiesandVillages {  
6.  int INF=1<<28;  
7.  double EPS=1e-9;  
8.   
9.  int m, n;  
10.   
11.  public double determineLength(int[] cx, int[] cy, int[] vx, int[] vy) {  
12.   m=cx.length;  
13.   n=vx.length;  
14.   double sum=0;  
15.   for(int j=0;j<n;j++){  
16.    LinkedList<R> list=new LinkedList<R>();  
17.    for(int i=0;i<n;i++){  
18.     if(i!=j){  
19.      list.add(new R(Math.hypot(vx[j]-vx[i], vy[j]-vy[i]), false));  
20.     }  
21.    }  
22.    for(int i=0;i<m;i++){  
23.     list.add(new R(Math.hypot(vx[j]-cx[i], vy[j]-cy[i]), true));  
24.    }  
25.    R[] rs=list.toArray(new R[0]);  
26.    Arrays.sort(rs);  
27.    for(int i=0;i<rs.length;i++){  
28.     if(rs[i].isCity){  
29.      sum+=rs[i].d/(i+1);  
30.      break;  
31.     }else{  
32.      sum+=rs[i].d/(i+1)/(i+2);  
33.     }  
34.    }  
35.   }  
36.   return sum;  
37.  }  
38.   
39.  class R implements Comparable<R>{  
40.   double d;  
41.   boolean isCity;  
42.   R(double d, boolean isCity){  
43.    this.d=d;  
44.    this.isCity=isCity;  
45.   }  
46.   public int compareTo(R r){  
47.    if(d-r.d+EPS<0){  
48.     return -1;  
49.    }else if(d-r.d>0+EPS){  
50.     return 1;  
51.    }else{  
52.     return 0;  
53.    }  
54.   }  
55.  }  
56. }  
57.   
58.   
59. // Powered by FileEdit  
60. // Powered by TZTester 1.01 [25-Feb-2003]  
61. // Powered by CodeProcessor  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class KingdomXCitiesandVillages {
 int INF=1<<28;
 double EPS=1e-9;

 int m, n;

 public double determineLength(int[] cx, int[] cy, int[] vx, int[] vy) {
  m=cx.length;
  n=vx.length;
  double sum=0;
  for(int j=0;j<n;j++){
   LinkedList<R> list=new LinkedList<R>();
   for(int i=0;i<n;i++){
    if(i!=j){
     list.add(new R(Math.hypot(vx[j]-vx[i], vy[j]-vy[i]), false));
    }
   }
   for(int i=0;i<m;i++){
    list.add(new R(Math.hypot(vx[j]-cx[i], vy[j]-cy[i]), true));
   }
   R[] rs=list.toArray(new R[0]);
   Arrays.sort(rs);
   for(int i=0;i<rs.length;i++){
    if(rs[i].isCity){
     sum+=rs[i].d/(i+1);
     break;
    }else{
     sum+=rs[i].d/(i+1)/(i+2);
    }
   }
  }
  return sum;
 }

 class R implements Comparable<R>{
  double d;
  boolean isCity;
  R(double d, boolean isCity){
   this.d=d;
   this.isCity=isCity;
  }
  public int compareTo(R r){
   if(d-r.d+EPS<0){
    return -1;
   }else if(d-r.d>0+EPS){
    return 1;
   }else{
    return 0;
   }
  }
 }
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

Aizu Online Judge 1216 Lost in Space

■1216 Lost in Space

全探索で間に合う．
元の三角形の辺の長さをd[i]とする．
与えられた座標軍からある3点を選び，それぞれの辺の長さをe[i]とする．
この時，それぞれの辺の比r[i]は，
r[i]=e[i]/d[i]
となる．
それぞれの比の誤差が，0.1%以上になることは無い，というのだから，任意のi，jに対して，
|r[i]-r[j]|/r[i] < 0.1
となる．

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.  double[] d;  
17.  P[] ps;  
18.  int n;  
19.   
20.  void run(){  
21.   d=new double[3];  
22.   for(int t=sc.nextInt(); t>0; t--){  
23.    for(int i=0; i<3; i++){  
24.     d[i]=sc.nextDouble();  
25.    }  
26.    n=sc.nextInt();  
27.    ps=new P[n];  
28.    for(int i=0; i<n; i++){  
29.     double x=sc.nextDouble();  
30.     double y=sc.nextDouble();  
31.     double z=sc.nextDouble();  
32.     ps[i]=new P(x, y, z);  
33.    }  
34.    solve();  
35.   }  
36.  }  
37.   
38.  void solve(){  
39.   double[] len={0, 0, 0};  
40.   for(int c=0; c<n; c++){  
41.    for(int b=0; b<n; b++){  
42.     if(b==c){  
43.      continue;  
44.     }  
45.     for(int a=0; a<n; a++){  
46.      if(a==b||a==c){  
47.       continue;  
48.      }  
49.      len[0]=ps[b].sub(ps[c]).abs()/d[0];  
50.      len[1]=ps[c].sub(ps[a]).abs()/d[1];  
51.      len[2]=ps[a].sub(ps[b]).abs()/d[2];  
52.      boolean error=false;  
53.      for(int i=0; i<3; i++){  
54.       int p=i;  
55.       int q=(i+1)%3;  
56.       error|=abs(len[p]-len[q])/len[p]+EPS>=0.001;  
57.      }  
58.      if(!error){  
59.       println((a+1)+" "+(b+1)+" "+(c+1));  
60.      }  
61.     }  
62.    }  
63.   }  
64.  }  
65.   
66.  class P{  
67.   double x, y, z;  
68.   
69.   P(){  
70.    this(0, 0, 0);  
71.   }  
72.   
73.   P(double x, double y, double z){  
74.    this.x=x;  
75.    this.y=y;  
76.    this.z=z;  
77.   }  
78.   
79.   P add(P p){  
80.    return new P(x+p.x, y+p.y, z+p.y);  
81.   }  
82.   
83.   P sub(P p){  
84.    return new P(x-p.x, y-p.y, z-p.z);  
85.   }  
86.   
87.   P mul(double m){  
88.    return new P(x*m, y*m, z*m);  
89.   }  
90.   
91.   P div(double d){  
92.    return new P(x/d, y/d, z/d);  
93.   }  
94.   
95.   double abs(){  
96.    return Math.sqrt(abs2());  
97.   }  
98.   
99.   double abs2(){  
100.    return x*x+y*y+z*z;  
101.   }  
102.   
103.   // inner product  
104.   double dot(P p){  
105.    return x*p.x+y*p.y+z*p.y;  
106.   }  
107.   
108.   // outer product  
109.   P det(P p){  
110.    return new P(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);  
111.   }  
112.   
113.   @Override  
114.   public String toString(){  
115.    return x+", "+y+", "+z;  
116.   }  
117.  }  
118.   
119.  void debug(Object... os){  
120.   System.err.println(Arrays.deepToString(os));  
121.  }  
122.   
123.  void print(String s){  
124.   System.out.print(s);  
125.  }  
126.   
127.  void println(String s){  
128.   System.out.println(s);  
129.  }  
130.   
131.  public static void main(String[] args){  
132.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
133.   new Main().run();  
134.  }  
135. }  

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;

 double[] d;
 P[] ps;
 int n;

 void run(){
  d=new double[3];
  for(int t=sc.nextInt(); t>0; t--){
   for(int i=0; i<3; i++){
    d[i]=sc.nextDouble();
   }
   n=sc.nextInt();
   ps=new P[n];
   for(int i=0; i<n; i++){
    double x=sc.nextDouble();
    double y=sc.nextDouble();
    double z=sc.nextDouble();
    ps[i]=new P(x, y, z);
   }
   solve();
  }
 }

 void solve(){
  double[] len={0, 0, 0};
  for(int c=0; c<n; c++){
   for(int b=0; b<n; b++){
    if(b==c){
     continue;
    }
    for(int a=0; a<n; a++){
     if(a==b||a==c){
      continue;
     }
     len[0]=ps[b].sub(ps[c]).abs()/d[0];
     len[1]=ps[c].sub(ps[a]).abs()/d[1];
     len[2]=ps[a].sub(ps[b]).abs()/d[2];
     boolean error=false;
     for(int i=0; i<3; i++){
      int p=i;
      int q=(i+1)%3;
      error|=abs(len[p]-len[q])/len[p]+EPS>=0.001;
     }
     if(!error){
      println((a+1)+" "+(b+1)+" "+(c+1));
     }
    }
   }
  }
 }

 class P{
  double x, y, z;

  P(){
   this(0, 0, 0);
  }

  P(double x, double y, double z){
   this.x=x;
   this.y=y;
   this.z=z;
  }

  P add(P p){
   return new P(x+p.x, y+p.y, z+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y, z-p.z);
  }

  P mul(double m){
   return new P(x*m, y*m, z*m);
  }

  P div(double d){
   return new P(x/d, y/d, z/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y+z*z;
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y+z*p.y;
  }

  // outer product
  P det(P p){
   return new P(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);
  }

  @Override
  public String toString(){
   return x+", "+y+", "+z;
  }
 }

 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();
 }
}

Aizu Online Judge 1214 Walking Ant

■1214 Walking Ant

BFSで解ける．但し状態を，(x, y, hp)とする．hpは現在の体力を表す．

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 m, n;  
17.  int sx, sy, gx, gy;  
18.  int[][] a;  
19.   
20.  void run(){  
21.   for(;;){  
22.    m=sc.nextInt();  
23.    n=sc.nextInt();  
24.    if((m|n)==0){  
25.     break;  
26.    }  
27.    a=new int[n][m];  
28.    for(int j=0; j<n; j++){  
29.     for(int i=0; i<m; i++){  
30.      a[j][i]=sc.nextInt();  
31.      if(a[j][i]==2){  
32.       sx=i;  
33.       sy=j;  
34.       a[j][i]=1;  
35.      }else if(a[j][i]==3){  
36.       gx=i;  
37.       gy=j;  
38.       a[j][i]=1;  
39.      }  
40.     }  
41.    }  
42.    solve();  
43.   }  
44.  }  
45.   
46.  void solve(){  
47.   int max=7;  
48.   int[][][] d=new int[n][m][max];  
49.   boolean[][][] visited=new boolean[n][m][max];  
50.   LinkedList<P> que=new LinkedList<P>();  
51.   
52.   for(int j=0; j<n; j++){  
53.    for(int i=0; i<m; i++){  
54.     fill(d[j][i], INF);  
55.    }  
56.   }  
57.   
58.   que.offer(new P(sx, sy, 6));  
59.   d[sy][sx][6]=0;  
60.   visited[sy][sx][6]=true;  
61.   
62.   int[] dx={0, 0, -1, 1};  
63.   int[] dy={-1, 1, 0, 0};  
64.   
65.   for(; !que.isEmpty();){  
66.    P p=que.poll();  
67.    for(int i=0; i<4; i++){  
68.     P q=new P(p.x+dx[i], p.y+dy[i], p.hp-1);  
69.     if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&a[q.y][q.x]!=0&&q.hp>0){  
70.      if(a[q.y][q.x]==4){  
71.       q.hp=6;  
72.      }  
73.      if(!visited[q.y][q.x][q.hp]){  
74.       que.offer(q);  
75.       d[q.y][q.x][q.hp]=d[p.y][p.x][p.hp]+1;  
76.       visited[q.y][q.x][q.hp]=true;  
77.      }  
78.     }  
79.    }  
80.   }  
81.   int ans=INF;  
82.   for(int k=0; k<max; k++){  
83.    ans=min(ans, d[gy][gx][k]);  
84.   }  
85.   println((ans!=INF?ans:-1)+"");  
86.  }  
87.   
88.  class P{  
89.   int x, y, hp;  
90.   
91.   P(int x, int y, int hp){  
92.    this.x=x;  
93.    this.y=y;  
94.    this.hp=hp;  
95.   }  
96.  }  
97.   
98.  void debug(Object... os){  
99.   System.err.println(Arrays.deepToString(os));  
100.  }  
101.   
102.  void print(String s){  
103.   System.out.print(s);  
104.  }  
105.   
106.  void println(String s){  
107.   System.out.println(s);  
108.  }  
109.   
110.  public static void main(String[] args){  
111.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
112.   new Main().run();  
113.  }  
114. }  

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 m, n;
 int sx, sy, gx, gy;
 int[][] a;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
     if(a[j][i]==2){
      sx=i;
      sy=j;
      a[j][i]=1;
     }else if(a[j][i]==3){
      gx=i;
      gy=j;
      a[j][i]=1;
     }
    }
   }
   solve();
  }
 }

 void solve(){
  int max=7;
  int[][][] d=new int[n][m][max];
  boolean[][][] visited=new boolean[n][m][max];
  LinkedList<P> que=new LinkedList<P>();

  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    fill(d[j][i], INF);
   }
  }

  que.offer(new P(sx, sy, 6));
  d[sy][sx][6]=0;
  visited[sy][sx][6]=true;

  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  for(; !que.isEmpty();){
   P p=que.poll();
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i], p.hp-1);
    if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&a[q.y][q.x]!=0&&q.hp>0){
     if(a[q.y][q.x]==4){
      q.hp=6;
     }
     if(!visited[q.y][q.x][q.hp]){
      que.offer(q);
      d[q.y][q.x][q.hp]=d[p.y][p.x][p.hp]+1;
      visited[q.y][q.x][q.hp]=true;
     }
    }
   }
  }
  int ans=INF;
  for(int k=0; k<max; k++){
   ans=min(ans, d[gy][gx][k]);
  }
  println((ans!=INF?ans:-1)+"");
 }

 class P{
  int x, y, hp;

  P(int x, int y, int hp){
   this.x=x;
   this.y=y;
   this.hp=hp;
  }
 }

 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();
 }
}

TopCoder Member SRM 503

SRM 503(12/19 1:00~3:00)

■FoxMakingDice(Div1 Easy)

Toastmanは，パンを何枚か焼きたい．パンには幾つかの種類があり，ある種類のパンは，X分未満焼くとunder toasted，X分超過焼くとover toastedとなる．
Toastmanは，パンを焼いたが，m_i分焼いてunder toastedだったもの，また，n_i分焼いてover toastedだったものが出来た．Toastmanは何種類のパンを用いたかを覚えていないが，ある種類のパンを焼いたときにunder toasted・over toastedだったものがそれぞれ少なくとも1枚以上はあったという．
パンの種類の最小数を答えよ．

under toastedだったものをU，over toastedだったものをOとし，それらを焼かれた時間の数直線にプロットする．例えば下図．
UOUOOUOUOUOUO

・パンの種類が1つで良い場合．

UUUUU | OOOOOO
上のような場合．Xは，"|"で表される．

・パンが何種類あっても不可能な場合．

O…………
または，
…………U
の場合．

・パンの種類が2つで良い場合．

上記のどれにも当てはまらない場合．
何故なら，必ずパンの順列は，
U[…………]O
となり，
U | […………]O
で分けると，
[…………]内のOは全て排除され．
[U……U]O
となる．その後，
[U……U] | O
で分ければ終了する．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. public class ToastXToast {  
7.  int INF=1<<28;  
8.  double EPS=1e-9;  
9.   
10.  public int bake(int[] a, int[] b) {  
11.   Arrays.sort(a); // o  
12.   Arrays.sort(b); // x  
13.   boolean f=true;  
14.   for(int j=0;j<b.length;j++){  
15.    for(int i=0;i<a.length;i++){  
16.     f&=a[i]<b[j];  
17.    }  
18.   }  
19.   if(f){  
20.    return 1;  
21.   }  
22.   else if(a[0]>b[0]||a[a.length-1]>b[b.length-1]){  
23.    return -1;  
24.   }  
25.   else if(a.length>=2&&b.length>=2){  
26.    return 2;  
27.   }  
28.   else{  
29.    return -1;  
30.   }  
31.  }  
32.   
33.  void debug(Object...os){  
34.   System.err.println(Arrays.deepToString(os));  
35.  }  
36.   
37.  void print(String s){  
38.   System.out.print(s);  
39.  }  
40.   
41.  void println(String s){  
42.   System.out.println(s);  
43.  }  
44.   
45.  public static void main(String[] args) {  
46.   ToastXToast temp = new ToastXToast();  
47.  }  
48. }  

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

public class ToastXToast {
 int INF=1<<28;
 double EPS=1e-9;

 public int bake(int[] a, int[] b) {
  Arrays.sort(a); // o
  Arrays.sort(b); // x
  boolean f=true;
  for(int j=0;j<b.length;j++){
   for(int i=0;i<a.length;i++){
    f&=a[i]<b[j];
   }
  }
  if(f){
   return 1;
  }
  else if(a[0]>b[0]||a[a.length-1]>b[b.length-1]){
   return -1;
  }
  else if(a.length>=2&&b.length>=2){
   return 2;
  }
  else{
   return -1;
  }
 }

 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) {
  ToastXToast temp = new ToastXToast();
 }
}

■Result

○×× 0 0
144.26pt.

■Rating

1243 -> 1279
若干上昇．少しずつRatingを上げていきたいものです…．

Aizu Online Judge 1212 Mirror Illusion

■1212 Mirror Illusion

ある座標pから方向vを見ていたとする．ちなみに，初期条件は，p₀=(0.75, 0.25)，v₀=(1, 1)
vのノルムを16以上にとれば，(p+v)が必ず室外に出るので，以下vをそういうベクトルとする．
まず，(p, p+v)が人に当たるかを調べる．当たっていたらそこで終了．
次に，(p, p+v)が鏡に当たるかを調べる． 一つでも当たる鏡があれば，その内で交差点が最もpに近い鏡mを選ぶ．pを，(p, p+v)とmとの交差点とする．また，新しい方向ベクトルを， mが横置きだったらv'=(v_x, -v_y)， 縦置きだったらv'=(-v_x, v_y)とする．
一つも当たらなかった場合は，外壁のいずれかに当たっていることになるので，4つの壁それぞれについて当たっているかおよび交差点を計算．

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 n;  
17.  int m;  
18.  Seg[] segs;  
19.   
20.  void run(){  
21.   m=8;  
22.   for(;;){  
23.    n=sc.nextInt();  
24.    if(n<0){  
25.     break;  
26.    }  
27.    segs=new Seg[n];  
28.    for(int i=0; i<n; i++){  
29.     char c=sc.next().charAt(0);  
30.     int x=sc.nextInt();  
31.     int y=sc.nextInt();  
32.     if(c=='x'){  
33.      segs[i]=new Seg(0, x, y, x+1, y);  
34.     }else{  
35.      segs[i]=new Seg(1, x, y, x, y+1);  
36.     }  
37.    }  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   P p0=new P(0.75, 0.25);  
44.   P p=new P(0.75, 0.25);  
45.   P v=new P(1, 1);  
46.   Seg[] walls=new Seg[4];  
47.   walls[0]=new Seg(0, 0, 0, m, 0);  
48.   walls[1]=new Seg(0, 0, m, m, m);  
49.   walls[2]=new Seg(0, 0, 0, 0, m);  
50.   walls[3]=new Seg(0, m, 0, m, m);  
51.   
52.   for(int i=0; i<10; i++){  
53.    v=v.div(v.abs()).mul(2*m);  
54.   
55.    if(p.sub(p0).abs()>EPS&&disSP(p, p.add(v), p0)<EPS){  
56.     int x=(int)(p0.x*100+EPS);  
57.     int y=(int)(p0.y*100+EPS);  
58.     println(x+" "+y);  
59.     break;  
60.    }  
61.   
62.    Seg seg=null;  
63.    P p2=null;  
64.    double min=INF;  
65.    for(Seg s : segs){  
66.     if(crsSS(p, p.add(v), s.p1, s.p2)){  
67.      P q=isLL(p, p.add(v), s.p1, s.p2);  
68.      double d=p.sub(q).abs();  
69.      if(d<min+EPS&&d>EPS){  
70.       seg=s;  
71.       p2=q;  
72.       min=p.sub(q).abs();  
73.      }  
74.     }  
75.    }  
76.   
77.    if(p2!=null){  
78.     p=p2;  
79.     if(seg.d==0){  
80.      v.y=-v.y;  
81.     }else{  
82.      v.x=-v.x;  
83.     }  
84.    }else{  
85.     for(Seg s : walls){  
86.      if(crsSS(p, p.add(v), s.p1, s.p2)){  
87.       P q=isLL(p, p.add(v), s.p1, s.p2);  
88.       if(p.sub(q).abs()>EPS){  
89.        int x=(int)(q.x*100+EPS);  
90.        int y=(int)(q.y*100+EPS);  
91.        println(x+" "+y);  
92.       }  
93.      }  
94.     }  
95.     break;  
96.    }  
97.   }  
98.  }  
99.   
100.  // 線分と点の距離  
101.  double disSP(P p1, P p2, P q){  
102.   if(p2.sub(p1).dot(q.sub(p1))<EPS)  
103.    return q.sub(p1).abs();  
104.   if(p1.sub(p2).dot(q.sub(p2))<EPS)  
105.    return q.sub(p2).abs();  
106.   return disLP(p1, p2, q);  
107.  }  
108.   
109.  // 直線と点の距離  
110.  double disLP(P p1, P p2, P q){  
111.   return abs(p2.sub(p1).det(q.sub(p1)))/p2.sub(p1).abs();  
112.  }  
113.   
114.  // 線分と線分の交差判定  
115.  boolean crsSS(P p1, P p2, P q1, P q2){  
116.   if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))  
117.    return false;  
118.   if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))  
119.    return false;  
120.   if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))  
121.    return false;  
122.   if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))  
123.    return false;  
124.   return signum(p2.sub(p1).det(q1.sub(p1)))  
125.     *signum(p2.sub(p1).det(q2.sub(p1)))<EPS  
126.     &&signum(q2.sub(q1).det(p1.sub(q1)))  
127.       *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;  
128.  }  
129.   
130.  // 直線と直線の交点  
131.  P isLL(P p1, P p2, P q1, P q2){  
132.   double d=q2.sub(q1).det(p2.sub(p1));  
133.   if(abs(d)<EPS)  
134.    return null;  
135.   return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));  
136.  }  
137.   
138.  class Seg{  
139.   int d;  
140.   P p1, p2;  
141.   
142.   Seg(int d, int x1, int y1, int x2, int y2){  
143.    this.d=d;  
144.    p1=new P(x1, y1);  
145.    p2=new P(x2, y2);  
146.   }  
147.  }  
148.   
149.  // 2 dimensions  
150.  class P{  
151.   double x, y;  
152.   
153.   P(){  
154.    this(0, 0);  
155.   }  
156.   
157.   P(double x, double y){  
158.    this.x=x;  
159.    this.y=y;  
160.   }  
161.   
162.   P add(P p){  
163.    return new P(x+p.x, y+p.y);  
164.   }  
165.   
166.   P sub(P p){  
167.    return new P(x-p.x, y-p.y);  
168.   }  
169.   
170.   P mul(double m){  
171.    return new P(x*m, y*m);  
172.   }  
173.   
174.   P div(double d){  
175.    return new P(x/d, y/d);  
176.   }  
177.   
178.   double abs(){  
179.    return Math.sqrt(abs2());  
180.   }  
181.   
182.   double abs2(){  
183.    return x*x+y*y;  
184.   }  
185.   
186.   double arg(){  
187.    return Math.atan2(y, x);  
188.   }  
189.   
190.   // inner product  
191.   double dot(P p){  
192.    return x*p.x+y*p.y;  
193.   }  
194.   
195.   // outer product  
196.   double det(P p){  
197.    return x*p.y-y*p.x;  
198.   }  
199.   
200.   P rot90(){  
201.    return new P(-y, x);  
202.   }  
203.   
204.   // conjugation  
205.   P conj(){  
206.    return new P(x, -y);  
207.   }  
208.  }  
209.   
210.  void debug(Object... os){  
211.   System.err.println(Arrays.deepToString(os));  
212.  }  
213.   
214.  void print(String s){  
215.   System.out.print(s);  
216.  }  
217.   
218.  void println(String s){  
219.   System.out.println(s);  
220.  }  
221.   
222.  public static void main(String[] args){  
223.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
224.   new Main().run();  
225.  }  
226. }  

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 n;
 int m;
 Seg[] segs;

 void run(){
  m=8;
  for(;;){
   n=sc.nextInt();
   if(n<0){
    break;
   }
   segs=new Seg[n];
   for(int i=0; i<n; i++){
    char c=sc.next().charAt(0);
    int x=sc.nextInt();
    int y=sc.nextInt();
    if(c=='x'){
     segs[i]=new Seg(0, x, y, x+1, y);
    }else{
     segs[i]=new Seg(1, x, y, x, y+1);
    }
   }
   solve();
  }
 }

 void solve(){
  P p0=new P(0.75, 0.25);
  P p=new P(0.75, 0.25);
  P v=new P(1, 1);
  Seg[] walls=new Seg[4];
  walls[0]=new Seg(0, 0, 0, m, 0);
  walls[1]=new Seg(0, 0, m, m, m);
  walls[2]=new Seg(0, 0, 0, 0, m);
  walls[3]=new Seg(0, m, 0, m, m);

  for(int i=0; i<10; i++){
   v=v.div(v.abs()).mul(2*m);

   if(p.sub(p0).abs()>EPS&&disSP(p, p.add(v), p0)<EPS){
    int x=(int)(p0.x*100+EPS);
    int y=(int)(p0.y*100+EPS);
    println(x+" "+y);
    break;
   }

   Seg seg=null;
   P p2=null;
   double min=INF;
   for(Seg s : segs){
    if(crsSS(p, p.add(v), s.p1, s.p2)){
     P q=isLL(p, p.add(v), s.p1, s.p2);
     double d=p.sub(q).abs();
     if(d<min+EPS&&d>EPS){
      seg=s;
      p2=q;
      min=p.sub(q).abs();
     }
    }
   }

   if(p2!=null){
    p=p2;
    if(seg.d==0){
     v.y=-v.y;
    }else{
     v.x=-v.x;
    }
   }else{
    for(Seg s : walls){
     if(crsSS(p, p.add(v), s.p1, s.p2)){
      P q=isLL(p, p.add(v), s.p1, s.p2);
      if(p.sub(q).abs()>EPS){
       int x=(int)(q.x*100+EPS);
       int y=(int)(q.y*100+EPS);
       println(x+" "+y);
      }
     }
    }
    break;
   }
  }
 }

 // 線分と点の距離
 double disSP(P p1, P p2, P q){
  if(p2.sub(p1).dot(q.sub(p1))<EPS)
   return q.sub(p1).abs();
  if(p1.sub(p2).dot(q.sub(p2))<EPS)
   return q.sub(p2).abs();
  return disLP(p1, p2, q);
 }

 // 直線と点の距離
 double disLP(P p1, P p2, P q){
  return abs(p2.sub(p1).det(q.sub(p1)))/p2.sub(p1).abs();
 }

 // 線分と線分の交差判定
 boolean crsSS(P p1, P p2, P q1, P q2){
  if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))
   return false;
  if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))
   return false;
  if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))
   return false;
  if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))
   return false;
  return signum(p2.sub(p1).det(q1.sub(p1)))
    *signum(p2.sub(p1).det(q2.sub(p1)))<EPS
    &&signum(q2.sub(q1).det(p1.sub(q1)))
      *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;
 }

 // 直線と直線の交点
 P isLL(P p1, P p2, P q1, P q2){
  double d=q2.sub(q1).det(p2.sub(p1));
  if(abs(d)<EPS)
   return null;
  return p1.add(p2.sub(p1).mul(q2.sub(q1).det(q1.sub(p1))/d));
 }

 class Seg{
  int d;
  P p1, p2;

  Seg(int d, int x1, int y1, int x2, int y2){
   this.d=d;
   p1=new P(x1, y1);
   p2=new P(x2, y2);
  }
 }

 // 2 dimensions
 class P{
  double x, y;

  P(){
   this(0, 0);
  }

  P(double x, double y){
   this.x=x;
   this.y=y;
  }

  P add(P p){
   return new P(x+p.x, y+p.y);
  }

  P sub(P p){
   return new P(x-p.x, y-p.y);
  }

  P mul(double m){
   return new P(x*m, y*m);
  }

  P div(double d){
   return new P(x/d, y/d);
  }

  double abs(){
   return Math.sqrt(abs2());
  }

  double abs2(){
   return x*x+y*y;
  }

  double arg(){
   return Math.atan2(y, x);
  }

  // inner product
  double dot(P p){
   return x*p.x+y*p.y;
  }

  // outer product
  double det(P p){
   return x*p.y-y*p.x;
  }

  P rot90(){
   return new P(-y, x);
  }

  // conjugation
  P conj(){
   return new P(x, -y);
  }
 }

 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();
 }
}

Aizu Online Judge 1211 Trapezoids

■1211 Trapezoids

下のような入力が与えられたとする．

***                     *  *         ********** *   *        *        * *    *       * ***    * *     *      * *  *   * *      *     * *****  * *       *    *        * *        *   ********** *         *             ************

まず，四角形の内部となりえない所をある値（ここでは'-'）で埋める．

-----------***--------- -----------*  *-------- **********-*   *------- *        *-*    *------ * ***    *-*     *----- * *  *   *-*      *---- * *****  *-*       *--- *        *-*        *-- **********-*         *- -----------************

(i, j)が'*'となる(i, j)をラスタスキャン． 輪郭をたどり，たどった点を' 'に変更する．

-----------***--------- -----------*  *-------- -----------*   *------- -        --*    *------ - ***    --*     *----- - *  *   --*      *---- - *****  --*       *--- -        --*        *-- -----------*         *- -----------************

'-'のみを壁として(i, j)からBFS．この時の探索回数が領域の面積．
(i, j)からBFSで0を'-'に塗りつぶしていく

-----------***--------- -----------*  *-------- -----------*   *------- -----------*    *------ --***------*     *----- --*  *-----*      *---- --*****----*       *--- -----------*        *-- -----------*         *- -----------************

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 n, m;  
17.  int[][] a;  
18.  int c;  
19.  boolean[] wall;  
20.   
21.  void run(){  
22.   for(int k=0;; k++){  
23.    n=sc.nextInt();  
24.    if(n==0){  
25.     break;  
26.    }  
27.    if(k>0){  
28.     println("----------");  
29.    }  
30.    sc.nextLine();  
31.    m=0;  
32.    String[] ss=new String[n];  
33.    for(int i=0; i<n; i++){  
34.     ss[i]=sc.nextLine();  
35.     m=max(m, ss[i].length());  
36.    }  
37.    a=new int[n][m];  
38.    for(int j=0; j<n; j++){  
39.     for(int i=0; i<ss[j].length(); i++){  
40.      a[j][i]=ss[j].charAt(i)=='*'?1:0;  
41.     }  
42.    }  
43.    solve();  
44.   }  
45.  }  
46.   
47.  void solve(){  
48.   c=2;  
49.   wall=new boolean[]{false, true, true};  
50.   for(int j=0; j<n; j++){  
51.    if(a[j][0]==0){  
52.     bfs(0, j);  
53.    }  
54.    if(a[j][m-1]==0){  
55.     bfs(m-1, j);  
56.    }  
57.   }  
58.   for(int i=0; i<m; i++){  
59.    if(a[0][i]==0){  
60.     bfs(i, 0);  
61.    }  
62.    if(a[n-1][i]==0){  
63.     bfs(i, n-1);  
64.    }  
65.   }  
66.   
67.   HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();  
68.   int[] dx={1, 1, 0, -1, -1, -1, 0, 1};  
69.   int[] dy={0, 1, 1, 1, 0, -1, -1, -1};  
70.   for(int j=0; j<n; j++){  
71.    for(int i=0; i<m; i++){  
72.     if(a[j][i]==1){  
73.      int outline=0;  
74.      int d=0;  
75.      int x=i, y=j;  
76.      for(;;){  
77.       outline++;  
78.       a[y][x]=0;  
79.       boolean f=false;  
80.       d=(d+5)%8;  
81.       for(int k=0; k<8; k++, d=(d+1)%8){  
82.        int x2=x+dx[d];  
83.        int y2=y+dy[d];  
84.        if(x2>=0&&x2<m&&y2>=0&&y2<n&&a[y2][x2]==1){  
85.         x=x2;  
86.         y=y2;  
87.         f=true;  
88.         break;  
89.        }  
90.       }  
91.       if(!f){  
92.        break;  
93.       }  
94.      }  
95.      c=-1;  
96.      wall=new boolean[]{false, false, true};  
97.      int area=bfs(x, y);  
98.      if(!map.containsKey(area)){  
99.       map.put(area, 0);  
100.      }  
101.      map.put(area, map.get(area)+1);  
102.   
103.      c=2;  
104.      wall=new boolean[]{false, true, true};  
105.      bfs(x, y);  
106.     }  
107.    }  
108.   }  
109.   Integer[] is=map.keySet().toArray(new Integer[0]);  
110.   sort(is);  
111.   for(int key : is){  
112.    println(key+" "+map.get(key));  
113.   }  
114.  }  
115.   
116.  int bfs(int x, int y){  
117.   int[] dx={0, 0, -1, 1};  
118.   int[] dy={-1, 1, 0, 0};  
119.   LinkedList<P> que=new LinkedList<P>();  
120.   boolean[][] visited=new boolean[n][m];  
121.   que.add(new P(x, y));  
122.   visited[y][x]=true;  
123.   int res=0;  
124.   for(; !que.isEmpty();){  
125.    P p=que.poll();  
126.    if(c>=0){  
127.     a[p.y][p.x]=c;  
128.    }  
129.    res++;  
130.    for(int i=0; i<4; i++){  
131.     P q=new P(p.x+dx[i], p.y+dy[i]);  
132.     if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x]  
133.       &&!wall[a[q.y][q.x]]){  
134.      que.add(q);  
135.      visited[q.y][q.x]=true;  
136.     }  
137.    }  
138.   }  
139.   return res;  
140.  }  
141.   
142.  class P{  
143.   int x, y;  
144.   
145.   P(int x, int y){  
146.    this.x=x;  
147.    this.y=y;  
148.   }  
149.  }  
150.   
151.  void debug(Object... os){  
152.   System.err.println(Arrays.deepToString(os));  
153.  }  
154.   
155.  void print(String s){  
156.   System.out.print(s);  
157.  }  
158.   
159.  void println(String s){  
160.   System.out.println(s);  
161.  }  
162.   
163.  public static void main(String[] args){  
164.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
165.   new Main().run();  
166.  }  
167. }  

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 n, m;
 int[][] a;
 int c;
 boolean[] wall;

 void run(){
  for(int k=0;; k++){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   if(k>0){
    println("----------");
   }
   sc.nextLine();
   m=0;
   String[] ss=new String[n];
   for(int i=0; i<n; i++){
    ss[i]=sc.nextLine();
    m=max(m, ss[i].length());
   }
   a=new int[n][m];
   for(int j=0; j<n; j++){
    for(int i=0; i<ss[j].length(); i++){
     a[j][i]=ss[j].charAt(i)=='*'?1:0;
    }
   }
   solve();
  }
 }

 void solve(){
  c=2;
  wall=new boolean[]{false, true, true};
  for(int j=0; j<n; j++){
   if(a[j][0]==0){
    bfs(0, j);
   }
   if(a[j][m-1]==0){
    bfs(m-1, j);
   }
  }
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    bfs(i, 0);
   }
   if(a[n-1][i]==0){
    bfs(i, n-1);
   }
  }

  HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
  int[] dx={1, 1, 0, -1, -1, -1, 0, 1};
  int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
  for(int j=0; j<n; j++){
   for(int i=0; i<m; i++){
    if(a[j][i]==1){
     int outline=0;
     int d=0;
     int x=i, y=j;
     for(;;){
      outline++;
      a[y][x]=0;
      boolean f=false;
      d=(d+5)%8;
      for(int k=0; k<8; k++, d=(d+1)%8){
       int x2=x+dx[d];
       int y2=y+dy[d];
       if(x2>=0&&x2<m&&y2>=0&&y2<n&&a[y2][x2]==1){
        x=x2;
        y=y2;
        f=true;
        break;
       }
      }
      if(!f){
       break;
      }
     }
     c=-1;
     wall=new boolean[]{false, false, true};
     int area=bfs(x, y);
     if(!map.containsKey(area)){
      map.put(area, 0);
     }
     map.put(area, map.get(area)+1);

     c=2;
     wall=new boolean[]{false, true, true};
     bfs(x, y);
    }
   }
  }
  Integer[] is=map.keySet().toArray(new Integer[0]);
  sort(is);
  for(int key : is){
   println(key+" "+map.get(key));
  }
 }

 int bfs(int x, int y){
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[n][m];
  que.add(new P(x, y));
  visited[y][x]=true;
  int res=0;
  for(; !que.isEmpty();){
   P p=que.poll();
   if(c>=0){
    a[p.y][p.x]=c;
   }
   res++;
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i]);
    if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x]
      &&!wall[a[q.y][q.x]]){
     que.add(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  return res;
 }

 class P{
  int x, y;

  P(int x, int y){
   this.x=x;
   this.y=y;
  }
 }

 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();
 }
}

Aizu Online Judge 1208 Rational Irrationals

■1208 Rational Irrationals

全探索を行うと，O(n²)でかなりキツイ．そこで二部探索を使う．
具体的には，分数をm/dとした時，dを1~nまで回し，√pに近くなるようなmを求める．
探索の幅として[1,n]を設定し，m/d<√pを条件とすれば，
m/d<√p<(m+1)/d
もしくは，
m/d<(m+1)/d<√p (ただし，m+1>n)
となる．
事実上計算量はO(n)．

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 p, m;  
17.   
18.  void run(){  
19.   for(;;){  
20.    p=sc.nextInt();  
21.    m=sc.nextInt();  
22.    if((p|m)==0){  
23.     break;  
24.    }  
25.    solve();  
26.   }  
27.  }  
28.   
29.  void solve(){  
30.   long n1=0, d1=1;  
31.   long n2=m, d2=1;  
32.   for(long d=1; d<=m; d++){  
33.    double left=1, right=m;  
34.    for(int i=0; i<100; i++){  
35.     double mid=(left+right)/2;  
36.     if(mid*mid<p*d*d+EPS){  
37.      left=mid;  
38.     }else{  
39.      right=mid;  
40.     }  
41.    }  
42.    int n=(int)(left+EPS);  
43.    if(n1*d<n*d1&&n*n<p*d*d){  
44.     n1=n;  
45.     d1=d;  
46.    }  
47.    if(++n<=m){  
48.     if(p*d*d<n*n&&n*d2<n2*d){  
49.      n2=n;  
50.      d2=d;  
51.     }  
52.    }  
53.   }  
54.   long gcd=gcd(n1, d1);  
55.   n1/=gcd;  
56.   d1/=gcd;  
57.   gcd=gcd(n2, d2);  
58.   n2/=gcd;  
59.   d2/=gcd;  
60.   println(n2+"/"+d2+" "+n1+"/"+d1);  
61.  }  
62.   
63.  long gcd(long m, long n){  
64.   for(; n!=0;){  
65.    m=m%n;  
66.    long t=m;  
67.    m=n;  
68.    n=t;  
69.   }  
70.   return m;  
71.  }  
72.   
73.  void debug(Object... os){  
74.   System.err.println(Arrays.deepToString(os));  
75.  }  
76.   
77.  void print(String s){  
78.   System.out.print(s);  
79.  }  
80.   
81.  void println(String s){  
82.   System.out.println(s);  
83.  }  
84.   
85.  public static void main(String[] args){  
86.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
87.   new Main().run();  
88.  }  
89. }  

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 p, m;

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

 void solve(){
  long n1=0, d1=1;
  long n2=m, d2=1;
  for(long d=1; d<=m; d++){
   double left=1, right=m;
   for(int i=0; i<100; i++){
    double mid=(left+right)/2;
    if(mid*mid<p*d*d+EPS){
     left=mid;
    }else{
     right=mid;
    }
   }
   int n=(int)(left+EPS);
   if(n1*d<n*d1&&n*n<p*d*d){
    n1=n;
    d1=d;
   }
   if(++n<=m){
    if(p*d*d<n*n&&n*d2<n2*d){
     n2=n;
     d2=d;
    }
   }
  }
  long gcd=gcd(n1, d1);
  n1/=gcd;
  d1/=gcd;
  gcd=gcd(n2, d2);
  n2/=gcd;
  d2/=gcd;
  println(n2+"/"+d2+" "+n1+"/"+d1);
 }

 long gcd(long m, long n){
  for(; n!=0;){
   m=m%n;
   long t=m;
   m=n;
   n=t;
  }
  return m;
 }

 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();
 }
}

Aizu Online Judge

■1204 Pipeline Scheduling

再帰を用いて実際にシミュレートする．左端から詰めていくようにして，簡単な枝刈り（現時点でのサイクル数が，暫定の最短より長い場合は中断）を付け加えれば通る．

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 n, t, u;  
17.  int[][] a, b;  
18.  int ans;  
19.   
20.  void run(){  
21.   t=10;  
22.   u=5;  
23.   for(;;){  
24.    n=sc.nextInt();  
25.    if(n==0){  
26.     break;  
27.    }  
28.    a=new int[u][n];  
29.    for(int j=0; j<u; j++){  
30.     String s=sc.next();  
31.     for(int i=0; i<n; i++){  
32.      a[j][i]=s.charAt(i)=='.'?0:1;  
33.     }  
34.    }  
35.    solve();  
36.   }  
37.  }  
38.   
39.  void rec(int k, int p){  
40.   if(p>=ans){  
41.    return;  
42.   }  
43.   if(k==t+1){  
44.    ans=min(ans, p+n-1);  
45.    return;  
46.   }  
47.   for(int q=p; q<p+n; q++){  
48.    boolean f=true;  
49.    for(int j=0; j<u; j++){  
50.     for(int i=0; i<n; i++){  
51.      f&=a[j][i]==0||b[j][q+i]==0;  
52.     }  
53.    }  
54.    if(f){  
55.     for(int j=0; j<u; j++){  
56.      for(int i=0; i<n; i++){  
57.       if(a[j][i]==1){  
58.        b[j][q+i]=k;  
59.       }  
60.      }  
61.     }  
62.     rec(k+1, q+1);  
63.     for(int j=0; j<u; j++){  
64.      for(int i=0; i<n; i++){  
65.       if(a[j][i]==1){  
66.        b[j][q+i]=0;  
67.       }  
68.      }  
69.     }  
70.    }  
71.   }  
72.  }  
73.   
74.  void solve(){  
75.   ans=INF;  
76.   b=new int[u][(n+1)*(t+1)];  
77.   rec(1, 0);  
78.   println(""+ans);  
79.  }  
80.   
81.  void debug(Object... os){  
82.   System.err.println(Arrays.deepToString(os));  
83.  }  
84.   
85.  void print(String s){  
86.   System.out.print(s);  
87.  }  
88.   
89.  void println(String s){  
90.   System.out.println(s);  
91.  }  
92.   
93.  public static void main(String[] args){  
94.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
95.   new Main().run();  
96.  }  
97. }  

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 n, t, u;
 int[][] a, b;
 int ans;

 void run(){
  t=10;
  u=5;
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   a=new int[u][n];
   for(int j=0; j<u; j++){
    String s=sc.next();
    for(int i=0; i<n; i++){
     a[j][i]=s.charAt(i)=='.'?0:1;
    }
   }
   solve();
  }
 }

 void rec(int k, int p){
  if(p>=ans){
   return;
  }
  if(k==t+1){
   ans=min(ans, p+n-1);
   return;
  }
  for(int q=p; q<p+n; q++){
   boolean f=true;
   for(int j=0; j<u; j++){
    for(int i=0; i<n; i++){
     f&=a[j][i]==0||b[j][q+i]==0;
    }
   }
   if(f){
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=k;
      }
     }
    }
    rec(k+1, q+1);
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=0;
      }
     }
    }
   }
  }
 }

 void solve(){
  ans=INF;
  b=new int[u][(n+1)*(t+1)];
  rec(1, 0);
  println(""+ans);
 }

 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();
 }
}

Aizu Online Judge 1203 Napoleon's Grumble

■1203 Napoleon's Grumble

回文の中心点jを0~n-1まで動かしながら，
c_j-i,…,c_j+i
c_j-i,…,c_j+i+1
が回文となる最大のiを探す．
片っ端から回文候補をリストに入れた後，冗長のものを省く．

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.  String s;  
17.   
18.  void run(){  
19.   for(; sc.hasNextLine();){  
20.    s=sc.nextLine();  
21.    solve();  
22.   }  
23.  }  
24.   
25.  void solve(){  
26.   s=s.toUpperCase().replaceAll("[^A-Z]", "");  
27.   int n=s.length();  
28.   TreeSet<String> set=new TreeSet<String>();  
29.   for(int j=0; j<n; j++){  
30.    int i;  
31.    for(i=0; j-i>=0&&j+i<n&&s.charAt(j-i)==s.charAt(j+i); i++);  
32.    i--;  
33.    if(i>=1){  
34.     set.add(s.substring(j-i, j+i+1));  
35.    }  
36.    for(i=0; j-i>=0&&j+i+1<n&&s.charAt(j-i)==s.charAt(j+i+1); i++);  
37.    i--;  
38.    if(i>=1){  
39.     set.add(s.substring(j-i, j+i+2));  
40.    }  
41.   }  
42.   for(Iterator<String> i=set.iterator(); i.hasNext();){  
43.    String s=i.next();  
44.    for(Iterator<String> j=set.iterator(); j.hasNext();){  
45.     String t=j.next();  
46.     if((s.length()+t.length())%2==0&&t.length()>s.length()){  
47.      int k=(t.length()-s.length())/2;  
48.      if(t.substring(k, t.length()-k).equals(s)){  
49.       i.remove();  
50.       break;  
51.      }  
52.     }  
53.    }  
54.   }  
55.   for(; !set.isEmpty();){  
56.    print(set.pollFirst());  
57.    if(!set.isEmpty()){  
58.     print(" ");  
59.    }  
60.   }  
61.   println("");  
62.  }  
63.   
64.  void debug(Object... os){  
65.   System.err.println(Arrays.deepToString(os));  
66.  }  
67.   
68.  void print(String s){  
69.   System.out.print(s);  
70.  }  
71.   
72.  void println(String s){  
73.   System.out.println(s);  
74.  }  
75.   
76.  public static void main(String[] args){  
77.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
78.   new Main().run();  
79.  }  
80. }  

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;

 String s;

 void run(){
  for(; sc.hasNextLine();){
   s=sc.nextLine();
   solve();
  }
 }

 void solve(){
  s=s.toUpperCase().replaceAll("[^A-Z]", "");
  int n=s.length();
  TreeSet<String> set=new TreeSet<String>();
  for(int j=0; j<n; j++){
   int i;
   for(i=0; j-i>=0&&j+i<n&&s.charAt(j-i)==s.charAt(j+i); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+1));
   }
   for(i=0; j-i>=0&&j+i+1<n&&s.charAt(j-i)==s.charAt(j+i+1); i++);
   i--;
   if(i>=1){
    set.add(s.substring(j-i, j+i+2));
   }
  }
  for(Iterator<String> i=set.iterator(); i.hasNext();){
   String s=i.next();
   for(Iterator<String> j=set.iterator(); j.hasNext();){
    String t=j.next();
    if((s.length()+t.length())%2==0&&t.length()>s.length()){
     int k=(t.length()-s.length())/2;
     if(t.substring(k, t.length()-k).equals(s)){
      i.remove();
      break;
     }
    }
   }
  }
  for(; !set.isEmpty();){
   print(set.pollFirst());
   if(!set.isEmpty()){
    print(" ");
   }
  }
  println("");
 }

 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();
 }
}

Aizu Online Judge 1201 Lattice Practices

■1201 Lattice Practices

まず，10枚の板から5枚を選び，その5枚で構成出来るパターンを全て列挙．列挙の際，反転させても変わらない板がある場合があるので，重複を考慮する必要がある．それぞれのパターンに対応するパターンを残りの5枚で構成できうるかを判定する． 10個から5個選ぶ…₁₀P₅=30240 反転の種類…2⁵=32

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[] a, rev;  
17.  int n, m;  
18.   
19.  void run(){  
20.   n=10;  
21.   m=n/2;  
22.   a=new int[n];  
23.   rev=new int[1<<m];  
24.   for(int i=0; i<1<<m; i++){  
25.    int x=i;  
26.    x=(x&0x55555555)<<1|(x>>1)&0x55555555;  
27.    x=(x&0x33333333)<<2|(x>>2)&0x33333333;  
28.    x=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;  
29.    x=(x<<24)|((x&0xff00)<<8)|((x>>8)&0xff00)|(x>>24);  
30.    rev[i]=(int)(x>>(32-m))&((1<<m)-1);  
31.   }  
32.   
33.   for(;;){  
34.    for(int i=0; i<n; i++){  
35.     String s=sc.next();  
36.     if(s.equals("END")){  
37.      return;  
38.     }  
39.     a[i]=Integer.parseInt(s, 2);  
40.    }  
41.    solve();  
42.   }  
43.  }  
44.   
45.  void solve(){  
46.   int ans=0;  
47.   int[] b=new int[m];  
48.   int[] c=new int[m];  
49.   int comb=(1<<m)-1;  
50.   boolean[] used=new boolean[m];  
51.   
52.   for(; comb<1<<n;){  
53.    // 2^(反転させても同じものの個数)で割る  
54.    int div=1;  
55.    for(int i=0, j=0, k=0; k<10; k++){  
56.     if((comb>>k&1)==1){  
57.      b[i++]=a[k];  
58.      if(rev[a[k]]==a[k]){  
59.       div*=2;  
60.      }  
61.     }else{  
62.      c[j++]=a[k];  
63.     }  
64.    }  
65.   
66.    Arrays.sort(b);  
67.    int sum=0;  
68.    for(;;){  
69.     // 2^n通り反転させる  
70.     for(int sup=0; sup<1<<m; sup++){  
71.      for(int i=0; i<m; i++){  
72.       if((sup>>i&1)==1){  
73.        b[i]=rev[b[i]];  
74.       }  
75.      }  
76.      // bの並びをcで構築できるか  
77.      Arrays.fill(used, false);  
78.      sum++;  
79.      for(int i=0; i<m; i++){  
80.       int bits=0;  
81.       for(int j=0; j<m; j++){  
82.        bits=(bits<<1)|(b[j]>>i&1);  
83.       }  
84.       int k=-1;  
85.       for(int j=0; j<m; j++){  
86.        if(!used[j]  
87.          &&((c[j]^bits)==(1<<m)-1||(rev[c[j]]^bits)==(1<<m)-1)){  
88.         k=j;  
89.        }  
90.       }  
91.       if(k>=0){  
92.        used[k]=true;  
93.       }else{  
94.        sum--;  
95.        break;  
96.       }  
97.      }  
98.      for(int i=0; i<m; i++){  
99.       if((sup>>i&1)==1){  
100.        b[i]=rev[b[i]];  
101.       }  
102.      }  
103.     }  
104.     if(!nextPermutation(b)){  
105.      break;  
106.     }  
107.    }  
108.    ans+=sum/div;  
109.   
110.    int x=comb&-comb, y=comb+x;  
111.    comb=((comb&~y)/x>>1)|y;  
112.   }  
113.   ans/=8; // 鏡像反転*回転  
114.   println(""+ans);  
115.  }  
116.   
117.  boolean nextPermutation(int[] is){  
118.   int n=is.length;  
119.   for(int i=n-1; i>0; i--){  
120.    if(is[i-1]<is[i]){  
121.     int j=n;  
122.     while(is[i-1]>=is[--j]);  
123.     swap(is, i-1, j);  
124.     rev(is, i, n);  
125.     return true;  
126.    }  
127.   }  
128.   rev(is, 0, n);  
129.   return false;  
130.  }  
131.   
132.  void swap(int[] is, int i, int j){  
133.   int t=is[i];  
134.   is[i]=is[j];  
135.   is[j]=t;  
136.  }  
137.   
138.  void rev(int[] is, int i, int j){  
139.   for(j--; i<j; i++, j--){  
140.    int t=is[i];  
141.    is[i]=is[j];  
142.    is[j]=t;  
143.   }  
144.  }  
145.   
146.  void debug(Object... os){  
147.   System.err.println(Arrays.deepToString(os));  
148.  }  
149.   
150.  void print(String s){  
151.   System.out.print(s);  
152.  }  
153.   
154.  void println(String s){  
155.   System.out.println(s);  
156.  }  
157.   
158.  public static void main(String[] args){  
159.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
160.   new Main().run();  
161.  }  
162. }  

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[] a, rev;
 int n, m;

 void run(){
  n=10;
  m=n/2;
  a=new int[n];
  rev=new int[1<<m];
  for(int i=0; i<1<<m; i++){
   int x=i;
   x=(x&0x55555555)<<1|(x>>1)&0x55555555;
   x=(x&0x33333333)<<2|(x>>2)&0x33333333;
   x=(x&0x0f0f0f0f)<<4|(x>>4)&0x0f0f0f0f;
   x=(x<<24)|((x&0xff00)<<8)|((x>>8)&0xff00)|(x>>24);
   rev[i]=(int)(x>>(32-m))&((1<<m)-1);
  }

  for(;;){
   for(int i=0; i<n; i++){
    String s=sc.next();
    if(s.equals("END")){
     return;
    }
    a[i]=Integer.parseInt(s, 2);
   }
   solve();
  }
 }

 void solve(){
  int ans=0;
  int[] b=new int[m];
  int[] c=new int[m];
  int comb=(1<<m)-1;
  boolean[] used=new boolean[m];

  for(; comb<1<<n;){
   // 2^(反転させても同じものの個数)で割る
   int div=1;
   for(int i=0, j=0, k=0; k<10; k++){
    if((comb>>k&1)==1){
     b[i++]=a[k];
     if(rev[a[k]]==a[k]){
      div*=2;
     }
    }else{
     c[j++]=a[k];
    }
   }

   Arrays.sort(b);
   int sum=0;
   for(;;){
    // 2^n通り反転させる
    for(int sup=0; sup<1<<m; sup++){
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
     // bの並びをcで構築できるか
     Arrays.fill(used, false);
     sum++;
     for(int i=0; i<m; i++){
      int bits=0;
      for(int j=0; j<m; j++){
       bits=(bits<<1)|(b[j]>>i&1);
      }
      int k=-1;
      for(int j=0; j<m; j++){
       if(!used[j]
         &&((c[j]^bits)==(1<<m)-1||(rev[c[j]]^bits)==(1<<m)-1)){
        k=j;
       }
      }
      if(k>=0){
       used[k]=true;
      }else{
       sum--;
       break;
      }
     }
     for(int i=0; i<m; i++){
      if((sup>>i&1)==1){
       b[i]=rev[b[i]];
      }
     }
    }
    if(!nextPermutation(b)){
     break;
    }
   }
   ans+=sum/div;

   int x=comb&-comb, y=comb+x;
   comb=((comb&~y)/x>>1)|y;
  }
  ans/=8; // 鏡像反転*回転
  println(""+ans);
 }

 boolean nextPermutation(int[] is){
  int n=is.length;
  for(int i=n-1; i>0; i--){
   if(is[i-1]<is[i]){
    int j=n;
    while(is[i-1]>=is[--j]);
    swap(is, i-1, j);
    rev(is, i, n);
    return true;
   }
  }
  rev(is, 0, n);
  return false;
 }

 void swap(int[] is, int i, int j){
  int t=is[i];
  is[i]=is[j];
  is[j]=t;
 }

 void rev(int[] is, int i, int j){
  for(j--; i<j; i++, j--){
   int t=is[i];
   is[i]=is[j];
   is[j]=t;
  }
 }

 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();
 }
}