2011年2月24日木曜日

Aizu Online Judge 0185 Goldbach's Conjecture II

■0185 Goldbach's Conjecture II

入力が最大で106なので，最初にエラトステネスの篩で素数を生成しておくのが無難．

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 max=1000000;  
  18.  int[] prime;  
  19.  boolean[] isPrime;  
  20.   
  21.  void run(){  
  22.   int p=0;  
  23.   prime=new int[max];  
  24.   isPrime=new boolean[max+1];  
  25.   Arrays.fill(isPrime, true);  
  26.   isPrime[0]=isPrime[1]=false;  
  27.   for(int i=2; i<=max; i++){  
  28.    if(isPrime[i]){  
  29.     prime[p++]=i;  
  30.     for(int j=2*i; j<=max; j+=i){  
  31.      isPrime[j]=false;  
  32.     }  
  33.    }  
  34.   }  
  35.   
  36.   for(;;){  
  37.    n=sc.nextInt();  
  38.    if(n==0){  
  39.     break;  
  40.    }  
  41.    int ans=0;  
  42.    for(int i=0; i<p; i++){  
  43.     if(prime[i]>n/2){  
  44.      break;  
  45.     }  
  46.     if(isPrime[n-prime[i]]){  
  47.      ans++;  
  48.     }  
  49.    }  
  50.    println(""+ans);  
  51.   }  
  52.  }  
  53.   
  54.  void debug(Object... os){  
  55.   System.err.println(Arrays.deepToString(os));  
  56.  }  
  57.   
  58.  void print(String s){  
  59.   System.out.print(s);  
  60.  }  
  61.   
  62.  void println(String s){  
  63.   System.out.println(s);  
  64.  }  
  65.   
  66.  public static void main(String[] args){  
  67.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  68.   new Main().run();  
  69.  }  
  70. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0184 Tsuruga Castle

■0184 Tsuruga Castle

やるだけ．出力量がかなり多いので，バッファに貯めて最後に出力した．

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.   for(;;){  
  18.    int n=sc.nextInt();  
  19.    if(n==0){  
  20.     break;  
  21.    }  
  22.    int[] h=new int[7];  
  23.    for(int i=0; i<n; i++){  
  24.     int a=sc.nextInt();  
  25.     for(int k=0; k<7; k++){  
  26.      if(a<(k+1)*10||k==6){  
  27.       h[k]++;  
  28.       break;  
  29.      }  
  30.     }  
  31.    }  
  32.    for(int i=0; i<7; i++){  
  33.     println(""+h[i]);  
  34.    }  
  35.   }  
  36.   System.out.flush();  
  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. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0183 Black-and-White

■0183 Black-and-White

やるだけ．

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;  
  17.  int n;  
  18.   
  19.  void run(){  
  20.   n=3;  
  21.   for(;;){  
  22.    a=new int[n][n];  
  23.    for(int j=0; j<n; j++){  
  24.     String s=sc.next();  
  25.     if(s.equals("0")){  
  26.      return;  
  27.     }  
  28.     for(int i=0; i<n; i++){  
  29.      switch(s.charAt(i)){  
  30.      case 'b':  
  31.       a[j][i]=0;  
  32.       break;  
  33.      case 'w':  
  34.       a[j][i]=1;  
  35.       break;  
  36.      case '+':  
  37.       a[j][i]=-1;  
  38.       break;  
  39.      }  
  40.     }  
  41.    }  
  42.    solve();  
  43.   }  
  44.  }  
  45.   
  46.  void solve(){  
  47.   if(check(0)){  
  48.    println("b");  
  49.   }else if(check(1)){  
  50.    println("w");  
  51.   }else{  
  52.    println("NA");  
  53.   }  
  54.  }  
  55.   
  56.  boolean check(int e){  
  57.   boolean f=false;  
  58.   for(int j=0; j<n; j++){  
  59.    boolean f1=true, f2=true;  
  60.    for(int i=0; i<n; i++){  
  61.     f1&=a[j][i]==e;  
  62.     f2&=a[i][j]==e;  
  63.    }  
  64.    f|=f1|f2;  
  65.   }  
  66.   boolean f1=true, f2=true;  
  67.   for(int i=0; i<n; i++){  
  68.    f1&=a[i][i]==e;  
  69.    f2&=a[i][n-1-i]==e;  
  70.   }  
  71.   return f|f1|f2;  
  72.  }  
  73.   
  74.  void debug(Object... os){  
  75.   System.err.println(Arrays.deepToString(os));  
  76.  }  
  77.   
  78.  void print(String s){  
  79.   System.out.print(s);  
  80.  }  
  81.   
  82.  void println(String s){  
  83.   System.out.println(s);  
  84.  }  
  85.   
  86.  public static void main(String[] args){  
  87.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  88.   new Main().run();  
  89.  }  
  90. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0181 Persistence

■0181 Persistence

二分探索．

本棚の幅をbとし，幅bの本棚に全て本を収納出来ることをC(b)で表す．
この問題における答えは，C(b)となる最小のb(=bmin)であり，C(b)であるかどうかは容易に求まる，かつb<bminなるbについては，C(b)は成立しないので二分探索を適用することが出来る．
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.   
  19.  void run(){  
  20.   for(;;){  
  21.    m=sc.nextInt();  
  22.    n=sc.nextInt();  
  23.    if((m|n)==0){  
  24.     break;  
  25.    }  
  26.    a=new int[n];  
  27.    for(int i=0; i<n; i++){  
  28.     a[i]=sc.nextInt();  
  29.    }  
  30.    solve();  
  31.   }  
  32.  }  
  33.   
  34.  void solve(){  
  35.   int left=0, right=1500000;  
  36.   for(int i=0; i<100; i++){  
  37.    int mid=(left+right)/2;  
  38.    if(check(mid)){  
  39.     right=mid;  
  40.    }else{  
  41.     left=mid;  
  42.    }  
  43.   }  
  44.   println(""+right);  
  45.  }  
  46.   
  47.  boolean check(int b){  
  48.   int d=1;  
  49.   int sum=0;  
  50.   for(int i=0; i<n; i++){  
  51.    if(a[i]>b){  
  52.     return false;  
  53.    }  
  54.    sum+=a[i];  
  55.    if(sum>b){  
  56.     sum=a[i];  
  57.     d++;  
  58.    }  
  59.   }  
  60.   return d<=m;  
  61.  }  
  62.   
  63.  void debug(Object... os){  
  64.   System.err.println(Arrays.deepToString(os));  
  65.  }  
  66.   
  67.  void print(String s){  
  68.   System.out.print(s);  
  69.  }  
  70.   
  71.  void println(String s){  
  72.   System.out.println(s);  
  73.  }  
  74.   
  75.  public static void main(String[] args){  
  76.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  77.   new Main().run();  
  78.  }  
  79. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0180 Stellar Performance of the Debunkey Family

■0180 Stellar Performance of the Debunkey Family

最小全域木．

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.  LinkedList<E> list;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    n=sc.nextInt();  
  22.    m=sc.nextInt();  
  23.    if((n|m)==0){  
  24.     break;  
  25.    }  
  26.    list=new LinkedList<E>();  
  27.    for(int i=0; i<m; i++){  
  28.     int a=sc.nextInt();  
  29.     int b=sc.nextInt();  
  30.     int cost=sc.nextInt();  
  31.     list.add(new E(a, b, cost));  
  32.    }  
  33.    solve();  
  34.   }  
  35.  }  
  36.   
  37.  void solve(){  
  38.   E[] es=list.toArray(new E[0]);  
  39.   Arrays.sort(es);  
  40.   init();  
  41.   int wt=0;  
  42.   for(E e : es){  
  43.    if(find(e.v1)!=find(e.v2)){  
  44.     union(e.v1, e.v2);  
  45.     wt+=e.w;  
  46.    }  
  47.   }  
  48.   println(""+wt);  
  49.  }  
  50.   
  51.  class E implements Comparable<E>{  
  52.   int v1, v2, w;  
  53.   
  54.   E(int v1, int v2, int w){  
  55.    this.v1=v1;  
  56.    this.v2=v2;  
  57.    this.w=w;  
  58.   }  
  59.   
  60.   @Override  
  61.   public int compareTo(E e){  
  62.    return w-e.w;  
  63.   }  
  64.  }  
  65.   
  66.  int[] p, rank;  
  67.   
  68.  void init(){  
  69.   p=new int[n];  
  70.   rank=new int[n];  
  71.   for(int i=0; i<n; i++){  
  72.    p[i]=i;  
  73.    rank[i]=0;  
  74.   }  
  75.  }  
  76.   
  77.  int find(int x){  
  78.   if(p[x]==x)  
  79.    return x;  
  80.   else  
  81.    return p[x]=find(p[x]);  
  82.  }  
  83.   
  84.  void union(int x, int y){  
  85.   x=find(x);  
  86.   y=find(y);  
  87.   if(rank[x]>rank[y]){  
  88.    p[y]=x;  
  89.   }else{  
  90.    p[x]=y;  
  91.    if(rank[x]==rank[y])  
  92.     rank[y]++;  
  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. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0179 Mysterious Worm

■0179 Mysterious Worm

深さ優先探索．同じ状態が何度も発生しないように，既に出た状態を集合に突っ込んでおくと良い(ただし，計算量がO(logn)であるものを用いないと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.  String worm;  
  17.   
  18.  void run(){  
  19.   for(;;){  
  20.    worm=sc.next();  
  21.    if(worm.equals("0")){  
  22.     break;  
  23.    }  
  24.    solve();  
  25.   }  
  26.  }  
  27.   
  28.  void solve(){  
  29.   LinkedList<String> que=new LinkedList<String>();  
  30.   TreeSet<String> set=new TreeSet<String>();  
  31.   HashMap<String, Integer> map=new HashMap<String, Integer>();  
  32.   que.add(worm);  
  33.   set.add(worm);  
  34.   map.put(worm, 0);  
  35.   for(; !que.isEmpty();){  
  36.    String s=que.poll();  
  37.    boolean f=true;  
  38.    for(int i=0; i<s.length(); i++){  
  39.     f&=s.charAt(0)==s.charAt(i);  
  40.    }  
  41.    if(f){  
  42.     println(""+map.get(s));  
  43.     return;  
  44.    }  
  45.    for(String t : next(s)){  
  46.     if(!set.contains(t)){  
  47.      que.offer(t);  
  48.      set.add(t);  
  49.      map.put(t, map.get(s)+1);  
  50.     }  
  51.    }  
  52.   }  
  53.   println("NA");  
  54.  }  
  55.   
  56.  LinkedList<String> next(String s){  
  57.   LinkedList<String> list=new LinkedList<String>();  
  58.   for(int i=0; i<s.length()-1; i++){  
  59.    if(s.charAt(i)!=s.charAt(i+1)){  
  60.     char c='*';  
  61.     switch(s.charAt(i)+s.charAt(i+1)){  
  62.     case 'r'+'g':  
  63.      c='b';  
  64.      break;  
  65.     case 'g'+'b':  
  66.      c='r';  
  67.      break;  
  68.     case 'b'+'r':  
  69.      c='g';  
  70.      break;  
  71.     }  
  72.     list.add(s.substring(0, i)+c+c  
  73.       +(i<s.length()-2?s.substring(i+2, s.length()):""));  
  74.    }  
  75.   }  
  76.   return list;  
  77.  }  
  78.   
  79.  void debug(Object... os){  
  80.   System.err.println(Arrays.deepToString(os));  
  81.  }  
  82.   
  83.  void print(String s){  
  84.   System.out.print(s);  
  85.  }  
  86.   
  87.  void println(String s){  
  88.   System.out.println(s);  
  89.  }  
  90.   
  91.  public static void main(String[] args){  
  92.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  93.   new Main().run();  
  94.  }  
  95. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年2月22日火曜日

Aizu Online Judge 0176 What Color?

■0176 What Color?

やるだけ．

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.   for(;;){  
  18.    String s=sc.next();  
  19.    if(s.equals("0")){  
  20.     break;  
  21.    }  
  22.    int r=Integer.parseInt(s.substring(1, 3), 16);  
  23.    int g=Integer.parseInt(s.substring(3, 5), 16);  
  24.    int b=Integer.parseInt(s.substring(5, 7), 16);  
  25.    int k=-1;  
  26.    double min=INF;  
  27.    for(int i=0; i<8; i++){  
  28.     int dr=r-(i/4)*0xff;  
  29.     int dg=g-((i/2)%2)*0xff;  
  30.     int db=b-(i%2)*0xff;  
  31.     double d=Math.sqrt(dr*dr+dg*dg+db*db);  
  32.     if(d+EPS<min){  
  33.      k=i;  
  34.      min=d;  
  35.     }  
  36.    }  
  37.    println(new String[]{"black", "blue", "lime", "aqua", "red",  
  38.      "fuchsia", "yellow", "white",}[k]);  
  39.   }  
  40.  }  
  41.   
  42.  void debug(Object... os){  
  43.   System.err.println(Arrays.deepToString(os));  
  44.  }  
  45.   
  46.  void print(String s){  
  47.   System.out.print(s);  
  48.  }  
  49.   
  50.  void println(String s){  
  51.   System.out.println(s);  
  52.  }  
  53.   
  54.  public static void main(String[] args){  
  55.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  56.   new Main().run();  
  57.  }  
  58. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0175 A King in Hawaii

■0175 A King in Hawaii

やるだけ．

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.   for(;;){  
  18.    int n=sc.nextInt();  
  19.    if(n==-1){  
  20.     break;  
  21.    }  
  22.    println(Integer.toString(n, 4));  
  23.   }  
  24.  }  
  25.   
  26.  void debug(Object... os){  
  27.   System.err.println(Arrays.deepToString(os));  
  28.  }  
  29.   
  30.  void print(String s){  
  31.   System.out.print(s);  
  32.  }  
  33.   
  34.  void println(String s){  
  35.   System.out.println(s);  
  36.  }  
  37.   
  38.  public static void main(String[] args){  
  39.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  40.   new Main().run();  
  41.  }  
  42. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0174 Badminton

■0174 Badminton

やるだけ．

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[] ss;  
  17.   
  18.  void run(){  
  19.   ss=new String[3];  
  20.   for(;;){  
  21.    ss[0]=sc.next();  
  22.    if(ss[0].equals("0")){  
  23.     break;  
  24.    }  
  25.    ss[1]=sc.next();  
  26.    ss[2]=sc.next();  
  27.    solve();  
  28.   }  
  29.  }  
  30.   
  31.  void solve(){  
  32.   for(int j=0; j<3; j++){  
  33.    int a=0, b=0;  
  34.    for(int i=0; i<ss[j].length()-1; i++){  
  35.     if(ss[j].charAt(i+1)=='A'){  
  36.      a++;  
  37.     }else{  
  38.      b++;  
  39.     }  
  40.    }  
  41.    if((a+1==11&&b<=9)||(a+1>=12&&a+1==b+2)){  
  42.     a++;  
  43.    }else{  
  44.     b++;  
  45.    }  
  46.    println(a+" "+b);  
  47.   }  
  48.  }  
  49.   
  50.  void debug(Object... os){  
  51.   System.err.println(Arrays.deepToString(os));  
  52.  }  
  53.   
  54.  void print(String s){  
  55.   System.out.print(s);  
  56.  }  
  57.   
  58.  void println(String s){  
  59.   System.out.println(s);  
  60.  }  
  61.   
  62.  public static void main(String[] args){  
  63.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  64.   new Main().run();  
  65.  }  
  66. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0173 Haunted House

■0173 Haunted House

やるだけ．

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.   for(int i=0; i<9; i++){  
  18.    String s=sc.next();  
  19.    int a=sc.nextInt();  
  20.    int b=sc.nextInt();  
  21.    println(s+" "+(a+b)+" "+(a*200+b*300));  
  22.   }  
  23.  }  
  24.   
  25.  void debug(Object... os){  
  26.   System.err.println(Arrays.deepToString(os));  
  27.  }  
  28.   
  29.  void print(String s){  
  30.   System.out.print(s);  
  31.  }  
  32.   
  33.  void println(String s){  
  34.   System.out.println(s);  
  35.  }  
  36.   
  37.  public static void main(String[] args){  
  38.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  39.   new Main().run();  
  40.  }  
  41. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0170 Lunch

