Aizu Online Judge 0202 At Boss's Expense

■0202 At Boss's Expense

可能な合計金額と，素数全列挙．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, x;
 int[] a;

 void run(){
  for(;;){
   n=sc.nextInt();
   x=sc.nextInt();
   if((n|x)==0){
    break;
   }
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int max=1000000;
  int p=0;
  int[] prime=new int[max];
  boolean[] isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }
  boolean[] dp=new boolean[max+1];
  dp[0]=true;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<=max; i++){
    dp[i]|=dp[i-a[j]];
   }
  }
  int ans=0;
  for(int i=2; i<=x; i++){
   if(dp[i]&&isPrime[i]){
    ans=i;
   }
  }
  if(ans>0){
   println(ans+"");
  }else{
   println("NA");
  }
 }

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

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

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

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

Aizu Online Judge 0201 Wrought Gold Master

■0201 Wrought Gold Master

DFS．あるアイテムについてそれ自身を買う，あるいはレシピを用いて錬金するという両手法を試し，最小を返す．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, m;
 HashMap<String, Integer> val;
 HashMap<String, LinkedList<String>> recipe;
 String item;

 void run(){
  for(;;){
   val=new HashMap<String, Integer>();
   recipe=new HashMap<String, LinkedList<String>>();
   n=sc.nextInt();
   if(n==0){
    break;
   }
   for(int i=0; i<n; i++){
    String s=sc.next();
    int d=sc.nextInt();
    val.put(s, d);
   }
   m=sc.nextInt();
   for(int j=0; j<m; j++){
    String s=sc.next();
    int k=sc.nextInt();
    LinkedList<String> list=new LinkedList<String>();
    for(int i=0; i<k; i++){
     String t=sc.next();
     list.add(t);
    }
    recipe.put(s, list);
   }
   item=sc.next();
   solve();
  }
 }

 void solve(){
  println(dfs(item)+"");
 }

 int dfs(String s){
  int res=INF;
  if(val.containsKey(s)){
   res=min(res, val.get(s));
  }
  if(recipe.containsKey(s)){
   int sum=0;
   for(String t : recipe.get(s)){
    sum+=dfs(t);
   }
   res=min(res, sum);
  }
  return res;
 }

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

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

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

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

Aizu Online Judge 0200 Traveling Alone: One-way Ticket of Youth

■0200 Traveling Alone: One-way Ticket of Youth

Warshall-Floyd．O(n³)でn=300なので，多分間に合うだろうという魂胆．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int[][] cost, time;
 int n, m, k;

 void run(){
  for(;;){
   n=sc.nextInt();
   m=sc.nextInt();
   if((n|m)==0){
    break;
   }
   cost=new int[m][m];
   time=new int[m][m];
   for(int j=0; j<m; j++){
    fill(cost[j], INF);
    fill(time[j], INF);
   }
   for(int i=0; i<n; i++){
    int a=sc.nextInt()-1;
    int b=sc.nextInt()-1;
    int c=sc.nextInt();
    int t=sc.nextInt();
    cost[a][b]=cost[b][a]=c;
    time[a][b]=time[b][a]=t;
   }
   for(int k=0; k<m; k++){
    for(int i=0; i<m; i++){
     for(int j=0; j<m; j++){
      cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);
      time[i][j]=min(time[i][j], time[i][k]+time[k][j]);
     }
    }
   }
   k=sc.nextInt();
   for(int i=0; i<k; i++){
    int p=sc.nextInt()-1;
    int q=sc.nextInt()-1;
    int r=sc.nextInt();
    if(r==0){
     println(cost[p][q]+"");
    }else{
     println(time[p][q]+"");
    }
   }
  }
 }

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

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

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

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

Aizu Online Judge 0197 Greatest Common Divisor: Euclidean Algorithm

■0197 Greatest Common Divisor: Euclidean Algorithm