■0170 Lunch

全探索．

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.  String[] f;  
  18.  int[] w, s;  
  19.  int[] a, best;  
  20.  double bestG;  
  21.   
  22.  void run(){  
  23.   for(;;){  
  24.    n=sc.nextInt();  
  25.    if(n==0){  
  26.     break;  
  27.    }  
  28.    f=new String[n];  
  29.    w=new int[n];  
  30.    s=new int[n];  
  31.    for(int i=0; i<n; i++){  
  32.     f[i]=sc.next();  
  33.     w[i]=sc.nextInt();  
  34.     s[i]=sc.nextInt();  
  35.    }  
  36.    solve();  
  37.   }  
  38.  }  
  39.   
  40.  void solve(){  
  41.   a=new int[n];  
  42.   best=new int[n];  
  43.   for(int i=0; i<n; i++){  
  44.    a[i]=i;  
  45.   }  
  46.   bestG=INF;  
  47.   rec(0);  
  48.   for(int e : best){  
  49.    println(f[e]);  
  50.   }  
  51.  }  
  52.   
  53.  void rec(int j){  
  54.   if(j==n){  
  55.    int sumW=0;  
  56.    int nW=0;  
  57.    for(int i=n-1; i>=0; i--){  
  58.     if(s[a[i]]<sumW){  
  59.      return;  
  60.     }  
  61.     sumW+=w[a[i]];  
  62.     nW+=(i+1)*w[a[i]];  
  63.    }  
  64.    double g=(double)nW/sumW;  
  65.    if(g+EPS<bestG){  
  66.     System.arraycopy(a, 0, best, 0, n);  
  67.     bestG=g;  
  68.    }  
  69.    return;  
  70.   }  
  71.   
  72.   for(int i=j; i<n; i++){  
  73.    int t=a[i];  
  74.    a[i]=a[j];  
  75.    a[j]=t;  
  76.    rec(j+1);  
  77.    t=a[i];  
  78.    a[i]=a[j];  
  79.    a[j]=t;  
  80.   }  
  81.  }  
  82.   
  83.  void debug(Object... os){  
  84.   System.err.println(Arrays.deepToString(os));  
  85.  }  
  86.   
  87.  void print(String s){  
  88.   System.out.print(s);  
  89.  }  
  90.   
  91.  void println(String s){  
  92.   System.out.println(s);  
  93.  }  
  94.   
  95.  public static void main(String[] args){  
  96.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  97.   new Main().run();  
  98.  }  
  99. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0169 Blackjack

■0169 Blackjack

やるだけ．

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.   for(;;){  
  18.    Scanner s=new Scanner(sc.nextLine());  
  19.    int count1=0;  
  20.    int sum=0;  
  21.    for(; s.hasNext();){  
  22.     int a=s.nextInt();  
  23.     if(a==0){  
  24.      return;  
  25.     }  
  26.     if(a>10){  
  27.      sum+=10;  
  28.     }else{  
  29.      sum+=a;  
  30.     }  
  31.     if(a==1){  
  32.      count1++;  
  33.     }  
  34.    }  
  35.    int ans=0;  
  36.    for(int i=0; i<=count1; i++){  
  37.     if(sum<=21){  
  38.      ans=sum;  
  39.     }  
  40.     sum+=10;  
  41.    }  
  42.    println(""+ans);  
  43.   }  
  44.  }  
  45.   
  46.  void debug(Object... os){  
  47.   System.err.println(Arrays.deepToString(os));  
  48.  }  
  49.   
  50.  void print(String s){  
  51.   System.out.print(s);  
  52.  }  
  53.   
  54.  void println(String s){  
  55.   System.out.println(s);  
  56.  }  
  57.   
  58.  public static void main(String[] args){  
  59.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  60.   new Main().run();  
  61.  }  
  62. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0168 Kannondou

■0168 Kannondou

動的計画法．

dp[段数]=組み合わせ
dp[0]=1
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
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.   for(;;){  
  18.    int n=sc.nextInt();  
  19.    if(n==0){  
  20.     break;  
  21.    }  
  22.    int[] dp=new int[n+4];  
  23.    dp[0]=1;  
  24.    for(int i=0; i<=n; i++){  
  25.     dp[i+1]+=dp[i];  
  26.     dp[i+2]+=dp[i];  
  27.     dp[i+3]+=dp[i];  
  28.    }  
  29.    int ans=((dp[n]+9)/10+364)/365;  
  30.    println(ans+"");  
  31.   }  
  32.  }  
  33.   
  34.  void debug(Object... os){  
  35.   System.err.println(Arrays.deepToString(os));  
  36.  }  
  37.   
  38.  void print(String s){  
  39.   System.out.print(s);  
  40.  }  
  41.   
  42.  void println(String s){  
  43.   System.out.println(s);  
  44.  }  
  45.   
  46.  public static void main(String[] args){  
  47.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  48.   new Main().run();  
  49.  }  
  50. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0167 Bubble Sort

■0167 Bubble Sort

やるだけ．

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[] a;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    n=sc.nextInt();  
  22.    if(n==0){  
  23.     break;  
  24.    }  
  25.    a=new int[n];  
  26.    for(int i=0; i<n; i++){  
  27.     a[i]=sc.nextInt();  
  28.    }  
  29.    solve();  
  30.   }  
  31.  }  
  32.   
  33.  void solve(){  
  34.   int swap=0;  
  35.   for(int j=n-1; j>=0; j--){  
  36.    for(int i=0; i<j; i++){  
  37.     if(a[i]>a[i+1]){  
  38.      int t=a[i];  
  39.      a[i]=a[i+1];  
  40.      a[i+1]=t;  
  41.      swap++;  
  42.     }  
  43.    }  
  44.   }  
  45.   println(""+swap);  
  46.  }  
  47.   
  48.  void debug(Object... os){  
  49.   System.err.println(Arrays.deepToString(os));  
  50.  }  
  51.   
  52.  void print(String s){  
  53.   System.out.print(s);  
  54.  }  
  55.   
  56.  void println(String s){  
  57.   System.out.println(s);  
  58.  }  
  59.   
  60.  public static void main(String[] args){  
  61.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  62.   new Main().run();  
  63.  }  
  64. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0166 Area of Polygon

■0166 Area of Polygon

中心角θの三角形の面積は，2sin(θ/2)

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.   for(;;){  
  18.    double[] area=new double[2];  
  19.    for(int j=0; j<2; j++){  
  20.     int m=sc.nextInt();  
  21.     if(m==0){  
  22.      return;  
  23.     }  
  24.     int sum=0;  
  25.     for(int i=0; i<m-1; i++){  
  26.      int deg=sc.nextInt();  
  27.      area[j]+=Math.sin(Math.toRadians(deg/2))*2;  
  28.      sum+=deg;  
  29.     }  
  30.     area[j]+=Math.sin(Math.toRadians(360-sum))/2;  
  31.    }  
  32.    if(area[0]>area[1]+EPS){  
  33.     println("1");  
  34.    }else if(area[0]+EPS<area[1]){  
  35.     println("2");  
  36.    }else{  
  37.     println("0");  
  38.    }  
  39.   }  
  40.  }  
  41.   
  42.  void debug(Object... os){  
  43.   System.err.println(Arrays.deepToString(os));  
  44.  }  
  45.   
  46.  void print(String s){  
  47.   System.out.print(s);  
  48.  }  
  49.   
  50.  void println(String s){  
  51.   System.out.println(s);  
  52.  }  
  53.   
  54.  public static void main(String[] args){  
  55.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  56.   new Main().run();  
  57.  }  
  58. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0164 Ohajiki Game

■0164 Ohajiki Game

やるだけ．

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.   for(;;){  
  18.    int n=sc.nextInt();  
  19.    if(n==0){  
  20.     break;  
  21.    }  
  22.    int[] a=new int[n];  
  23.    for(int i=0; i<n; i++){  
  24.     a[i]=sc.nextInt();  
  25.    }  
  26.    for(int r=31, i=0;; i=(i+1)%n){  
  27.     println(""+r);  
  28.     r-=a[i];  
  29.     if(r<=0){  
  30.      println("0");  
  31.      break;  
  32.     }  
  33.     println(""+r);  
  34.     r-=(r-1)%5;  
  35.    }  
  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. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0163 Highway Toll

■0163 Highway Toll

やるだけ．

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[][] d={  
  18.     //  
  19.     {0, 6, 13, 18, 23, 43, 58}, //  
  20.     {6, 0, 7, 12, 17, 37, 52}, //  
  21.     {13, 7, 0, 5, 10, 30, 45}, //  
  22.     {18, 12, 5, 0, 5, 25, 40}, //  
  23.     {23, 17, 10, 5, 0, 20, 35}, //  
  24.     {43, 37, 30, 25, 20, 0, 15}, //  
  25.     {58, 52, 45, 40, 35, 15, 0}, //  
  26.   };  
  27.   int[][] c={  
  28.     //  
  29.     {0, 300, 500, 600, 700, 1350, 1650}, //  
  30.     {300, 0, 350, 450, 600, 1150, 1500}, //  
  31.     {500, 350, 0, 250, 400, 1000, 1350}, //  
  32.     {600, 450, 250, 0, 250, 850, 1300}, //  
  33.     {700, 600, 400, 250, 0, 600, 1150}, //  
  34.     {1350, 1150, 1000, 850, 600, 0, 500}, //  
  35.     {1650, 1500, 1350, 1300, 1150, 500, 0},}; //  
  36.   
  37.   for(;;){  
  38.    int ic1=sc.nextInt()-1;  
  39.    if(ic1==-1){  
  40.     break;  
  41.    }  
  42.    int h1=sc.nextInt();  
  43.    int m1=sc.nextInt()+h1*60;  
  44.    int ic2=sc.nextInt()-1;  
  45.    int h2=sc.nextInt();  
  46.    int m2=sc.nextInt()+h2*60;  
  47.    int s=17*60+30;  
  48.    int g=19*60+30;  
  49.    int ans=c[ic1][ic2];  
  50.    if((s<=m1&&m1<=g)||(s<=m2&&m2<=g)){  
  51.     if(d[ic1][ic2]<=40){  
  52.      // 半額  
  53.      ans=(int)(Math.ceil(ans/2./50.)*50+EPS);  
  54.     }  
  55.    }  
  56.    println(""+ans);  
  57.   }  
  58.  }  
  59.   
  60.  void debug(Object... os){  
  61.   System.err.println(Arrays.deepToString(os));  
  62.  }  
  63.   
  64.  void print(String s){  
  65.   System.out.print(s);  
  66.  }  
  67.   
  68.  void println(String s){  
  69.   System.out.println(s);  
  70.  }  
  71.   
  72.  public static void main(String[] args){  
  73.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  74.   new Main().run();  
  75.  }  
  76. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0144 Packet Transportation

■0144 Packet Transportation

BFSするだけ．

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 start, goal, ttl;  
  18.  LinkedList<Integer>[] graph;  
  19.   
  20.  @SuppressWarnings("unchecked")  
  21.  void run(){  
  22.   n=sc.nextInt();  
  23.   graph=new LinkedList[n];  
  24.   for(int j=0; j<n; j++){  
  25.    int u=sc.nextInt()-1;// ルータ番号  
  26.    int m=sc.nextInt();  
  27.    graph[u]=new LinkedList<Integer>();  
  28.    for(int i=0; i<m; i++){  
  29.     int v=sc.nextInt()-1;  
  30.     graph[u].add(v);  
  31.    }  
  32.   }  
  33.   int p=sc.nextInt();  
  34.   for(int i=0; i<p; i++){  
  35.    start=sc.nextInt()-1;  
  36.    goal=sc.nextInt()-1;  
  37.    ttl=sc.nextInt();  
  38.    solve();  
  39.   }  
  40.  }  
  41.   
  42.  void solve(){  
  43.   LinkedList<Integer> que=new LinkedList<Integer>();  
  44.   boolean[] visited=new boolean[n];  
  45.   int[] d=new int[n];  
  46.   Arrays.fill(d, INF);  
  47.   que.offer(start);  
  48.   d[start]=1;  
  49.   visited[start]=true;  
  50.   for(; !que.isEmpty();){  
  51.    int u=que.poll();  
  52.    for(int v : graph[u]){  
  53.     if(!visited[v]){  
  54.      que.offer(v);  
  55.      d[v]=d[u]+1;  
  56.      visited[v]=true;  
  57.     }  
  58.    }  
  59.   }  
  60.   if(d[goal]<=ttl){  
  61.    println(""+d[goal]);  
  62.   }else{  
  63.    println("NA");  
  64.   }  
  65.  }  
  66.   
  67.  void debug(Object... os){  
  68.   System.err.println(Arrays.deepToString(os));  
  69.  }  
  70.   
  71.  void print(String s){  
  72.   System.out.print(s);  
  73.  }  
  74.   
  75.  void println(String s){  
  76.   System.out.println(s);  
  77.  }  
  78.   
  79.  public static void main(String[] args){  
  80.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  81.   new Main().run();  
  82.  }  
  83. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0143 Altair and Vega

■0143 Altair and Vega

牽牛と織女を結ぶ線分が，三角形を構成する線分と何回交差するかで答えは決まる．

0，2回：遮断されていない
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.  int n;  
  17.  P ps1, ps2, ps3;  
  18.  P k, s;  
  19.   
  20.  void run(){  
  21.   n=sc.nextInt();  
  22.   for(int i=0; i<n; i++){  
  23.    int xp1=sc.nextInt();  
  24.    int yp1=sc.nextInt();  
  25.    int xp2=sc.nextInt();  
  26.    int yp2=sc.nextInt();  
  27.    int xp3=sc.nextInt();  
  28.    int yp3=sc.nextInt();  
  29.    int xk=sc.nextInt();  
  30.    int yk=sc.nextInt();  
  31.    int xs=sc.nextInt();  
  32.    int ys=sc.nextInt();  
  33.    ps1=new P(xp1, yp1);  
  34.    ps2=new P(xp2, yp2);  
  35.    ps3=new P(xp3, yp3);  
  36.    k=new P(xk, yk);  
  37.    s=new P(xs, ys);  
  38.    solve();  
  39.   }  
  40.  }  
  41.   
  42.  void solve(){  
  43.   if(crsSS(k, s, ps1, ps2)^crsSS(k, s, ps2, ps3)^crsSS(k, s, ps3, ps1)){  
  44.    println("OK");  
  45.   }else{  
  46.    println("NG");  
  47.   }  
  48.  }  
  49.   
  50.  boolean crsSS(P p1, P p2, P q1, P q2){  
  51.   if(max(p1.x, p2.x)+EPS<min(q1.x, q2.x))  
  52.    return false;  
  53.   if(max(q1.x, q2.x)+EPS<min(p1.x, p2.x))  
  54.    return false;  
  55.   if(max(p1.y, p2.y)+EPS<min(q1.y, q2.y))  
  56.    return false;  
  57.   if(max(q1.y, q2.y)+EPS<min(p1.y, p2.y))  
  58.    return false;  
  59.   return signum(p2.sub(p1).det(q1.sub(p1)))  
  60.     *signum(p2.sub(p1).det(q2.sub(p1)))<EPS  
  61.     &&signum(q2.sub(q1).det(p1.sub(q1)))  
  62.       *signum(q2.sub(q1).det(p2.sub(q1)))<EPS;  
  63.  }  
  64.   
  65.  class P{  
  66.   double x, y;  
  67.   
  68.   P(){  
  69.    this(0, 0);  
  70.   }  
  71.   
  72.   P(double x, double y){  
  73.    this.x=x;  
  74.    this.y=y;  
  75.   }  
  76.   
  77.   P add(P p){  
  78.    return new P(x+p.x, y+p.y);  
  79.   }  
  80.   
  81.   P sub(P p){  
  82.    return new P(x-p.x, y-p.y);  
  83.   }  
  84.   
  85.   P mul(double m){  
  86.    return new P(x*m, y*m);  
  87.   }  
  88.   
  89.   P div(double d){  
  90.    return new P(x/d, y/d);  
  91.   }  
  92.   
  93.   double abs(){  
  94.    return Math.sqrt(abs2());  
  95.   }  
  96.   
  97.   double abs2(){  
  98.    return x*x+y*y;  
  99.   }  
  100.   
  101.   double arg(){  
  102.    return Math.atan2(y, x);  
  103.   }  
  104.   
  105.   // inner product  
  106.   double dot(P p){  
  107.    return x*p.x+y*p.y;  
  108.   }  
  109.   
  110.   // outer product  
  111.   double det(P p){  
  112.    return x*p.y-y*p.x;  
  113.   }  
  114.   
  115.   P rot90(){  
  116.    return new P(-y, x);  
  117.   }  
  118.   
  119.   // conjugation  
  120.   P conj(){  
  121.    return new P(x, -y);  
  122.   }  
  123.  }  
  124.   
  125.  void debug(Object... os){  
  126.   System.err.println(Arrays.deepToString(os));  
  127.  }  
  128.   
  129.  void print(String s){  
  130.   System.out.print(s);  
  131.  }  
  132.   
  133.  void println(String s){  
  134.   System.out.println(s);  
  135.  }  
  136.   
  137.  public static void main(String[] args){  
  138.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  139.   new Main().run();  
  140.  }  
  141. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年2月20日日曜日

Aizu Online Judge 0155 Spider Jin

■0155 Spider Jin

最初にどのビルからどのビルへ移動することが出来るかの辺を張る．あとはDijkstraをしながら，あるビルの前に訪れるビルを逐一記録しておけば良い．

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[] b, x, y;  
  18.  int m;  
  19.  int[] s, g;  
  20.  HashMap<Integer, Integer> map;  
  21.   
  22.  void run(){  
  23.   for(;;){  
  24.    n=sc.nextInt();  
  25.    if(n==0){  
  26.     break;  
  27.    }  
  28.    b=new int[n];  
  29.    x=new int[n];  
  30.    y=new int[n];  
  31.    for(int i=0; i<n; i++){  
  32.     b[i]=sc.nextInt();  
  33.     x[i]=sc.nextInt();  
  34.     y[i]=sc.nextInt();  
  35.    }  
  36.    m=sc.nextInt();  
  37.    s=new int[m];  
  38.    g=new int[m];  
  39.    for(int i=0; i<m; i++){  
  40.     s[i]=sc.nextInt();  
  41.     g[i]=sc.nextInt();  
  42.    }  
  43.    solve();  
  44.   }  
  45.  }  
  46.   
  47.  void solve(){  
  48.   map=new HashMap<Integer, Integer>();  
  49.   for(int i=0; i<n; i++){  
  50.    map.put(b[i], i);  
  51.   }  
  52.   
  53.   @SuppressWarnings("unchecked")  
  54.   LinkedList<E>[] es=new LinkedList[n];  
  55.   for(int j=0; j<n; j++){  
  56.    es[j]=new LinkedList<E>();  
  57.    for(int i=0; i<n; i++){  
  58.     if(i==j){  
  59.      continue;  
  60.     }  
  61.     double cost=Math.hypot(x[i]-x[j], y[i]-y[j]);  
  62.     if(cost<50+EPS){  
  63.      es[j].add(new E(i, cost));  
  64.     }  
  65.    }  
  66.   }  
  67.   for(int i=0; i<m; i++){  
  68.    LinkedList<Integer> path=dijkstra(es, map.get(s[i]), map.get(g[i]));  
  69.    if(path==null){  
  70.     println("NA");  
  71.    }else{  
  72.     for(int k=0; k<path.size(); k++){  
  73.      print(b[path.get(k)]+(k==path.size()-1?"\n":" "));  
  74.     }  
  75.    }  
  76.   }  
  77.  }  
  78.   
  79.  LinkedList<Integer> dijkstra(LinkedList<E>[] es, int s, int g){  
  80.   int n=es.length;  
  81.   double[] d=new double[n];  
  82.   int[] pre=new int[n];  
  83.   PriorityQueue<P> que=new PriorityQueue<P>();  
  84.   
  85.   Arrays.fill(d, INF);  
  86.   Arrays.fill(pre, -1);  
  87.   d[s]=0;  
  88.   pre[s]=s;  
  89.   que.offer(new P(s, 0));  
  90.   for(; !que.isEmpty();){  
  91.    P p=que.poll();  
  92.    if(d[p.v]<p.d)  
  93.     continue;  
  94.    for(E e : es[p.v]){  
  95.     if(d[e.to]>d[p.v]+e.cost){  
  96.      pre[e.to]=p.v;  
  97.      d[e.to]=d[p.v]+e.cost;  
  98.      que.offer(new P(e.to, d[e.to]));  
  99.     }  
  100.    }  
  101.   }  
  102.   LinkedList<Integer> path=new LinkedList<Integer>();  
  103.   for(int i=g;; i=pre[i]){  
  104.    path.addFirst(i);  
  105.    if(i==-1){  
  106.     return null;  
  107.    }  
  108.    if(i==s){  
  109.     return path;  
  110.    }  
  111.   }  
  112.  }  
  113.   
  114.  class E{  
  115.   int to;  
  116.   double cost;  
  117.   
  118.   E(int to, double cost){  
  119.    this.to=to;  
  120.    this.cost=cost;  
  121.   }  
  122.  }  
  123.   
  124.  class P implements Comparable<P>{  
  125.   int v;  
  126.   double d;  
  127.   
  128.   P(int v, double d){  
  129.    this.v=v;  
  130.    this.d=d;  
  131.   }  
  132.   
  133.   @Override  
  134.   public int compareTo(P p){  
  135.    if(d+EPS<p.d){  
  136.     return -1;  
  137.    }else if(d>p.d+EPS){  
  138.     return 1;  
  139.    }else{  
  140.     return 0;  
  141.    }  
  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. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0154 Sum of Cards

■0154 Sum of Cards

動的計画法による解法．

dp[i]=総和が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.  int m, g;  
  17.  int[] a, b, n;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    m=sc.nextInt();  
  22.    if(m==0){  
  23.     break;  
  24.    }  
  25.    a=new int[m];  
  26.    b=new int[m];  
  27.    for(int i=0; i<m; i++){  
  28.     a[i]=sc.nextInt();  
  29.     b[i]=sc.nextInt();  
  30.    }  
  31.    g=sc.nextInt();  
  32.    n=new int[g];  
  33.    for(int i=0; i<g; i++){  
  34.     n[i]=sc.nextInt();  
  35.    }  
  36.    solve();  
  37.   }  
  38.  }  
  39.   
  40.  void solve(){  
  41.   int max=1001;  
  42.   int[] dp=new int[max];  
  43.   int[] dp2=new int[max];  
  44.   dp[0]=1;  
  45.   for(int j=0; j<m; j++){  
  46.    System.arraycopy(dp, 0, dp2, 0, max);  
  47.    for(int i=0; i<b[j]; i++){  
  48.     for(int k=max-a[j]*(i+1)-1; k>=0; k--){  
  49.      dp[k+a[j]*(i+1)]+=dp2[k];  
  50.     }  
  51.    }  
  52.   }  
  53.   for(int i=0; i<g; i++){  
  54.    println(""+dp[n[i]]);  
  55.   }  
  56.  }  
  57.   
  58.  void debug(Object... os){  
  59.   System.err.println(Arrays.deepToString(os));  
  60.  }  
  61.   
  62.  void print(String s){  
  63.   System.out.print(s);  
  64.  }  
  65.   
  66.  void println(String s){  
  67.   System.out.println(s);  
  68.  }  
  69.   
  70.  public static void main(String[] args){  
  71.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  72.   new Main().run();  
  73.  }  
  74. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0152 Bowling

■0152 Bowling

簡単な実装ゲー．

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.   
  19.  void run(){  
  20.   for(;;){  
  21.    n=sc.nextInt();  
  22.    if(n==0){  
  23.     break;  
  24.    }  
  25.    sc.nextLine();  
  26.    rs=new R[n];  
  27.    for(int j=0; j<n; j++){  
  28.     Scanner s=new Scanner(sc.nextLine());  
  29.     rs[j]=new R();  
  30.     rs[j].id=s.nextInt();  
  31.     for(int i=0; s.hasNext(); i++){  
  32.      rs[j].pins[i]=s.nextInt();  
  33.     }  
  34.    }  
  35.    solve();  
  36.   }  
  37.  }  
  38.   
  39.  void solve(){  
  40.   for(int i=0; i<n; i++){  
  41.    rs[i].score=getScore(rs[i].pins);  
  42.   }  
  43.   Arrays.sort(rs);  
  44.   for(R r : rs){  
  45.    println(r.id+" "+r.score);  
  46.   }  
  47.  }  
  48.   
  49.  int getScore(int[] pin){  
  50.   int score=0;  
  51.   for(int frame=0, i=0; frame<10; frame++){  
  52.    if(frame<9){  
  53.     if(pin[i]==10){  
  54.      score+=10+pin[i+1]+pin[i+2];  
  55.      i++;  
  56.     }else if(pin[i]+pin[i+1]==10){  
  57.      score+=10+pin[i+2];  
  58.      i+=2;  
  59.     }else{  
  60.      score+=pin[i]+pin[i+1];  
  61.      i+=2;  
  62.     }  
  63.    }else{  
  64.     score+=pin[i]+pin[i+1]+pin[i+2];  
  65.    }  
  66.   }  
  67.   return score;  
  68.  }  
  69.   
  70.  class R implements Comparable<R>{  
  71.   int id, score;  
  72.   int[] pins=new int[22];  
  73.   
  74.   @Override  
  75.   public int compareTo(R r){  
  76.    if(r.score!=score){  
  77.     return r.score-score;  
  78.    }else{  
  79.     return id-r.id;  
  80.    }  
  81.   }  
  82.  }  
  83.   
  84.  void debug(Object... os){  
  85.   System.err.println(Arrays.deepToString(os));  
  86.  }  
  87.   
  88.  void print(String s){  
  89.   System.out.print(s);  
  90.  }  
  91.   
  92.  void println(String s){  
  93.   System.out.println(s);  
  94.  }  
  95.   
  96.  public static void main(String[] args){  
  97.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  98.   new Main().run();  
  99.  }  
  100. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0151 Grid

■0151 Grid

適当に全方向探索するだけ．

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;  
  17.  int n;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    n=sc.nextInt();  
  22.    if(n==0){  
  23.     break;  
  24.    }  
  25.    a=new int[n][n];  
  26.    for(int j=0; j<n; j++){  
  27.     String s=sc.next();  
  28.     for(int i=0; i<n; i++){  
  29.      a[j][i]=s.charAt(i)-'0';  
  30.     }  
  31.    }  
  32.    solve();  
  33.   }  
  34.  }  
  35.   
  36.  void solve(){  
  37.   int ans=0;  
  38.   for(int j=0; j<n; j++){  
  39.    for(int i=0, k=0; i<n; i++)  
  40.     ans=Math.max(ans, k=(k+1)*a[j][i]);  
  41.    for(int i=0, k=0; i<n; i++)  
  42.     ans=Math.max(ans, k=(k+1)*a[i][j]);  
  43.    for(int i=0, k=0; j+i<n; i++)  
  44.     ans=Math.max(ans, k=(k+1)*a[j+i][i]);  
  45.    for(int i=0, k=0; j-i>=0; i++)  
  46.     ans=Math.max(ans, k=(k+1)*a[j-i][i]);  
  47.    for(int i=0, k=0; j+i<n; i++)  
  48.     ans=Math.max(ans, k=(k+1)*a[j+i][n-1-i]);  
  49.    for(int i=0, k=0; j-i>=0; i++)  
  50.     ans=Math.max(ans, k=(k+1)*a[j-i][n-1-i]);  
  51.   }  
  52.   println(""+ans);  
  53.  }  
  54.   
  55.  void debug(Object... os){  
  56.   System.err.println(Arrays.deepToString(os));  
  57.  }  
  58.   
  59.  void print(String s){  
  60.   System.out.print(s);  
  61.  }  
  62.   
  63.  void println(String s){  
  64.   System.out.println(s);  
  65.  }  
  66.   
  67.  public static void main(String[] args){  
  68.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  69.   new Main().run();  
  70.  }  
  71. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0150 Twin Prime