やるだけ．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 void run(){
  for(;;){
   int x=sc.nextInt();
   int y=sc.nextInt();
   if((x|y)==0){
    break;
   }
   if(x<y){
    int t=x;
    x=y;
    y=t;
   }
   for(int i=0;; i++){
    if(y==0){
     println(x+" "+i);
     break;
    }
    x=x%y;
    int t=x;
    x=y;
    y=t;
   }
  }
 }

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

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

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

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

Aizu Online Judge 0196 Baseball Championship

■0196 Baseball Championship

やるだけ．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 void run(){
  for(;;){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   R[] rs=new R[n];
   for(int j=0; j<n; j++){
    rs[j]=new R();
    rs[j].name=sc.next();
    for(int i=0; i<n-1; i++){
     switch(sc.nextInt()){
     case 0:
      rs[j].win--;
      break;
     case 1:
      rs[j].lose++;
      break;
     }
    }
   }
   Arrays.sort(rs);
   for(R r : rs){
    println(r.name);
   }
  }
 }

 class R implements Comparable<R>{
  int win, lose;
  String name;

  @Override
  public int compareTo(R r){
   if(win!=r.win){
    return win-r.win;
   }else{
    return lose-r.lose;
   }
  }
 }

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

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

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

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

Aizu Online Judge 0195 What is the Most Popular Shop in Tokaichi?

■0195 What is the Most Popular Shop in Tokaichi?

やるだけ．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 void run(){
  for(;;){
   int n=5;
   int max=0;
   char c='A';
   for(int i=0; i<n; i++){
    int a=sc.nextInt()+sc.nextInt();
    if(a==0){
     return;
    }
    if(a>max){
     c=(char)('A'+i);
     max=a;
    }
   }
   println(c+" "+max);
  }
 }

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

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

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

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

Aizu Online Judge 0189 Convenient Location

■0189 Convenient Location

各々のノードのついて，Dijkstraをやるだけ．

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n, m;
 LinkedList<E>[] es;

 @SuppressWarnings("unchecked")
 void run(){
  for(;;){
   es=new LinkedList[10];
   for(int i=0; i<es.length; i++){
    es[i]=new LinkedList<E>();
   }
   n=0;
   m=sc.nextInt();
   if(m==0){
    break;
   }
   for(int i=0; i<m; i++){
    int u=sc.nextInt();
    int v=sc.nextInt();
    int w=sc.nextInt();
    es[u].add(new E(v, w));
    es[v].add(new E(u, w));
    n=max(n, u+1);
    n=max(n, v+1);
   }
   solve();
  }
 }

 void solve(){
  int min=INF;
  int v=0;
  for(int i=0; i<n; i++){
   int d=dijkstra(i);
   if(d<min){
    v=i;
    min=d;
   }
  }
  println(v+" "+min);
 }

 int dijkstra(int s){
  int[] d=new int[n];
  PriorityQueue<P> que=new PriorityQueue<P>();

  Arrays.fill(d, INF);
  d[s]=0;
  que.offer(new P(s, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to]>d[p.v]+e.cost){
     d[e.to]=d[p.v]+e.cost;
     que.offer(new P(e.to, d[e.to]));
    }
   }
  }

  int res=0;
  for(int i=0; i<n; i++){
   res+=d[i];
  }
  return res;
 }

 class E{
  int to, cost;

  E(int to, int cost){
   this.to=to;
   this.cost=cost;
  }
 }

 class P implements Comparable<P>{
  int v, d;

  P(int v, int d){
   this.v=v;
   this.d=d;
  }

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

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

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

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

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

Aizu Online Judge 0185 Goldbach's Conjecture II

■0185 Goldbach's Conjecture II

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

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 int max=1000000;
 int[] prime;
 boolean[] isPrime;

 void run(){
  int p=0;
  prime=new int[max];
  isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }

  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   int ans=0;
   for(int i=0; i<p; i++){
    if(prime[i]>n/2){
     break;
    }
    if(isPrime[n-prime[i]]){
     ans++;
    }
   }
   println(""+ans);
  }
 }

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

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

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

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