■0150 Twin Prime

やるだけ．

素数判定は簡単なものでも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.  void run(){  
  17.   boolean[] fs=new boolean[10001];  
  18.   for(int i=0; i<10001; i++){  
  19.    fs[i]=isPrime(i-2)&&isPrime(i);  
  20.   }  
  21.   
  22.   for(; sc.hasNext();){  
  23.    int n=sc.nextInt();  
  24.    if(n==0){  
  25.     break;  
  26.    }  
  27.    for(; !fs[n]; n--);  
  28.    println((n-2)+" "+n);  
  29.   }  
  30.  }  
  31.   
  32.  boolean isPrime(int n){  
  33.   for(int i=2; i*i<=n; i++){  
  34.    if(n%i==0){  
  35.     return false;  
  36.    }  
  37.   }  
  38.   return n>=2;  
  39.  }  
  40.   
  41.  void debug(Object... os){  
  42.   System.err.println(Arrays.deepToString(os));  
  43.  }  
  44.   
  45.  void print(String s){  
  46.   System.out.print(s);  
  47.  }  
  48.   
  49.  void println(String s){  
  50.   System.out.println(s);  
  51.  }  
  52.   
  53.  public static void main(String[] args){  
  54.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  55.   new Main().run();  
  56.  }  
  57. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0149 Eye Test

■0149 Eye 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 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[][] h=new int[4][2];  
  18.   double[] ts={1.1, 0.6, 0.2, 0};  
  19.   for(; sc.hasNext();){  
  20.    for(int j=0; j<2; j++){  
  21.     double s=sc.nextDouble();  
  22.     for(int i=0; i<4; i++){  
  23.      if(s+EPS>ts[i]){  
  24.       h[i][j]++;  
  25.       break;  
  26.      }  
  27.     }  
  28.    }  
  29.   }  
  30.   for(int i=0; i<4; i++){  
  31.    println(h[i][0]+" "+h[i][1]);  
  32.   }  
  33.  }  
  34.   
  35.  void debug(Object... os){  
  36.   System.err.println(Arrays.deepToString(os));  
  37.  }  
  38.   
  39.  void print(String s){  
  40.   System.out.print(s);  
  41.  }  
  42.   
  43.  void println(String s){  
  44.   System.out.println(s);  
  45.  }  
  46.   
  47.  public static void main(String[] args){  
  48.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  49.   new Main().run();  
  50.  }  
  51. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0148 Candy and Class Flag

■0148 Candy and Class Flag

やるだけ．

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.   for(; sc.hasNext();){  
  18.    println(String.format("3C%02d", (sc.nextInt()-1)%39+1));  
  19.   }  
  20.  }  
  21.   
  22.  void debug(Object... os){  
  23.   System.err.println(Arrays.deepToString(os));  
  24.  }  
  25.   
  26.  void print(String s){  
  27.   System.out.print(s);  
  28.  }  
  29.   
  30.  void println(String s){  
  31.   System.out.println(s);  
  32.  }  
  33.   
  34.  public static void main(String[] args){  
  35.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  36.   new Main().run();  
  37.  }  
  38. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0147 Fukushimaken

■0147 Fukushimaken

軽い実装ゲー．

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.   LinkedList<Integer> que=new LinkedList<Integer>();  
  18.   int[] wait=new int[100]; // 待ち時間  
  19.   int[] a=new int[17]; // 座っている客  
  20.   int[] rest=new int[17]; // 客が帰るまでの時間  
  21.   int[] b=new int[17];  
  22.   
  23.   for(int t=0;; t++){  
  24.    // 食事終了  
  25.    for(int i=0; i<17; i++){  
  26.     if(--rest[i]<=0){  
  27.      a[i]=-1;  
  28.     }  
  29.    }  
  30.   
  31.    // 新しい客  
  32.    if(t%5==0&&t<500){  
  33.     que.addLast(t/5);  
  34.    }  
  35.   
  36.    // つめられるだけつめる  
  37.    for(; !que.isEmpty();){  
  38.     int c=que.getFirst();  
  39.     int n=c%5==1?5:2;  
  40.     int j=-1;  
  41.     for(int i=16; i>=0; i--){  
  42.      b[i]=a[i]==-1?((i==16?0:b[i+1])+1):0;  
  43.      if(b[i]>=n){  
  44.       j=i;  
  45.      }  
  46.     }  
  47.     if(j==-1){  
  48.      break;  
  49.     }  
  50.     for(int i=j; i<j+n; i++){  
  51.      a[i]=c;  
  52.      rest[i]=17*(c%2)+3*(c%3)+19;  
  53.     }  
  54.     wait[c]=t-5*c;  
  55.     que.removeFirst();  
  56.    }  
  57.   
  58.    if(t>500&&que.isEmpty()){  
  59.     break;  
  60.    }  
  61.   }  
  62.   
  63.   for(; sc.hasNext();){  
  64.    println(""+wait[sc.nextInt()]);  
  65.   }  
  66.   
  67.  }  
  68.   
  69.  void debug(Object... os){  
  70.   System.err.println(Arrays.deepToString(os));  
  71.  }  
  72.   
  73.  void print(String s){  
  74.   System.out.print(s);  
  75.  }  
  76.   
  77.  void println(String s){  
  78.   System.out.println(s);  
  79.  }  
  80.   
  81.  public static void main(String[] args){  
  82.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  83.   new Main().run();  
  84.  }  
  85. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0146 Lupin The 4th

■0146 Lupin The 4th

動的計画法による解法．

dp[訪れた蔵の集合][現在訪れている蔵]=その状態までの最小時間
とすると，
dp[0][i]=0
dp[k|(1<<i)][i]=minj{dp[k][j]+|d[i]-d[j]|/(2000/(70+ws[k]))}
となる．
d[i]：城から蔵iの距離
ws[k]：kの蔵全ての千両箱の総重量
計算量O(2nn2)
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[] name, d, w;  
  18.   
  19.  void run(){  
  20.   n=sc.nextInt();  
  21.   name=new int[n];  
  22.   d=new int[n];  
  23.   w=new int[n];  
  24.   for(int i=0; i<n; i++){  
  25.    name[i]=sc.nextInt();  
  26.    d[i]=sc.nextInt();  
  27.    w[i]=sc.nextInt();  
  28.   }  
  29.   solve();  
  30.  }  
  31.   
  32.  void solve(){  
  33.   double[][] dp=new double[1<<n][n];  
  34.   int[][] p=new int[1<<n][n];  
  35.   int[] ws=new int[1<<n];  
  36.   
  37.   for(int k=0; k<1<<n; k++){  
  38.    for(int i=0; i<n; i++){  
  39.     ws[k|(1<<i)]=ws[k]+20*w[i];  
  40.    }  
  41.   }  
  42.   
  43.   for(int k=1; k<1<<n; k++){  
  44.    Arrays.fill(dp[k], INF);  
  45.   }  
  46.   
  47.   for(int k=0; k<1<<n; k++){  
  48.    for(int j=0; j<n; j++){  
  49.     for(int i=0; i<n; i++){  
  50.      if((k>>i&1)==0){  
  51.       double t=dp[k][j]+Math.abs(d[i]-d[j])/2000.0*(70+ws[k]);  
  52.       if(t+EPS<dp[k|(1<<i)][i]){  
  53.        dp[k|(1<<i)][i]=t;  
  54.        p[k|(1<<i)][i]=j;  
  55.       }  
  56.      }  
  57.     }  
  58.    }  
  59.   }  
  60.   
  61.   int m=0;  
  62.   for(int i=0; i<n; i++){  
  63.    if(dp[(1<<n)-1][i]+EPS<dp[(1<<n)-1][m]){  
  64.     m=i;  
  65.    }  
  66.   }  
  67.   
  68.   LinkedList<Integer> path=new LinkedList<Integer>();  
  69.   for(int i=m, sup=(1<<n)-1; sup!=0;){  
  70.    path.addFirst(i);  
  71.    int j=p[sup][i];  
  72.    sup&=~(1<<i);  
  73.    i=j;  
  74.   }  
  75.   
  76.   for(int i=0; i<path.size(); i++){  
  77.    print(name[path.get(i)]+(i==path.size()-1?"\n":" "));  
  78.   }  
  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. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0145 Cards

■0145 Cards

動的計画法による解法．計算量はO(n)

dp[i][j]=i番目からj番目のカードをまとめたときの最小コスト
とすると，
dp[i][i]=0
dp[i][j]=mink{dp[i][k]+dp[k+1][j]+a[i]*b[k]*a[k+1]*b[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.  int n;  
  17.  int[] a, b;  
  18.   
  19.  void run(){  
  20.   n=sc.nextInt();  
  21.   a=new int[n];  
  22.   b=new int[n];  
  23.   for(int i=0; i<n; i++){  
  24.    a[i]=sc.nextInt();  
  25.    b[i]=sc.nextInt();  
  26.   }  
  27.   solve();  
  28.  }  
  29.   
  30.  void solve(){  
  31.   int[][] dp=new int[n][n];  
  32.   
  33.   for(int i=0; i<n; i++){  
  34.    Arrays.fill(dp[i], INF);  
  35.    dp[i][i]=0;  
  36.   }  
  37.   
  38.   for(int m=1; m<n; m++){  
  39.    for(int i=0, j=m; j<n; i++, j++){  
  40.     for(int k=i; k<j; k++){  
  41.      dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+a[i]*b[k]  
  42.        *a[k+1]*b[j]);  
  43.     }  
  44.    }  
  45.   }  
  46.   
  47.   println(""+dp[0][n-1]);  
  48.   
  49.  }  
  50.   
  51.  void debug(Object... os){  
  52.   System.err.println(Arrays.deepToString(os));  
  53.  }  
  54.   
  55.  void print(String s){  
  56.   System.out.print(s);  
  57.  }  
  58.   
  59.  void println(String s){  
  60.   System.out.println(s);  
  61.  }  
  62.   
  63.  public static void main(String[] args){  
  64.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  65.   new Main().run();  
  66.  }  
  67. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年2月18日金曜日

Aizu Online Judge 0140 Bus Line

■0140 Bus Line

適当な場合分けによる冗長なコード．

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 s, g;  
  17.  int n;  
  18.   
  19.  void run(){  
  20.   n=sc.nextInt();  
  21.   for(int i=0; i<n; i++){  
  22.    s=sc.nextInt();  
  23.    g=sc.nextInt();  
  24.    solve();  
  25.   }  
  26.  }  
  27.   
  28.  void solve(){  
  29.   LinkedList<Integer> list=new LinkedList<Integer>();  
  30.   if(s<g){  
  31.    for(int i=s; i<=g; i++){  
  32.     list.add(i);  
  33.    }  
  34.   }else{  
  35.    if(s<=5){  
  36.     for(int i=s; i>=g; i--){  
  37.      list.add(i);  
  38.     }  
  39.    }else{  
  40.     int i=s;  
  41.     boolean f=false;  
  42.     for(; i<=9; i++){  
  43.      list.add(i);  
  44.      if(i==g){  
  45.       f=true;  
  46.       break;  
  47.      }  
  48.     }  
  49.     if(!f){  
  50.      for(i=5; i>=0; i--){  
  51.       list.add(i);  
  52.       if(i==g){  
  53.        f=true;  
  54.        break;  
  55.       }  
  56.      }  
  57.     }  
  58.     if(!f){  
  59.      for(i=1; i<=g; i++){  
  60.       list.add(i);  
  61.       if(i==g){  
  62.        f=true;  
  63.        break;  
  64.       }  
  65.      }  
  66.     }  
  67.    }  
  68.   }  
  69.   for(int i=0; i<list.size(); i++){  
  70.    print(list.get(i)+(i==list.size()-1?"\n":" "));  
  71.   }  
  72.  }  
  73.   
  74.  void debug(Object... os){  
  75.   System.err.println(Arrays.deepToString(os));  
  76.  }  
  77.   
  78.  void print(String s){  
  79.   System.out.print(s);  
  80.  }  
  81.   
  82.  void println(String s){  
  83.   System.out.println(s);  
  84.  }  
  85.   
  86.  public static void main(String[] args){  
  87.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  88.   new Main().run();  
  89.  }  
  90. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0139 Snakes

■0139 Snakes

正規表現を使って判定すれば簡単．

view plainprint?
  1. import java.util.*;  
  2. import java.util.regex.Matcher;  
  3. import java.util.regex.Pattern;  
  4. import java.lang.*;  
  5. import java.math.*;  
  6. import java.io.*;  
  7.   
  8. import static java.lang.Math.*;  
  9. import static java.util.Arrays.*;  
  10.   
  11. public class Main{  
  12.   
  13.  Scanner sc=new Scanner(System.in);  
  14.   
  15.  int INF=1<<28;  
  16.  double EPS=1e-9;  
  17.   
  18.  void run(){  
  19.   for(int n=sc.nextInt(); n>0; n--){  
  20.    String s=sc.next();  
  21.    Matcher m=Pattern.compile("^>'(=+)#(=+)~$").matcher(s);  
  22.    if(m.find()){  
  23.     if(m.group(1).length()==m.group(2).length()){  
  24.      println("A");  
  25.      continue;  
  26.     }  
  27.    }  
  28.    m=Pattern.compile("^>\\^(Q=)+~~$").matcher(s);  
  29.    if(m.find()){  
  30.     println("B");  
  31.     continue;  
  32.    }  
  33.    println("NA");  
  34.   }  
  35.  }  
  36.   
  37.  void debug(Object... os){  
  38.   System.err.println(Arrays.deepToString(os));  
  39.  }  
  40.   
  41.  void print(String s){  
  42.   System.out.print(s);  
  43.  }  
  44.   
  45.  void println(String s){  
  46.   System.out.println(s);  
  47.  }  
  48.   
  49.  public static void main(String[] args){  
  50.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  51.   new Main().run();  
  52.  }  
  53. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0138 Track and Field Competition

■0138 Track and Field Competition

やるだけ．

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.   R[][] rss=new R[3][8];  
  18.   for(int i=0; i<24; i++){  
  19.    R r=new R();  
  20.    r.id=sc.nextInt();  
  21.    r.time=(int)(sc.nextDouble()*100);  
  22.    rss[i/8][i%8]=r;  
  23.   }  
  24.   Arrays.sort(rss[0]);  
  25.   Arrays.sort(rss[1]);  
  26.   Arrays.sort(rss[2]);  
  27.   LinkedList<R> list=new LinkedList<R>();  
  28.   for(int i=2; i<8; i++){  
  29.    list.add(rss[0][i]);  
  30.    list.add(rss[1][i]);  
  31.    list.add(rss[2][i]);  
  32.   }  
  33.   R[] rs=list.toArray(new R[0]);  
  34.   Arrays.sort(rs);  
  35.   
  36.   for(int j=0; j<3; j++){  
  37.    for(int i=0; i<2; i++){  
  38.     println(String.format("%d %.2f", rss[j][i].id,  
  39.       rss[j][i].time/100.));  
  40.    }  
  41.   }  
  42.   println(String.format("%d %.2f", rs[0].id, rs[0].time/100.));  
  43.   println(String.format("%d %.2f", rs[1].id, rs[1].time/100.));  
  44.  }  
  45.   
  46.  class R implements Comparable<R>{  
  47.   int id;  
  48.   int time;  
  49.   
  50.   @Override  
  51.   public int compareTo(R r){  
  52.    return time-r.time;  
  53.   }  
  54.  }  
  55.   
  56.  void debug(Object... os){  
  57.   System.err.println(Arrays.deepToString(os));  
  58.  }  
  59.   
  60.  void print(String s){  
  61.   System.out.print(s);  
  62.  }  
  63.   
  64.  void println(String s){  
  65.   System.out.println(s);  
  66.  }  
  67.   
  68.  public static void main(String[] args){  
  69.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  70.   new Main().run();  
  71.  }  
  72. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0137 Middle-Square Method

■0137 Middle-Square Method

やるだけ．

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=sc.nextInt();  
  18.   for(int j=1;j<=n;j++){  
  19.    int k=sc.nextInt();  
  20.    println("Case "+j+":");  
  21.    for(int i=0; i<10; i++){  
  22.     k=(k*k/100)%10000;  
  23.     println(""+k);  
  24.    }  
  25.   }  
  26.  }  
  27.   
  28.  void debug(Object... os){  
  29.   System.err.println(Arrays.deepToString(os));  
  30.  }  
  31.   
  32.  void print(String s){  
  33.   System.out.print(s);  
  34.  }  
  35.   
  36.  void println(String s){  
  37.   System.out.println(s);  
  38.  }  
  39.   
  40.  public static void main(String[] args){  
  41.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  42.   new Main().run();  
  43.  }  
  44. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0136 Frequency Distribution of Height

■0136 Frequency Distribution of Height

やるだけ．

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=sc.nextInt();  
  18.   int[] a=new int[6];  
  19.   for(int i=0; i<n; i++){  
  20.    double d=sc.nextDouble();  
  21.    for(int k=0; k<6; k++){  
  22.     if(d+EPS<165+k*5||k==5){  
  23.      a[k]++;  
  24.      break;  
  25.     }  
  26.    }  
  27.   }  
  28.   for(int i=0; i<6; i++){  
  29.    print((i+1)+":");  
  30.    for(int k=0; k<a[i]; k++){  
  31.     print("*");  
  32.    }  
  33.    println("");  
  34.   }  
  35.  }  
  36.   
  37.  void debug(Object... os){  
  38.   System.err.println(Arrays.deepToString(os));  
  39.  }  
  40.   
  41.  void print(String s){  
  42.   System.out.print(s);  
  43.  }  
  44.   
  45.  void println(String s){  
  46.   System.out.println(s);  
  47.  }  
  48.   
  49.  public static void main(String[] args){  
  50.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  51.   new Main().run();  
  52.  }  
  53. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0135 Clock Short Hand and Long Hand

■0135 Clock Short Hand and Long Hand

時計の長針・短針の角度をそれぞれ360°に直すだけ．

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=sc.nextInt();  
  18.   sc.useDelimiter("(\\s)+|[:]");  
  19.   for(int i=0; i<n; i++){  
  20.    double h=sc.nextInt()*30;  
  21.    double m=sc.nextInt()*6;  
  22.    h+=m/12;  
  23.    double d=Math.abs(h-m);  
  24.    d=Math.min(d, 360-d);  
  25.    if(d+EPS<30){  
  26.     println("alert");  
  27.    }else if(d+EPS>=90&&d<=180+EPS){  
  28.     println("safe");  
  29.    }else{  
  30.     println("warning");  
  31.    }  
  32.   }  
  33.  }  
  34.   
  35.  void debug(Object... os){  
  36.   System.err.println(Arrays.deepToString(os));  
  37.  }  
  38.   
  39.  void print(String s){  
  40.   System.out.print(s);  
  41.  }  
  42.   
  43.  void println(String s){  
  44.   System.out.println(s);  
  45.  }  
  46.   
  47.  public static void main(String[] args){  
  48.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  49.   new Main().run();  
  50.  }  
  51. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0134 Exit Survey

■0134 Exit Survey

やるだけ．

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=sc.nextInt();  
  18.   long sum=0;  
  19.   for(int i=0; i<n; i++){  
  20.    sum+=sc.nextInt();  
  21.   }  
  22.   println(""+(sum/n));  
  23.  }  
  24.   
  25.  void debug(Object... os){  
  26.   System.err.println(Arrays.deepToString(os));  
  27.  }  
  28.   
  29.  void print(String s){  
  30.   System.out.print(s);  
  31.  }  
  32.   
  33.  void println(String s){  
  34.   System.out.println(s);  
  35.  }  
  36.   
  37.  public static void main(String[] args){  
  38.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  39.   new Main().run();  
  40.  }  
  41. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0133 Rotation of a Pattern

■0133 Rotation of a Pattern

添字を弄るだけ．

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=8;  
  18.   String[] ss=new String[n];  
  19.   for(int j=0; j<n; j++){  
  20.    ss[j]=sc.next();  
  21.   }  
  22.   println("90");  
  23.   for(int i=0; i<n; i++){  
  24.    for(int j=n-1; j>=0; j--){  
  25.     print(""+ss[j].charAt(i));  
  26.    }  
  27.    println("");  
  28.   }  
  29.   println("180");  
  30.   for(int j=n-1; j>=0; j--){  
  31.    for(int i=n-1; i>=0; i--){  
  32.     print(""+ss[j].charAt(i));  
  33.    }  
  34.    println("");  
  35.   }  
  36.   println("270");  
  37.   for(int i=n-1; i>=0; i--){  
  38.    for(int j=0; j<n; j++){  
  39.     print(""+ss[j].charAt(i));  
  40.    }  
  41.    println("");  
  42.   }  
  43.  }  
  44.   
  45.  void debug(Object... os){  
  46.   System.err.println(Arrays.deepToString(os));  
  47.  }  
  48.   
  49.  void print(String s){  
  50.   System.out.print(s);  
  51.  }  
  52.   
  53.  void println(String s){  
  54.   System.out.println(s);  
  55.  }  
  56.   
  57.  public static void main(String[] args){  
  58.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  59.   new Main().run();  
  60.  }  
  61. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0131 Doctor's Strange Particles

■0131 Doctor's Strange Particles

いわゆるライツアウト．最上段の反転パターン方法を固定すると，あとは自動的に決定するので，最上段の反転パターンのみを全探索．

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, b;  
  17.  int[][] tmp;  
  18.  int n;  
  19.   
  20.  void run(){  
  21.   n=10;  
  22.   for(int m=sc.nextInt(); m>0; m--){  
  23.    a=new int[n][n];  
  24.    for(int j=0; j<n; j++){  
  25.     for(int i=0; i<n; i++){  
  26.      a[j][i]=sc.nextInt();  
  27.     }  
  28.    }  
  29.    solve();  
  30.   }  
  31.  }  
  32.   
  33.  void solve(){  
  34.   tmp=new int[n][n];  
  35.   b=new int[n][n];  
  36.   for(int sup=0; sup<1<<n; sup++){  
  37.    for(int j=0; j<n; j++){  
  38.     System.arraycopy(a[j], 0, tmp[j], 0, n);  
  39.     Arrays.fill(b[j], 0);  
  40.    }  
  41.    for(int i=0; i<n; i++){  
  42.     if(((sup>>i)&1)!=0){  
  43.      reverse(i, 0);  
  44.     }  
  45.    }  
  46.    for(int j=1; j<n; j++){  
  47.     for(int i=0; i<n; i++){  
  48.      if(tmp[j-1][i]==1){  
  49.       reverse(i, j);  
  50.      }  
  51.     }  
  52.    }  
  53.    int c=0;  
  54.    for(int i=0;i<n;i++){  
  55.     c+=tmp[n-1][i];  
  56.    }  
  57.    if(c==0){  
  58.     for(int j=0;j<n;j++){  
  59.      for(int i=0;i<n;i++){  
  60.       print(b[j][i]+(i==n-1?"\n":" "));  
  61.      }  
  62.     }  
  63.     return;  
  64.    }  
  65.   }  
  66.  }  
  67.   
  68.  void reverse(int x, int y){  
  69.   int[] dx={0, 0, 0, -1, 1};  
  70.   int[] dy={0, -1, 1, 0, 0};  
  71.   for(int i=0; i<5; i++){  
  72.    int x2=x+dx[i];  
  73.    int y2=y+dy[i];  
  74.    if(x2>=0&&x2<n&&y2>=0&&y2<n){  
  75.     tmp[y2][x2]=1-tmp[y2][x2];  
  76.    }  
  77.   }  
  78.   b[y][x]=1-b[y][x];  
  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. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年2月16日水曜日

Aizu Online Judge 0129 Hide-and-Seek Supporting System

■0129 Hide-and-Seek Supporting System

鬼-たろう君からなる直線と円の交点を求めて，交点が鬼-たろう君からなる線分上に存在するかを判定するだけ．

view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. public class Main{  
  7.   
  8.  Scanner sc=new Scanner(System.in);  
  9.   
  10.  int INF=1<<28;  
  11.  double EPS=1e-9;  
  12.   
  13.  int n, m;  
  14.  P[] cs;  
  15.  int[] rs;  
  16.  P t, s;  
  17.   
  18.  void run(){  
  19.   for(;;){  
  20.    n=sc.nextInt();  
  21.    if(n==0){  
  22.     break;  
  23.    }  
  24.    cs=new P[n];  
  25.    rs=new int[n];  
  26.    for(int i=0; i<n; i++){  
  27.     int x=sc.nextInt();  
  28.     int y=sc.nextInt();  
  29.     rs[i]=sc.nextInt();  
  30.     cs[i]=new P(x, y);  
  31.    }  
  32.    m=sc.nextInt();  
  33.    for(int i=0; i<m; i++){  
  34.     int tx=sc.nextInt();  
  35.     int ty=sc.nextInt();  
  36.     int sx=sc.nextInt();  
  37.     int sy=sc.nextInt();  
  38.     t=new P(tx, ty);  
  39.     s=new P(sx, sy);  
  40.     solve();  
  41.    }  
  42.   }  
  43.  }  
  44.   
  45.  void solve(){  
  46.   boolean safe=false;  
  47.   for(int i=0; i<n; i++){  
  48.    P[] ps=isCL(cs[i], rs[i], t, s);  
  49.    for(P p : ps){  
  50.     if(between(t.x, s.x, p.x)&&between(t.y, s.y, p.y)){  
  51.      safe=true;  
  52.     }  
  53.    }  
  54.   }  
  55.   println(safe?"Safe":"Danger");  
  56.  }  
  57.   
  58.  boolean between(double x1, double x2, double x){  
  59.   return (x1<x+EPS&&x<x2+EPS)||(x1+EPS>x&&x+EPS>x2);  
  60.  }  
  61.   
  62.  P[] isCL(P c, double r, P p1, P p2){  
  63.   double x=p1.sub(c).dot(p2.sub(p1));  
  64.   double y=p2.sub(p1).abs2();  
  65.   double d=x*x-y*(p1.sub(c).abs2()-r*r);  
  66.   if(d<-EPS)  
  67.    return new P[0];  
  68.   if(d<0)  
  69.    d=0;  
  70.   P q1=p1.sub(p2.sub(p1).mul(x/y));  
  71.   P q2=p2.sub(p1).mul(Math.sqrt(d)/y);  
  72.   return new P[]{q1.sub(q2), q1.add(q2)};  
  73.  }  
  74.   
  75.  class P{  
  76.   double x, y;  
  77.   
  78.   P(){  
  79.    this(0, 0);  
  80.   }  
  81.   
  82.   P(double x, double y){  
  83.    this.x=x;  
  84.    this.y=y;  
  85.   }  
  86.   
  87.   P add(P p){  
  88.    return new P(x+p.x, y+p.y);  
  89.   }  
  90.   
  91.   P sub(P p){  
  92.    return new P(x-p.x, y-p.y);  
  93.   }  
  94.   
  95.   P mul(double m){  
  96.    return new P(x*m, y*m);  
  97.   }  
  98.   
  99.   P div(double d){  
  100.    return new P(x/d, y/d);  
  101.   }  
  102.   
  103.   double abs(){  
  104.    return Math.sqrt(abs2());  
  105.   }  
  106.   
  107.   double abs2(){  
  108.    return x*x+y*y;  
  109.   }  
  110.   
  111.   double arg(){  
  112.    return Math.atan2(y, x);  
  113.   }  
  114.   
  115.   // inner product  
  116.   double dot(P p){  
  117.    return x*p.x+y*p.y;  
  118.   }  
  119.   
  120.   // outer product  
  121.   double det(P p){  
  122.    return x*p.y-y*p.x;  
  123.   }  
  124.   
  125.   P rot90(){  
  126.    return new P(-y, x);  
  127.   }  
  128.   
  129.   // conjugation  
  130.   P conj(){  
  131.    return new P(x, -y);  
  132.   }  
  133.  }  
  134.   
  135.  void debug(Object... os){  
  136.   System.err.println(Arrays.deepToString(os));  
  137.  }  
  138.   
  139.  void print(String s){  
  140.   System.out.print(s);  
  141.  }  
  142.   
  143.  void println(String s){  
  144.   System.out.println(s);  
  145.  }  
  146.   
  147.  public static void main(String[] args){  
  148.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  149.   new Main().run();  
  150.  }  
  151. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0122 Summer of Phyonkichi

■0122 Summer of Phyonkichi

適当にDFSをやって最後のスプリンクラーまでたどり着いたら"OK"．

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 x, y;  
  17.  int n;  
  18.  int[] xs, ys;  
  19.   
  20.  // カエルのジャンプ範囲  
  21.  int[] dx={-1, 0, 1, -1, 0, 1, -2, -2, -2, 2, 2, 2};  
  22.  int[] dy={-2, -2, -2, 2, 2, 2, -1, 0, 1, -1, 0, 1};  
  23.   
  24.  void run(){  
  25.   for(;;){  
  26.    x=sc.nextInt();  
  27.    y=sc.nextInt();  
  28.    if((x|y)==0){  
  29.     break;  
  30.    }  
  31.    n=sc.nextInt();  
  32.    xs=new int[n];  
  33.    ys=new int[n];  
  34.    for(int i=0; i<n; i++){  
  35.     xs[i]=sc.nextInt();  
  36.     ys[i]=sc.nextInt();  
  37.    }  
  38.    solve();  
  39.   }  
  40.  }  
  41.   
  42.  void solve(){  
  43.   for(int i=0; i<dx.length; i++){  
  44.    if(dfs(x+dx[i], y+dy[i], 0)){  
  45.     println("OK");  
  46.     return;  
  47.    }  
  48.   }  
  49.   println("NA");  
  50.  }  
  51.   
  52.  // (x,y)にてk番目のスプリンクラーに突撃  
  53.  boolean dfs(int x, int y, int k){  
  54.   if(k==n){  
  55.    return true;  
  56.   }  
  57.   if(x<0||x>=10||y<0||y>=10){  
  58.    return false;  
  59.   }  
  60.   if(x<xs[k]-1||x>xs[k]+1||y<ys[k]-1||y>ys[k]+1){  
  61.    return false;  
  62.   }  
  63.   for(int i=0; i<dx.length; i++){  
  64.    if(dfs(x+dx[i], y+dy[i], k+1)){  
  65.     return true;  
  66.    }  
  67.   }  
  68.   return false;  
  69.  }  
  70.   
  71.  void debug(Object... os){  
  72.   System.err.println(Arrays.deepToString(os));  
  73.  }  
  74.   
  75.  void print(String s){  
  76.   System.out.print(s);  
  77.  }  
  78.   
  79.  void println(String s){  
  80.   System.out.println(s);  
  81.  }  
  82.   
  83.  public static void main(String[] args){  
  84.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  85.   new Main().run();  
  86.  }  
  87. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0118 Property Distribution

■0118 Property Distribution

再帰を使うとおそらくスタックオーバーフローするので，キューを使ってBFS．

view plainprint?
  1. import java.util.*;  
  2. import java.lang.*;  
  3. import java.math.*;  
  4. import java.io.*;  
  5.   
  6. public class Main{  
  7.   
  8.  Scanner sc=new Scanner(System.in);;  
  9.   
  10.  int INF=1<<28;  
  11.  double EPS=1e-9;  
  12.   
  13.  int[][] a;  
  14.  int w, h;  
  15.  boolean[][] visited;  
  16.   
  17.  void run(){  
  18.   for(;;){  
  19.    h=sc.nextInt();  
  20.    w=sc.nextInt();  
  21.    if((h|w)==0){  
  22.     break;  
  23.    }  
  24.    a=new int[h][w];  
  25.    visited=new boolean[h][w];  
  26.    for(int j=0; j<h; j++){  
  27.     String s=sc.next();  
  28.     for(int i=0; i<w; i++){  
  29.      switch(s.charAt(i)){  
  30.      case '@':  
  31.       a[j][i]=0;  
  32.       break;  
  33.      case '#':  
  34.       a[j][i]=1;  
  35.       break;  
  36.      case '*':  
  37.       a[j][i]=2;  
  38.       break;  
  39.      }  
  40.     }  
  41.    }  
  42.    solve();  
  43.   }  
  44.  }  
  45.   
  46.  void solve(){  
  47.   int ans=0;  
  48.   for(int j=0; j<h; j++){  
  49.    for(int i=0; i<w; i++){  
  50.     if(!visited[j][i]){  
  51.      ans++;  
  52.      bfs(i, j);  
  53.     }  
  54.    }  
  55.   }  
  56.   println(ans+"");  
  57.  }  
  58.   
  59.  void bfs(int x, int y){  
  60.   LinkedList<P> que=new LinkedList<P>();  
  61.   que.offer(new P(x, y));  
  62.   visited[y][x]=true;  
  63.   int[] dx={0, 0, -1, 1};  
  64.   int[] dy={-1, 1, 0, 0};  
  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]);  
  69.     if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&!visited[q.y][q.x]  
  70.       &&a[p.y][p.x]==a[q.y][q.x]){  
  71.      que.offer(q);  
  72.      visited[q.y][q.x]=true;  
  73.     }  
  74.    }  
  75.   }  
  76.  }  
  77.   
  78.  class P{  
  79.   int x, y;  
  80.   
  81.   P(int x, int y){  
  82.    this.x=x;  
  83.    this.y=y;  
  84.   }  
  85.  }  
  86.   
  87.  void debug(Object... os){  
  88.   System.err.println(Arrays.deepToString(os));  
  89.  }  
  90.   
  91.  void print(String s){  
  92.   System.out.print(s);  
  93.  }  
  94.   
  95.  void println(String s){  
  96.   System.out.println(s);  
  97.  }  
  98.   
  99.  public static void main(String[] args){  
  100.   new Main().run();  
  101.  }  
  102. }  
投稿者 時刻: 1 件のコメント:
ラベル:

2011年2月15日火曜日

Aizu Online Judge 0117 A Reward a Carpenter

■0117 A Reward a Carpenter

(殿様から大工が受け取ったお金)-(柱の代金)-(出発町から山里までの総交通費)-(山里から出発町までの総交通費)が答え．後ろ2つは，それぞれDijkstraで求めれば良い．

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.   
  18.  void run(){  
  19.   sc.useDelimiter("[,]|(\\s)+");  
  20.   n=sc.nextInt();  
  21.   m=sc.nextInt();  
  22.   @SuppressWarnings("unchecked")  
  23.   LinkedList<E>[] es=new LinkedList[n];  
  24.   for(int i=0; i<n; i++){  
  25.    es[i]=new LinkedList<E>();  
  26.   }  
  27.   
  28.   for(int i=0; i<m; i++){  
  29.    int u=sc.nextInt()-1;  
  30.    int v=sc.nextInt()-1;  
  31.    int cost1=sc.nextInt();  
  32.    int cost2=sc.nextInt();  
  33.    es[u].add(new E(v, cost1));  
  34.    es[v].add(new E(u, cost2));  
  35.   }  
  36.   
  37.   int s=sc.nextInt()-1;  
  38.   int g=sc.nextInt()-1;  
  39.   int m1=sc.nextInt();  
  40.   int m2=sc.nextInt();  
  41.   
  42.   int ans=m1-m2-(dijkstra(es, s, g)+dijkstra(es, g, s));  
  43.   println(""+ans);  
  44.  }  
  45.   
  46.  int dijkstra(LinkedList<E>[] es, int s, int g){  
  47.   int n=es.length;  
  48.   int[] d=new int[n];  
  49.   PriorityQueue<P> que=new PriorityQueue<P>();  
  50.   
  51.   Arrays.fill(d, INF);  
  52.   d[s]=0;  
  53.   que.offer(new P(s, 0));  
  54.   for(; !que.isEmpty();){  
  55.    P p=que.poll();  
  56.    if(d[p.v]<p.d){  
  57.     continue;  
  58.    }  
  59.    for(E e : es[p.v]){  
  60.     if(d[e.to]>d[p.v]+e.cost){  
  61.      d[e.to]=d[p.v]+e.cost;  
  62.      que.offer(new P(e.to, d[e.to]));  
  63.     }  
  64.    }  
  65.   }  
  66.   return d[g];  
  67.  }  
  68.   
  69.  class E{  
  70.   int to, cost;  
  71.   
  72.   E(int to, int cost){  
  73.    this.to=to;  
  74.    this.cost=cost;  
  75.   }  
  76.  }  
  77.   
  78.  class P implements Comparable<P>{  
  79.   int v, d;  
  80.   
  81.   P(int v, int d){  
  82.    this.v=v;  
  83.    this.d=d;  
  84.   }  
  85.   
  86.   @Override  
  87.   public int compareTo(P p){  
  88.    return d-p.d;  
  89.   }  
  90.   
  91.   @Override  
  92.   public String toString(){  
  93.    return v+","+d;  
  94.   }  
  95.  }  
  96.   
  97.  void debug(Object... os){  
  98.   System.err.println(Arrays.deepToString(os));  
  99.  }  
  100.   
  101.  void print(String s){  
  102.   System.out.print(s);  
  103.  }  
  104.   
  105.  void println(String s){  
  106.   System.out.println(s);  
  107.  }  
  108.   
  109.  public static void main(String[] args){  
  110.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  111.   new Main().run();  
  112.  }  
  113. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0110 Alphametic

■0110 Alphametic

Xを0~9に変えて全部試すだけ．ただし，左端がXかつX=0となるようなケースに注意する必要がある．桁が大きそうなので，BigIntegerを使用した．

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 e1, e2, e3;  
  17.  int x;  
  18.   
  19.  void run(){  
  20.   for(; sc.hasNext();){  
  21.    String[] ss=sc.nextLine().split("[+]");  
  22.    e1=ss[0];  
  23.    ss=ss[1].split("=");  
  24.    e2=ss[0];  
  25.    e3=ss[1];  
  26.    solve();  
  27.   }  
  28.  }  
  29.   
  30.  void solve(){  
  31.   for(x=0; x<10; x++){  
  32.    if(x==0){  
  33.     if(e1.length()>1&&e1.charAt(0)=='X')  
  34.      continue;  
  35.     if(e2.length()>1&&e2.charAt(0)=='X')  
  36.      continue;  
  37.     if(e3.length()>1&&e3.charAt(0)=='X')  
  38.      continue;  
  39.    }  
  40.    if(toBI(e1).add(toBI(e2)).compareTo(toBI(e3))==0){  
  41.     println(""+x);  
  42.     return;  
  43.    }  
  44.   }  
  45.   println("NA");  
  46.  }  
  47.   
  48.  BigInteger toBI(String s){  
  49.   BigInteger bi=BigInteger.ZERO;  
  50.   for(char c : s.toCharArray()){  
  51.    if(c=='X'){  
  52.     bi=bi.multiply(BigInteger.TEN).add(new BigInteger(""+x));  
  53.    }else{  
  54.     bi=bi.multiply(BigInteger.TEN).add(new BigInteger(""+c));  
  55.    }  
  56.   }  
  57.   return bi;  
  58.  }  
  59.   
  60.  void debug(Object... os){  
  61.   System.err.println(Arrays.deepToString(os));  
  62.  }  
  63.   
  64.  void print(String s){  
  65.   System.out.print(s);  
  66.  }  
  67.   
  68.  void println(String s){  
  69.   System.out.println(s);  
  70.  }  
  71.   
  72.  public static void main(String[] args){  
  73.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  74.   new Main().run();  
  75.  }  
  76. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0106 Discounts of Buckwheat

■0106 Discounts of Buckwheat

入力の範囲が狭い(46通り)ので，全入力に対する解を予め全探索で求めておく．

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[] a=new int[51];  
  18.   Arrays.fill(a, INF);  
  19.   for(int k=0; toGramme(0, 0, k)<=50; k++){  
  20.    for(int j=0; toGramme(0, j, k)<=50; j++){  
  21.     for(int i=0; toGramme(i, j, k)<=50; i++){  
  22.      int g=toGramme(i, j, k);  
  23.      a[g]=Math.min(a[g], toMoney(i, j, k));  
  24.     }  
  25.    }  
  26.   }  
  27.   for(;;){  
  28.    int g=sc.nextInt()/100;  
  29.    if(g==0){  
  30.     break;  
  31.    }  
  32.    println(a[g]+"");  
  33.   }  
  34.  }  
  35.   
  36.  int toGramme(int i, int j, int k){  
  37.   return i*2+j*3+k*5;  
  38.  }  
  39.   
  40.  int toMoney(int i, int j, int k){  
  41.   int sum=0;  
  42.   sum+=380*(i-i%5)*80/100+380*(i%5);  
  43.   sum+=550*(j-j%4)*85/100+550*(j%4);  
  44.   sum+=850*(k-k%3)*88/100+850*(k%3);  
  45.   return sum;  
  46.  }  
  47.   
  48.  void debug(Object... os){  
  49.   System.err.println(Arrays.deepToString(os));  
  50.  }  
  51.   
  52.  void print(String s){  
  53.   System.out.print(s);  
  54.  }  
  55.   
  56.  void println(String s){  
  57.   System.out.println(s);  
  58.  }  
  59.   
  60.  public static void main(String[] args){  
  61.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  62.   new Main().run();  
  63.  }  
  64. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年2月13日日曜日

Prologの技芸 12.4節の練習問題

(1)


edit :- edit(file([],[])).
edit(File) :-
 write_prompt, read(Command), edit(File,Command).

edit(File,exit) :- !.
edit(File,Command) :-
 apply(Command,File,File1), !, edit(File1).
edit(File,Command) :-
 writeln([Command,'is not applicable']), !, edit(File).

apply(up,file([X|Xs],Ys),file(Xs,[X|Ys])).
apply(up(N),file(Xs,Ys),file(Xs1,Ys1)) :-
 N > 0, up(N,Xs,Ys,Xs1,Ys1).
apply(down,file(Xs,[Y|Ys]),file([Y|Xs],Ys)).
apply(down(N),file(Xs,Ys),file(Xs1,Ys1)) :-
 N > 0, down(N,Xs,Ys,Xs1,Ys1).
apply(insert(Line),file(Xs,Ys),file(Xs,[Line|Ys])).
apply(delete,file(Xs,[Y|Ys]),file(Xs,Ys)).
apply(delete(N),file(Xs,Ys),file(Xs1,Ys1)) :-
 N > 0, delete(N,Xs,Ys,Xs1,Ys1).
apply(print,file([X|Xs],Ys),file([X|Xs],Ys)) :-
 writeln(X).
apply(print(*),file(Xs,Ys),file(Xs,Ys)) :-
 reverse(Xs,Xs1), write_file(Xs1), write_file(Ys).
apply(search(T), file([X|Xs],Ys), file(Xs1,Ys1)) :-
 search(Xs,T,N), apply(up(N),file([X|Xs],Ys),file(Xs1,Ys1)).
apply(search(T), file(Xs,Ys), file(Xs1,Ys1)) :-
 search(Ys,T,N), apply(down(N),file(Xs,Ys),file(Xs1,Ys1)).
apply(search(T), file([T|Xs],Ys), file([T|Xs],Ys)).
apply(replace(S,T),file(Xs,Ys),file(Xs1,Ys1)) :-
 replace(Xs,Xs1,S,T), replace(Ys,Ys1,S,T).

up(N,[],Ys,[],Ys).
up(0,Xs,Ys,Xs,Ys).
up(N,[X|Xs],Ys,Xs1,Ys1) :-
 N > 0, N1 is N-1, up(N1,Xs,[X|Ys],Xs1,Ys1).

down(N,Xs,[],Xs,[]).
down(0,Xs,Ys,Xs,Ys).
down(N,Xs,[Y|Ys],Xs1,Ys1) :-
 N > 0, N1 is N-1, down(N1,[Y|Xs],Ys,Xs1,Ys1).

delete(N,Xs,[],Xs,[]).
delete(0,Xs,Ys,Xs,Ys).
delete(N,Xs,[Y|Ys],Xs1,Ys1) :-
 N > 0, N1 is N-1, delete(N1,Xs,Ys,Xs1,Ys1).

replace([],[],_,_).
replace([X|Xs],[X|Ys],S,T) :- X \= S, replace(Xs,Ys,S,T).
replace([S|Xs],[T|Ys],S,T) :- replace(Xs,Ys,S,T).

search([X|Xs],X,1).
search([X|Xs],Y,N) :-
 Y \= X, search(Xs,Y,M), N is M+1.

write_file([X|Xs]) :-
 write(X), nl, write_file(Xs).
write_file([]).

write_prompt :- writeln('>>').
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 12.3節の練習問題

(1)

% nim(N,S) :-
%  和がNで自分に回ってきたとき，Sと言えば勝てる．
nim(N,S) :- between(1,3,S), N1 is N+S, lose(N1), !.

:- dynamic win/1. 
:- dynamic lose/1. 
win(N) :-
 N =< 20, between(1,3,A),
 N1 is N+A, lemma(lose(N1)), !.
lose(20).
lose(N) :-
 N =< 20,
 N1 is N+1, N2 is N+2, N3 is N+3,
 lemma(win(N1)), lemma(win(N2)), lemma(win(N3)).
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 12.1節の練習問題

(1)

word_char(39). % アポストロフィ
word_char(C) :- char_type(C, digit).

end_of_words_char(C). :- char_code('?',C).
end_of_words_char(C). :- char_code('!',C).
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 11.4節の練習問題

(1)

% substitute(Old,New,OldTerm,NewTerm) :-
%  NewTermは，OldTerm中のOldをNewに置き換えたものである．

substitute(Old,New,Old,New) :- !.
substitute(Old,New,Term,Term) :-
 atomic(Term), !.
substitute(Old,New,Term,Term1) :-
 functor(Term,F,N),
 functor(Term1,F,N),
 substitute(N,Old,New,Term,Term1).
substitute(N,Old,New,Term,Term1) :-
 N > 0,
 !,
 arg(N,Term,Arg),
 substitute(Old,New,Arg,Arg1),
 arg(N,Term1,Arg1),
 N1 is N-1,
 substitute(N1,Old,New,Term,Term1).
substitute(0,Old,New,Term,Term1).

(2)

% select(X,Xs,Ys) :-
%  YsはリストXsの一番初めに出てきたXを
%  削除したリストである．
select(X,[X|Xs],Xs) :- !.
select(X,[Y|Ys],[Y|Zs]) :- select(X,Ys,Zs).
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 11.3節の練習問題

(1)

X \== Y :- X == Y, !, fail.
X \== Y.

(2)

nonvar(X) :- var(X), !, fail.
nonvar(X).
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 11.1節の練習問題

(1)

% クイックソート
% quicksort(Xs,Ys) :-
%  リストYsはリストXsの順序付けられた順列である．

quicksort([X|Xs],Ys) :-
 partition(Xs,X,Littles,Bigs),
 quicksort(Littles,Ls),
 quicksort(Bigs,Bs),
 append(Ls,[X|Bs],Ys).
quicksort([],[]).

partition([X|Xs],Y,[X|Ls],Bs) :-
 X =< Y, !, partition(Xs,Y,Ls,Bs).
partition([X|Xs],Y,Ls,[X|Bs]) :-
 X > Y, !, partition(Xs,Y,Ls,Bs).
partition([],Y,[],[]).

(2)

% derivative(Expression,X,DifferentiatedExpression) :-
%  DifferentiatedExpressionは，
% 式ExpressionのXに関する導関数である．

constant(X) :- integer(X).
constant(X) :- atom(X).

derivative(X,_,0) :- constant(X), !.
derivative(X,X,s(0)) :- !.
derivative(X^N,X,N*X^M) :- integer(N), !, M is N-1.
derivative(sin(X),X,cos(X)) :- !.
derivative(cos(X),X,-sin(X)) :- !.
derivative(e^X,X,e^X) :- !.
derivative(log(X),X,1/X) :- !.
derivative(F+G,X,DF+DG) :-
 !, derivative(F,X,DF), derivative(G,X,DG).
derivative(F-G,X,DF-DG) :-
 !, derivative(F,X,DF), derivative(G,X,DG).
derivative(F*G,X,F*DG+DF*G) :-
 !, derivative(F,X,DF), derivative(G,X,DG).
derivative(1/F,X,-DF / (F*F)) :-
 !, derivative(F,X,DF).
derivative(F/G,X,(G*DF-F*DG)/(G*G)) :-
 !, derivative(F,X,DF), derivative(G,X,DG).

(3)

% 挿入ソート
% insertionsort(Xs,Ys) :-
%  リストYsはリストXsの順序付けられた順列である．
insertionsort([X|Xs],Ys) :-
 !, insertionsort(Xs,Zs), insert(X,Zs,Ys).
insertionsort([],[]).

insert(X,[],[X]) :- !.
insert(X,[Y|Ys],[Y|Zs]) :- X > Y, !, insert(X,Ys,Zs).
insert(X,[Y|Ys],[X,Y|Ys]) :- X =< Y, !.
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 10.1節の練習問題

(1)

range(M,N,[M|Ns]) :-
 nonvar(M), nonvar(N), M < N, M1 is M+1, range(M1,N,Ns).
range(M,N,[M|Ns]) :-
 nonvar(M), nonvar(Ns), M1 is M+1, range(M1,N,Ns).
range(N,N,[N]).

(2)

plus(X,Y,Z) :- nonvar(Z), between(0,Z,X), Y is Z-X.
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 9.2節の練習問題

(1)

% occurrences(Sub,Term,N) :-
%  項Term中の部分項Subの出現回数がNのとき真になる．

occurrences(Term,Term,1) :- !.
occurrences(Sub,Term,N) :-
 compound(Term), !,
 functor(Term,F,M), occurrences(M,Sub,Term,0,N).
occurrences(Sub,Term,0).
occurrences(M,Sub,Term,N1,N2) :-
 M > 0, !, arg(M,Term,Arg), occurrences(Sub,Arg,N),
 N3 is N+N1, M1 is M-1, occurrences(M1,Sub,Term,N3,N2).
occurrences(0,Sub,Term,N,N).

(2)

% position(Subterm,Term,Position) :-
%  Positionは項Term中の部分項Subtermが占める
%  引数位置のリストである．

position(Term,Term,[]) :- !.
position(Sub,Term,Path) :-
 compound(Term), functor(Term,F,N),
 position(N,Sub,Term,Path), !.
position(N,Sub,Term,[N|Path]) :-
 arg(N,Term,Arg), position(Sub,Arg,Path).
position(N,Sub,Term,Path) :-
 N > 1, N1 is N-1, position(N1,Sub,Term,Path).

(3)

% univ(Term,List) :-
%  Listは，Termの関数子と，その後ろに
%  Termの引数を連ねたものからなるリストである．

univ(Term,[F|Args]) :-
 functor(Term,F,N), args(N,Term,Args,[]).
args(N,Term,Xs,Ys) :-
 N > 0, N1 is N-1,
 arg(N,Term,Arg), args(N1,Term,Xs,[Arg|Ys]).
args(0,Term,Xs,Xs).

(4)

% functor1(Term,F,Arity) :-
%  Termは，主関数子の名前がFで
%  引数の数がArityであるような項である．

functor1(Term,F,N) :-
 Term =.. [F|Args], length(Args,N).

% arg1(N,Term,Arg) :-
%  Argは，項TermのN番目の引数である．
arg1(N,Term,Arg) :-
 Term =.. [F|Args], retrieve(N,Args,Arg).

retrieve(1,[X|Xs],X).
retrieve(N,[X|Xs],Y) :-
 N > 1, N1 is N-1, retrieve(N1,Xs,Y).

(5)

% substitute(Old,New,OldTerm,NewTerm) :-
%  NewTermは，OldTerm中のOldをNewに置き換えたものである．

substitute(Old,New,Old,New).
substitute(Old,New,Term,Term) :-
 atomic(Term), Term \= Old.
substitute(Old,New,Term,Term1) :-
 compound(Term),
 Term =.. [F|Args],
 substitute_args(Old,New,Args,Args1),
 Term1 =.. [F|Args1].
substitute_args(Old,New,[Arg|Args],[Arg1|Args1]) :-
 substitute(Old,New,Arg,Arg1),
 substitute_args(Old,New,Args,Args1).
substitute_args(Old,New,[],[]).
投稿者 時刻: 0 件のコメント:
ラベル: ,

Prologの技芸 9.1節の練習問題

(1)

% flatten(Xs,Ys) :-
%  YsはXsの要素のリストである．
flatten(Xs,Ys) :- flatten(Xs,[],Ys).
flatten([X|Xs],Zs,Ys) :-
 flatten(Xs,Zs,Ys1), flatten(X,Ys1,Ys).
flatten(X,Xs,[X|Xs]) :-
 atomic(X), X \= [].
flatten([],Xs,Xs).
投稿者 時刻: 0 件のコメント:
ラベル: ,

Aizu Online Judge 0084 Search Engine

■0084 Search Engine

正規表現で書こうと思ったが，得意ではないので適当に自分で書いた．長いこと，単語はアルファベットのみから構成されるものと思い込んでいた…．反省．

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.   String line=sc.nextLine();  
  18.   String s="";  
  19.   LinkedList<String> list=new LinkedList<String>();  
  20.   for(char c : line.toCharArray()){  
  21.    if(c==' '||c=='.'||c==','){  
  22.     if(s.length()>=3&&s.length()<=6){  
  23.      list.add(s);  
  24.     }  
  25.     s="";  
  26.    }else{  
  27.     s+=c;  
  28.    }  
  29.   }  
  30.   if(s.length()>=3&&s.length()<=6){  
  31.    list.add(s);  
  32.   }  
  33.   for(int i=0; i<list.size(); i++){  
  34.    print(list.get(i)+(i==list.size()-1?"\n":" "));  
  35.   }  
  36.  }  
  37.   
  38.  void debug(Object... os){  
  39.   System.err.println(Arrays.deepToString(os));  
  40.  }  
  41.   
  42.  void print(String s){  
  43.   System.out.print(s);  
  44.  }  
  45.   
  46.  void println(String s){  
  47.   System.out.println(s);  
  48.  }  
  49.   
  50.  public static void main(String[] args){  
  51.   new Main().run();  
  52.  }  
  53. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年2月12日土曜日

Aizu Online Judge 0092 Square Searching

■0092 Square Searching

dp[j][i] := (i,j)が右下となる正方形の最大辺

とすると，dp[j][i]を決めるには，(i,j)の左上，左，上を見れば良い．n = min{dp[j-1][i-1], dp[j][i-1], dp[j-1][i]}とすると，(i,j)を右下とする長さn+1の正方形内は全て空白となる．即ち，

dp[j][i] = min{dp[j-1][i-1], dp[j][i-1], dp[j-1][i]} + 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.  int n;  
  17.  int[][] a;  
  18.   
  19.  void run(){  
  20.   for(;;){  
  21.    n=sc.nextInt();  
  22.    if(n==0){  
  23.     break;  
  24.    }  
  25.    a=new int[n][n];  
  26.    for(int j=0; j<n; j++){  
  27.     String s=sc.next();  
  28.     for(int i=0; i<n; i++){  
  29.      a[j][i]=s.charAt(i)=='.'?0:1;  
  30.     }  
  31.    }  
  32.    solve();  
  33.   }  
  34.  }  
  35.   
  36.  void solve(){  
  37.   int[][] dp=new int[n][n];  
  38.   int max=0;  
  39.   for(int j=0; j<n; j++){  
  40.    for(int i=0; i<n; i++){  
  41.     if(a[j][i]==0){  
  42.      if(i>0&&j>0){  
  43.       int n=Math.min(dp[j-1][i-1],  
  44.         Math.min(dp[j][i-1], dp[j-1][i]));  
  45.       dp[j][i]=n+1;  
  46.      }else{  
  47.       dp[j][i]=1;  
  48.      }  
  49.     }else{  
  50.      dp[j][i]=0;  
  51.     }  
  52.     max=Math.max(max, dp[j][i]);  
  53.    }  
  54.   }  
  55.   println(""+max);  
  56.  }  
  57.   
  58.  void debug(Object... os){  
  59.   System.err.println(Arrays.deepToString(os));  
  60.  }  
  61.   
  62.  void print(String s){  
  63.   System.out.print(s);  
  64.  }  
  65.   
  66.  void println(String s){  
  67.   System.out.println(s);  
  68.  }  
  69.   
  70.  public static void main(String[] args){  
  71.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  72.   new Main().run();  
  73.  }  
  74. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0086 Patrol

■0086 Patrol

いわゆる一筆書き．ただし，この問題では，スタート地点からゴール地点へ良く必要があるので，以下のように頂点A，Bを追加する．

A----S(Graph)G---B

あとは，以下の条件(「一筆書き - Wikipedia」からの引用)の内，2つ目の条件をみたすかを調べるだけ(字数が奇数である頂点とは，ここではAとBのこと)．

ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである（オイラー路参照）。

  • すべての頂点の次数（頂点につながっている辺の数）が偶数 → 運筆が起点に戻る場合（閉路）
  • 次数が奇数である頂点の数が2で、残りの頂点の次数は全て偶数　→ 運筆が起点に戻らない場合（閉路でない路）
view plainprint?
  1. import java.util.*;  
  2. import java.util.Map.Entry;  
  3. import java.lang.*;  
  4. import java.math.*;  
  5. import java.io.*;  
  6.   
  7. import static java.lang.Math.*;  
  8. import static java.util.Arrays.*;  
  9.   
  10. public class Main{  
  11.   
  12.  Scanner sc=new Scanner(System.in);  
  13.   
  14.  int INF=1<<28;  
  15.  double EPS=1e-9;  
  16.   
  17.  HashMap<Integer, Integer> map;  
  18.   
  19.  void run(){  
  20.   map=new HashMap<Integer, Integer>();  
  21.   for(; sc.hasNext();){  
  22.    map.clear();  
  23.    for(;;){  
  24.     int v=sc.nextInt();  
  25.     int u=sc.nextInt();  
  26.     if((v|u)==0){  
  27.      break;  
  28.     }  
  29.     if(!map.containsKey(v)){  
  30.      map.put(v, 0);  
  31.     }  
  32.     if(!map.containsKey(u)){  
  33.      map.put(u, 0);  
  34.     }  
  35.     map.put(v, map.get(v)+1);  
  36.     map.put(u, map.get(u)+1);  
  37.    }  
  38.    map.put(1, map.get(1)+1);  
  39.    map.put(2, map.get(2)+1);  
  40.    boolean even=true;  
  41.    for(Entry<Integer, Integer> entry : map.entrySet()){  
  42.     even&=entry.getValue()%2==0;  
  43.    }  
  44.    println(even?"OK":"NG");  
  45.   }  
  46.  }  
  47.   
  48.  void debug(Object... os){  
  49.   System.err.println(Arrays.deepToString(os));  
  50.  }  
  51.   
  52.  void print(String s){  
  53.   System.out.print(s);  
  54.  }  
  55.   
  56.  void println(String s){  
  57.   System.out.println(s);  
  58.  }  
  59.   
  60.  public static void main(String[] args){  
  61.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  62.   new Main().run();  
  63.  }  
  64. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0072 Carden Lantern

■0072 Carden Lantern

ただの最小全域木．木を構成しながら，(コスト/100-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%lt;%lt;28;  
  14.  double EPS=1e-9;  
  15.   
  16.  int n, m;  
  17.  int[][] w;  
  18.   
  19.  void run(){  
  20.   sc.useDelimiter("[,]|(\\s)+");  
  21.   for(; sc.hasNext();){  
  22.    n=sc.nextInt();  
  23.    if(n==0){  
  24.     break;  
  25.    }  
  26.    m=sc.nextInt();  
  27.    w=new int[n][n];  
  28.    for(int i=0; i%lt;n; i++){  
  29.     Arrays.fill(w[i], -1);  
  30.    }  
  31.    for(int i=0; i%lt;m; i++){  
  32.     int a=sc.nextInt();  
  33.     int b=sc.nextInt();  
  34.     int c=sc.nextInt()/100;  
  35.     w[a][b]=w[b][a]=c;  
  36.    }  
  37.    solve();  
  38.   }  
  39.  }  
  40.   
  41.  // w[i][j]=w[j][i]  
  42.  // w[i][j]=-1 -> E(i, j) not exist  
  43.  void solve(){  
  44.   init();  
  45.   LinkedList%lt;E> list=new LinkedList%lt;E>();  
  46.   
  47.   for(int j=0; j%lt;n-1; j++)  
  48.    for(int i=j+1; i%lt;n; i++)  
  49.     if(w[j][i]!=-1)  
  50.      list.add(new E(j, i, w[j][i]));  
  51.   
  52.   E[] es=list.toArray(new E[0]);  
  53.   Arrays.sort(es, new Comparator%lt;E>(){  
  54.    @Override  
  55.    public int compare(E e1, E e2){  
  56.     return e1.w-e2.w;  
  57.    }  
  58.   });  
  59.   
  60.   list.clear();  
  61.   int ans=0;  
  62.   for(E e : es){  
  63.    if(find(e.v1)!=find(e.v2)){  
  64.     union(e.v1, e.v2);  
  65.     ans+=e.w-1;  
  66.     list.add(e);  
  67.    }  
  68.   }  
  69.   println(""+ans);  
  70.  }  
  71.   
  72.  int[] p, rank;  
  73.   
  74.  void init(){  
  75.   p=new int[n];  
  76.   rank=new int[n];  
  77.   for(int i=0; i%lt;n; i++){  
  78.    p[i]=i;  
  79.    rank[i]=0;  
  80.   }  
  81.  }  
  82.   
  83.  int find(int x){  
  84.   if(p[x]==x)  
  85.    return x;  
  86.   else  
  87.    return p[x]=find(p[x]);  
  88.  }  
  89.   
  90.  void union(int x, int y){  
  91.   x=find(x);  
  92.   y=find(y);  
  93.   if(rank[x]>rank[y]){  
  94.    p[y]=x;  
  95.   }else{  
  96.    p[x]=y;  
  97.    if(rank[x]==rank[y])  
  98.     rank[y]++;  
  99.   }  
  100.  }  
  101.   
  102.  class E{  
  103.   int v1, v2, w;  
  104.   
  105.   E(int v1, int v2, int w){  
  106.    this.v1=v1;  
  107.    this.v2=v2;  
  108.    this.w=w;  
  109.   }  
  110.  }  
  111.   
  112.  void debug(Object... os){  
  113.   System.err.println(Arrays.deepToString(os));  
  114.  }  
  115.   
  116.  void print(String s){  
  117.   System.out.print(s);  
  118.  }  
  119.   
  120.  void println(String s){  
  121.   System.out.println(s);  
  122.  }  
  123.   
  124.  public static void main(String[] args){  
  125.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  126.   new Main().run();  
  127.  }  
  128. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0070 Combination of Number Sequences

■0070 Combination of Number Sequences

探索?
TLE
高速化したよー
TLE

～長い年月～

やっぱDPじゃん
テキトーに組む
TLE
ま・さ・か
実は探索?
nとsの範囲が実は狭いことに気付く(n≦10，s≦330)．大きい場合は絶対に存在しない．
ばっち枝刈りしたZE
TLE
あるぇー（・３・）
nとsが小さいんだから，予めDPで生成しておけるよねー．
前に書いたDPを流用
AC
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.  static final int INF=1<<28;  
  14.  static final double EPS=1e-9;  
  15.   
  16.  int n, s;  
  17.  int[][] sum;  
  18.   
  19.  void run(){  
  20.   n=10;  
  21.   s=330;  
  22.   init();  
  23.   for(; sc.hasNext();){  
  24.    n=sc.nextInt();  
  25.    s=sc.nextInt();  
  26.    if(n<=10&&s<=330){  
  27.     println(sum[n-1][s]+"");  
  28.    }else{  
  29.     println("0");  
  30.    }  
  31.   }  
  32.   sc.close();  
  33.  }  
  34.   
  35.  void init(){  
  36.   int[][] dp=new int[s+1][1<<10];  
  37.   int[][] dp2=new int[s+1][1<<10];  
  38.   sum=new int[n][s+1];  
  39.   dp[0][0]=1;  
  40.   
  41.   for(int j=0; j<n; j++){  
  42.    for(int i=0; i<=s; i++){  
  43.     System.arraycopy(dp[i], 0, dp2[i], 0, 1<<10);  
  44.     Arrays.fill(dp[i], 0);  
  45.    }  
  46.    for(int i=0; i<10; i++){  
  47.     int d=(j+1)*i;  
  48.     for(int b=0; b<1<<10; b++){  
  49.      if(((1<<i)&b)==0){  
  50.       for(int k=0; k+d<=s; k++){  
  51.        dp[k+d][(1<<i)|b]+=dp2[k][b];  
  52.       }  
  53.      }  
  54.     }  
  55.    }  
  56.    for(int i=0; i<=s; i++){  
  57.     for(int b=0; b<1<<10; b++){  
  58.      sum[j][i]+=dp[i][b];  
  59.     }  
  60.    }  
  61.   }  
  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.   new Main().run();  
  78.  }  
  79. }  
投稿者 時刻: 0 件のコメント:
ラベル:

2011年2月11日金曜日

Aizu Online Judge 0069 Drawing Lots II

■0069 Drawing Lots II

あみだくじの実装をやるだけ．
注意点は，横棒を追加するときに，注目している場所の左右に横棒が既に置かれていないかをチェックするということ．

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 start, goal;  
  18.  int[][] a;  
  19.   
  20.  void run(){  
  21.   for(;;){  
  22.    m=sc.nextInt();  
  23.    if(m==0){  
  24.     break;  
  25.    }  
  26.    start=sc.nextInt()-1;  
  27.    goal=sc.nextInt()-1;  
  28.    n=sc.nextInt();  
  29.    a=new int[n][m-1];  
  30.    for(int j=0; j<n; j++){  
  31.     String s=sc.next();  
  32.     for(int i=0; i<m-1; i++){  
  33.      a[j][i]=s.charAt(i)-'0';  
  34.     }  
  35.    }  
  36.    solve();  
  37.   }  
  38.  }  
  39.   
  40.  void solve(){  
  41.   if(check()){  
  42.    println("0");  
  43.    return;  
  44.   }  
  45.   
  46.   for(int j=0; j<n; j++){  
  47.    for(int i=0; i<m-1; i++){  
  48.     if(a[j][i]==1){  
  49.      continue;  
  50.     }  
  51.     if(i<m-2&&a[j][i+1]==1){  
  52.      continue;  
  53.     }  
  54.     if(i>0&&a[j][i-1]==1){  
  55.      continue;  
  56.     }  
  57.     a[j][i]=1;  
  58.     if(check()){  
  59.      println((j+1)+" "+(i+1));  
  60.      return;  
  61.     }  
  62.     a[j][i]=0;  
  63.    }  
  64.   }  
  65.   println("1");  
  66.  }  
  67.   
  68.  boolean check(){  
  69.   int p=start;  
  70.   for(int j=0; j<n; j++){  
  71.    if(p<m-1&&a[j][p]==1){  
  72.     p++;  
  73.    }else if(p>0&&a[j][p-1]==1){  
  74.     p--;  
  75.    }  
  76.   }  
  77.   return p==goal;  
  78.  }  
  79.   
  80.  void debug(Object... os){  
  81.   System.err.println(Arrays.deepToString(os));  
  82.  }  
  83.   
  84.  void print(String s){  
  85.   System.out.print(s);  
  86.  }  
  87.   
  88.  void println(String s){  
  89.   System.out.println(s);  
  90.  }  
  91.   
  92.  public static void main(String[] args){  
  93.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  94.   new Main().run();  
  95.  }  
  96. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Aizu Online Judge 0043 Puzzle

■0043 Puzzle

a[k]=数字kが出てきた回数とする．
a[k]++;とすると，これはkを付け加えた場合に相当する．
あとは，aが条件をみたすかを簡単な探索で解く．

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.   for(; sc.hasNext();){  
  18.    String s=sc.next();  
  19.    int[] a=new int[10];  
  20.    for(int i=0; i<s.length(); i++){  
  21.     a[s.charAt(i)-'0']++;  
  22.    }  
  23.    solve(a);  
  24.   }  
  25.  }  
  26.   
  27.  void solve(int[] a){  
  28.   LinkedList<Integer> list=new LinkedList<Integer>();  
  29.   for(int i=1; i<=9; i++){  
  30.    a[i]++;  
  31.    if(satisfy(a.clone())){  
  32.     list.add(i);  
  33.    }  
  34.    a[i]--;  
  35.   }  
  36.   for(int i=0; i<list.size(); i++){  
  37.    print(list.get(i)+(i==list.size()-1?"\n":" "));  
  38.   }  
  39.   if(list.size()==0){  
  40.    println("0");  
  41.   }  
  42.  }  
  43.   
  44.  boolean satisfy(int[] a){  
  45.   if(!check(a)){  
  46.    return false;  
  47.   }  
  48.   for(int i=1; i<=9; i++){  
  49.    a[i]-=2;  
  50.    if(rec(a, 0)){  
  51.     return true;  
  52.    }  
  53.    a[i]+=2;  
  54.   }  
  55.   return false;  
  56.  }  
  57.   
  58.  boolean rec(int[] a, int n){  
  59.   if(!check(a)){  
  60.    return false;  
  61.   }  
  62.   if(n==4){  
  63.    return true;  
  64.   }  
  65.   for(int i=1; i<=9; i++){  
  66.    a[i]-=3;  
  67.    if(rec(a, n+1)){  
  68.     return true;  
  69.    }  
  70.    a[i]+=3;  
  71.   }  
  72.   for(int i=1; i<=7; i++){  
  73.    a[i]--;  
  74.    a[i+1]--;  
  75.    a[i+2]--;  
  76.    if(rec(a, n+1)){  
  77.     return true;  
  78.    }  
  79.    a[i]++;  
  80.    a[i+1]++;  
  81.    a[i+2]++;  
  82.   }  
  83.   return false;  
  84.  }  
  85.   
  86.  boolean check(int[] a){  
  87.   for(int e : a){  
  88.    if(e<0||e>4){  
  89.     return false;  
  90.    }  
  91.   }  
  92.   return true;  
  93.  }  
  94.   
  95.  void debug(Object... os){  
  96.   System.err.println(Arrays.deepToString(os));  
  97.  }  
  98.   
  99.  void print(String s){  
  100.   System.out.print(s);  
  101.  }  
  102.   
  103.  void println(String s){  
  104.   System.out.println(s);  
  105.  }  
  106.   
  107.  public static void main(String[] args){  
  108.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
  109.   new Main().run();  
  110.  }  
  111. }  
投稿者 時刻: 0 件のコメント:
ラベル:

Prologでanarchy golf 001 hello world

さて，久し振りの記事は，「Prologでショートコーディング」です．

Prologを少しずつやってはいるものの，入出力関係にはどうしても疎いままなので，演習がてらにやってみよう，というわけです．

まずは，Hello, world!から

anarchy golf - hello world

m:-write('Hello, world!').

とても簡単26B．anarchy golfでは，"m"という述語から実行されます．

投稿者 時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)