今月の〇〇(2011年3月)

■Aizu Online Judge

Solved:235/43th
Rating:151.76/67th
簡単な問題ばかり解いていたので，Ratingの順位がやや低めです．ということで来月の目標はRating200にしました．

■TopCoder/Codeforces

ほとんど参加できていません．そのためレーティングも代わり映えしていません．そのため来月は，レーティングの昇降は兎も角として，出来るだけ参加することを重視しようと思います．

■専門書

「計算理論の基礎」を読み進めています．5章辺りを読んでいますが，練習問題に全く手を付けていないため，そちらにも着手する必要がありそうです．また，「コンピュータの数学」は今の自分なら十分読めると判断したため，そろそろ真面目に読もうかと考えている次第です．

Aizu Online Judge 0125 Day Count

■0125 Day Count

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.  void run(){  
14.   for(;;){  
15.    int y1=sc.nextInt();  
16.    int m1=sc.nextInt();  
17.    int d1=sc.nextInt();  
18.    int y2=sc.nextInt();  
19.    int m2=sc.nextInt();  
20.    int d2=sc.nextInt();  
21.    if(y1<0||m1<0||d1<0||y2<0||m2<0||d2<0){  
22.     break;  
23.    }  
24.    int a=day(y1, m1, d1);  
25.    int b=day(y2, m2, d2);  
26.    println((b-a)+"");  
27.   }  
28.  }  
29.   
30.  int day(int y, int m, int d){  
31.   int res=0;  
32.   int[] days={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};  
33.   for(int i=0; i<m-1; i++){  
34.    res+=days[i];  
35.   }  
36.   res+=y*365+d-1;  
37.   if((m==2&&d<=28)||m==1){  
38.    y--;  
39.   }  
40.   if(y>=0){  
41.    res+=y/4+1;  
42.    res-=y/100+1;  
43.    res+=y/400+1;  
44.   }  
45.   return res;  
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.   new Main().run();  
62.  }  
63. }  

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

public class Main{

 Scanner sc=new Scanner(System.in);;

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

 void run(){
  for(;;){
   int y1=sc.nextInt();
   int m1=sc.nextInt();
   int d1=sc.nextInt();
   int y2=sc.nextInt();
   int m2=sc.nextInt();
   int d2=sc.nextInt();
   if(y1<0||m1<0||d1<0||y2<0||m2<0||d2<0){
    break;
   }
   int a=day(y1, m1, d1);
   int b=day(y2, m2, d2);
   println((b-a)+"");
  }
 }

 int day(int y, int m, int d){
  int res=0;
  int[] days={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  for(int i=0; i<m-1; i++){
   res+=days[i];
  }
  res+=y*365+d-1;
  if((m==2&&d<=28)||m==1){
   y--;
  }
  if(y>=0){
   res+=y/4+1;
   res-=y/100+1;
   res+=y/400+1;
  }
  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){
  new Main().run();
 }
}

Aizu Online Judge 0121 Seven Puzzle

■0121 Seven Puzzle

先に，全てのパターンについて最小ステップ数を計算しておく．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.  HashMap<Integer, Integer> map;  
17.  int[] a;  
18.  int w=4, h=2;  
19.   
20.  void run(){  
21.   a=new int[w*h];  
22.   init();  
23.   for(; sc.hasNext();){  
24.    for(int i=0; i<w*h; i++){  
25.     a[i]=sc.nextInt();  
26.    }  
27.    println(""+map.get(id(a)));  
28.   }  
29.  }  
30.   
31.  void init(){  
32.   
33.   LinkedList<S> que=new LinkedList<S>();  
34.   map=new HashMap<Integer, Integer>();  
35.   
36.   que.offer(new S(0, 0, new int[]{0, 1, 2, 3, 4, 5, 6, 7}));  
37.   map.put(id(que.peek().a), 0);  
38.   int[] dx={0, 0, -1, 1};  
39.   int[] dy={-1, 1, 0, 0};  
40.   
41.   for(; !que.isEmpty();){  
42.    S s=que.poll();  
43.    int p=s.y*w+s.x;  
44.    for(int i=0; i<4; i++){  
45.     int x2=s.x+dx[i];  
46.     int y2=s.y+dy[i];  
47.     int p2=y2*w+x2;  
48.     if(x2>=0&&x2<w&&y2>=0&&y2<h){  
49.      int[] a2=s.a.clone();  
50.      int t=a2[p];  
51.      a2[p]=a2[p2];  
52.      a2[p2]=t;  
53.      S s2=new S(x2, y2, a2);  
54.      if(!map.containsKey(id(s2.a))){  
55.       que.offer(s2);  
56.       map.put(id(s2.a), map.get(id(s.a))+1);  
57.      }  
58.     }  
59.    }  
60.   }  
61.  }  
62.   
63.  int id(int[] a){  
64.   int res=0;  
65.   for(int e : a){  
66.    res=res*10+e;  
67.   }  
68.   return res;  
69.  }  
70.   
71.  class S{  
72.   int x, y;  
73.   int[] a;  
74.   
75.   S(int x, int y, int[] a){  
76.    this.x=x;  
77.    this.y=y;  
78.    this.a=a;  
79.   }  
80.  }  
81.   
82.  void debug(Object... os){  
83.   System.err.println(Arrays.deepToString(os));  
84.  }  
85.   
86.  void print(String s){  
87.   System.out.print(s);  
88.  }  
89.   
90.  void println(String s){  
91.   System.out.println(s);  
92.  }  
93.   
94.  public static void main(String[] args){  
95.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
96.   new Main().run();  
97.  }  
98. }  

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;

 HashMap<Integer, Integer> map;
 int[] a;
 int w=4, h=2;

 void run(){
  a=new int[w*h];
  init();
  for(; sc.hasNext();){
   for(int i=0; i<w*h; i++){
    a[i]=sc.nextInt();
   }
   println(""+map.get(id(a)));
  }
 }

 void init(){

  LinkedList<S> que=new LinkedList<S>();
  map=new HashMap<Integer, Integer>();

  que.offer(new S(0, 0, new int[]{0, 1, 2, 3, 4, 5, 6, 7}));
  map.put(id(que.peek().a), 0);
  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  for(; !que.isEmpty();){
   S s=que.poll();
   int p=s.y*w+s.x;
   for(int i=0; i<4; i++){
    int x2=s.x+dx[i];
    int y2=s.y+dy[i];
    int p2=y2*w+x2;
    if(x2>=0&&x2<w&&y2>=0&&y2<h){
     int[] a2=s.a.clone();
     int t=a2[p];
     a2[p]=a2[p2];
     a2[p2]=t;
     S s2=new S(x2, y2, a2);
     if(!map.containsKey(id(s2.a))){
      que.offer(s2);
      map.put(id(s2.a), map.get(id(s.a))+1);
     }
    }
   }
  }
 }

 int id(int[] a){
  int res=0;
  for(int e : a){
   res=res*10+e;
  }
  return res;
 }

 class S{
  int x, y;
  int[] a;

  S(int x, int y, int[] a){
   this.x=x;
   this.y=y;
   this.a=a;
  }
 }

 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 0120 Patisserie

■0120 Patisserie

r₁のロールケーキにr₂のロールケーキを並べると，
長さが2√(r₁r₂)-r₁+r₂だけ増える．
dp[k][S]=右端がロールケーキk，集合Sのロールケーキを既に並べたとしたときの最小の長さ
としてDP．計算量はO(2ⁿn²)．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int len, n;  
17.  int[] a;  
18.   
19.  void run(){  
20.   for(;sc.hasNext();){  
21.    String[] ss=sc.nextLine().split(" ");  
22.    len=Integer.parseInt(ss[0]);  
23.    n=ss.length-1;  
24.    a=new int[n];  
25.    for(int i=0; i<n; i++){  
26.     a[i]=Integer.parseInt(ss[i+1]);  
27.    }  
28.    solve();  
29.   }  
30.  }  
31.   
32.  void solve(){  
33.   double[][] dp=new double[1<<n][n];  
34.   for(int j=0; j<1<<n; j++){  
35.    fill(dp[j], INF);  
36.   }  
37.   for(int i=0; i<n; i++){  
38.    dp[1<<i][i]=2*a[i];  
39.   }  
40.   for(int s=1; s<1<<n; s++){  
41.    for(int j=0; j<n; j++){  
42.     if((s>>j&1)==0){  
43.      continue;  
44.     }  
45.     for(int i=0; i<n; i++){  
46.      if((s>>i&1)==0){  
47.       dp[s|1<<i][i]=min(dp[s|1<<i][i],  
48.         dp[s][j]+2*sqrt(a[j]*a[i])-a[j]+a[i]);  
49.      }  
50.     }  
51.    }  
52.   }  
53.   double min=INF;  
54.   for(int i=0; i<n; i++){  
55.    min=min(min, dp[(1<<n)-1][i]);  
56.   }  
57.   println(min<len+EPS?"OK":"NA");  
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. }  

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

 void run(){
  for(;sc.hasNext();){
   String[] ss=sc.nextLine().split(" ");
   len=Integer.parseInt(ss[0]);
   n=ss.length-1;
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=Integer.parseInt(ss[i+1]);
   }
   solve();
  }
 }

 void solve(){
  double[][] dp=new double[1<<n][n];
  for(int j=0; j<1<<n; j++){
   fill(dp[j], INF);
  }
  for(int i=0; i<n; i++){
   dp[1<<i][i]=2*a[i];
  }
  for(int s=1; s<1<<n; s++){
   for(int j=0; j<n; j++){
    if((s>>j&1)==0){
     continue;
    }
    for(int i=0; i<n; i++){
     if((s>>i&1)==0){
      dp[s|1<<i][i]=min(dp[s|1<<i][i],
        dp[s][j]+2*sqrt(a[j]*a[i])-a[j]+a[i]);
     }
    }
   }
  }
  double min=INF;
  for(int i=0; i<n; i++){
   min=min(min, dp[(1<<n)-1][i]);
  }
  println(min<len+EPS?"OK":"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 0514 Quality Checking

■0514 Quality Checking

合格

→3つ共正常

失敗

→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.  void run(){  
17.   for(;;){  
18.    int na, nb, nc;  
19.    na=sc.nextInt();  
20.    nb=sc.nextInt();  
21.    nc=sc.nextInt();  
22.    if((na|nb|nc)==0){  
23.     break;  
24.    }  
25.   
26.    int n=sc.nextInt();  
27.    int[] as=new int[na];  
28.    int[] bs=new int[nb];  
29.    int[] cs=new int[nc];  
30.    Arrays.fill(as, 2);  
31.    Arrays.fill(bs, 2);  
32.    Arrays.fill(cs, 2);  
33.   
34.    R[] rs=new R[n];  
35.    for(int i=0; i<n; i++){  
36.     int a=sc.nextInt()-1;  
37.     int b=sc.nextInt()-na-1;  
38.     int c=sc.nextInt()-na-nb-1;  
39.     int r=sc.nextInt();  
40.     rs[i]=new R(a, b, c, r);  
41.     if(r==1){  
42.      as[a]=1;  
43.      bs[b]=1;  
44.      cs[c]=1;  
45.     }  
46.    }  
47.   
48.    for(int i=0; i<n; i++){  
49.     if(rs[i].r==0){  
50.      int a=as[rs[i].a];  
51.      int b=bs[rs[i].b];  
52.      int c=cs[rs[i].c];  
53.      if(a==1&&b==1){  
54.       c=0;  
55.      }else if(b==1&&c==1){  
56.       a=0;  
57.      }else if(c==1&&a==1){  
58.       b=0;  
59.      }  
60.      as[rs[i].a]=a;  
61.      bs[rs[i].b]=b;  
62.      cs[rs[i].c]=c;  
63.     }  
64.    }  
65.    for(int i=0; i<na; i++){  
66.     println(as[i]+"");  
67.    }  
68.    for(int i=0; i<nb; i++){  
69.     println(bs[i]+"");  
70.    }  
71.    for(int i=0; i<nc; i++){  
72.     println(cs[i]+"");  
73.    }  
74.   }  
75.  }  
76.   
77.  class R{  
78.   int a, b, c, r;  
79.   
80.   R(int a, int b, int c, int r){  
81.    this.a=a;  
82.    this.b=b;  
83.    this.c=c;  
84.    this.r=r;  
85.   }  
86.  }  
87.   
88.  void debug(Object... os){  
89.   System.err.println(Arrays.deepToString(os));  
90.  }  
91.   
92.  void print(String s){  
93.   System.out.print(s);  
94.  }  
95.   
96.  void println(String s){  
97.   System.out.println(s);  
98.  }  
99.   
100.  public static void main(String[] args){  
101.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
102.   new Main().run();  
103.  }  
104. }  

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 na, nb, nc;
   na=sc.nextInt();
   nb=sc.nextInt();
   nc=sc.nextInt();
   if((na|nb|nc)==0){
    break;
   }

   int n=sc.nextInt();
   int[] as=new int[na];
   int[] bs=new int[nb];
   int[] cs=new int[nc];
   Arrays.fill(as, 2);
   Arrays.fill(bs, 2);
   Arrays.fill(cs, 2);

   R[] rs=new R[n];
   for(int i=0; i<n; i++){
    int a=sc.nextInt()-1;
    int b=sc.nextInt()-na-1;
    int c=sc.nextInt()-na-nb-1;
    int r=sc.nextInt();
    rs[i]=new R(a, b, c, r);
    if(r==1){
     as[a]=1;
     bs[b]=1;
     cs[c]=1;
    }
   }

   for(int i=0; i<n; i++){
    if(rs[i].r==0){
     int a=as[rs[i].a];
     int b=bs[rs[i].b];
     int c=cs[rs[i].c];
     if(a==1&&b==1){
      c=0;
     }else if(b==1&&c==1){
      a=0;
     }else if(c==1&&a==1){
      b=0;
     }
     as[rs[i].a]=a;
     bs[rs[i].b]=b;
     cs[rs[i].c]=c;
    }
   }
   for(int i=0; i<na; i++){
    println(as[i]+"");
   }
   for(int i=0; i<nb; i++){
    println(bs[i]+"");
   }
   for(int i=0; i<nc; i++){
    println(cs[i]+"");
   }
  }
 }

 class R{
  int a, b, c, r;

  R(int a, int b, int c, int r){
   this.a=a;
   this.b=b;
   this.c=c;
   this.r=r;
  }
 }

 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 0231 Dangerous Bridge

■0231 Dangerous Bridge

時刻aと時刻b-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[] m, a, b;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    if(n==0){  
23.     break;  
24.    }  
25.    m=new int[n];  
26.    a=new int[n];  
27.    b=new int[n];  
28.    for(int i=0; i<n; i++){  
29.     m[i]=sc.nextInt();  
30.     a[i]=sc.nextInt();  
31.     b[i]=sc.nextInt();  
32.    }  
33.    solve();  
34.   }  
35.  }  
36.   
37.  void solve(){  
38.   for(int j=0; j<n; j++){  
39.    int sum1=0, sum2=0;  
40.    for(int i=0; i<n; i++){  
41.     if(a[i]<=a[j]&&a[j]<b[i]){  
42.      sum1+=m[i];  
43.     }  
44.     if(a[i]<=b[j]-1&&b[j]-1<b[i]){  
45.      sum2+=m[i];  
46.     }  
47.    }  
48.    if(sum1>150||sum2>150){  
49.     println("NG");  
50.     return;  
51.    }  
52.   }  
53.   println("OK");  
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. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int n;
 int[] m, a, b;

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

 void solve(){
  for(int j=0; j<n; j++){
   int sum1=0, sum2=0;
   for(int i=0; i<n; i++){
    if(a[i]<=a[j]&&a[j]<b[i]){
     sum1+=m[i];
    }
    if(a[i]<=b[j]-1&&b[j]-1<b[i]){
     sum2+=m[i];
    }
   }
   if(sum1>150||sum2>150){
    println("NG");
    return;
   }
  }
  println("OK");
 }

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

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

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

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

Codeforces Round #61 (Div. 2)

コンテストが随分ご無沙汰だったので参加してきました．

Codeforces Round #61 (Div. 2)

A. Petya and Java

面倒だったので，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 A{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  void run(){  
16.   BigInteger b=sc.nextBigInteger();  
17.   long[] s={-128, -32768, -2147483648, -9223372036854775808L};  
18.   long[] e={127, 32767, 2147483647, 9223372036854775807L};  
19.   String[] ss={"byte", "short", "int", "long"};  
20.   for(int i=0; i<4; i++){  
21.    if(b.compareTo(new BigInteger(s[i]+""))>=0  
22.      &&b.compareTo(new BigInteger(e[i]+""))<=0){  
23.     println(ss[i]);  
24.     return;  
25.    }  
26.   }  
27.   println("BigInteger");  
28.  }  
29.   
30.  void println(String s){  
31.   System.out.println(s);  
32.  }  
33.   
34.  void print(String s){  
35.   System.out.print(s);  
36.  }  
37.   
38.  void debug(Object... os){  
39.   System.err.println(Arrays.deepToString(os));  
40.  }  
41.   
42.  public static void main(String[] args){  
43.   new A().run();  
44.  }  
45. }  

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

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

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

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

 void run(){
  BigInteger b=sc.nextBigInteger();
  long[] s={-128, -32768, -2147483648, -9223372036854775808L};
  long[] e={127, 32767, 2147483647, 9223372036854775807L};
  String[] ss={"byte", "short", "int", "long"};
  for(int i=0; i<4; i++){
   if(b.compareTo(new BigInteger(s[i]+""))>=0
     &&b.compareTo(new BigInteger(e[i]+""))<=0){
    println(ss[i]);
    return;
   }
  }
  println("BigInteger");
 }

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

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

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

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

B. Petya and Countryside

全探索すれば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 B{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  int n;  
16.  int[] a;  
17.   
18.  void run(){  
19.   n=sc.nextInt();  
20.   a=new int[n];  
21.   for(int i=0; i<n; i++){  
22.    a[i]=sc.nextInt();  
23.   }  
24.   int max=0;  
25.   for(int j=0; j<n; j++){  
26.    int s=1;  
27.    for(int i=j-1; i>=0; i--){  
28.     if(a[i]<=a[i+1]){  
29.      s++;  
30.     }else{  
31.      break;  
32.     }  
33.    }  
34.    for(int i=j+1; i<n; i++){  
35.     if(a[i-1]>=a[i]){  
36.      s++;  
37.     }else{  
38.      break;  
39.     }  
40.    }  
41.    max=max(max, s);  
42.   }  
43.   println(max+"");  
44.  }  
45.   
46.  void println(String s){  
47.   System.out.println(s);  
48.  }  
49.   
50.  void print(String s){  
51.   System.out.print(s);  
52.  }  
53.   
54.  void debug(Object... os){  
55.   System.err.println(Arrays.deepToString(os));  
56.  }  
57.   
58.  public static void main(String[] args){  
59.   new B().run();  
60.  }  
61. }  

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

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

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

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

 int n;
 int[] a;

 void run(){
  n=sc.nextInt();
  a=new int[n];
  for(int i=0; i<n; i++){
   a[i]=sc.nextInt();
  }
  int max=0;
  for(int j=0; j<n; j++){
   int s=1;
   for(int i=j-1; i>=0; i--){
    if(a[i]<=a[i+1]){
     s++;
    }else{
     break;
    }
   }
   for(int i=j+1; i<n; i++){
    if(a[i-1]>=a[i]){
     s++;
    }else{
     break;
    }
   }
   max=max(max, s);
  }
  println(max+"");
 }

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

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

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

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

C. Petya and File System

書けば通ると思いましたが，落ちてしまいました．

D. Petya and His Friends

私が考えたのは以下のやり方．

a1	a2	a3	a4	…	an
2	2	2	2	…
	3	3	3	…	3
5		5	5	…	5
7	7		7	…	7

これを縦に掛けたものがそれぞれ答え．

実際には，6, 10, 15, 15*2, 15*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 D{  
10.  Scanner sc=new Scanner(System.in);  
11.   
12.  int INF=1<<28;  
13.  double EPS=1e-9;  
14.   
15.  void run(){  
16.   int n=sc.nextInt();  
17.   if(n==2){  
18.    println("-1");  
19.    return;  
20.   }  
21.   BigInteger[] bis=new BigInteger[n];  
22.   for(int i=0; i<n; i++){  
23.    bis[i]=BigInteger.ONE;  
24.   }  
25.   
26.   int max=1000;  
27.   int p=0;  
28.   int[] prime=new int[max];  
29.   boolean[] isPrime=new boolean[max+1];  
30.   Arrays.fill(isPrime, true);  
31.   isPrime[0]=isPrime[1]=false;  
32.   for(int i=2; i<=max; i++){  
33.    if(isPrime[i]){  
34.     prime[p++]=i;  
35.     for(int j=2*i; j<=max; j+=i){  
36.      isPrime[j]=false;  
37.     }  
38.    }  
39.   }  
40.   
41.   for(int j=0; j<n; j++){  
42.    BigInteger bi=new BigInteger(prime[j]+"");  
43.    for(int i=0; i<n-1; i++){  
44.     bis[(j+i)%n]=bis[(j+i)%n].multiply(bi);  
45.    }  
46.   }  
47.   for(int i=0; i<n; i++){  
48.    if(bis[i].toString().length()>100){  
49.     println("-1");  
50.     return;  
51.    }  
52.   }  
53.   for(int i=0; i<n; i++){  
54.    println(bis[i]+"");  
55.   }  
56.  }  
57.   
58.  void println(String s){  
59.   System.out.println(s);  
60.  }  
61.   
62.  void print(String s){  
63.   System.out.print(s);  
64.  }  
65.   
66.  void debug(Object... os){  
67.   System.err.println(Arrays.deepToString(os));  
68.  }  
69.   
70.  public static void main(String[] args){  
71.   new D().run();  
72.  }  
73. }  

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

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

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

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

 void run(){
  int n=sc.nextInt();
  if(n==2){
   println("-1");
   return;
  }
  BigInteger[] bis=new BigInteger[n];
  for(int i=0; i<n; i++){
   bis[i]=BigInteger.ONE;
  }

  int max=1000;
  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;
    }
   }
  }

  for(int j=0; j<n; j++){
   BigInteger bi=new BigInteger(prime[j]+"");
   for(int i=0; i<n-1; i++){
    bis[(j+i)%n]=bis[(j+i)%n].multiply(bi);
   }
  }
  for(int i=0; i<n; i++){
   if(bis[i].toString().length()>100){
    println("-1");
    return;
   }
  }
  for(int i=0; i<n; i++){
   println(bis[i]+"");
  }
 }

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

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

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

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

ooxo- 3226p 68位
1506 -> 1694
紫コーダーになりました．

Aizu Online Judge 0212 Highway Express Bus

■0212 Highway Express Bus

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

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 c, n, m, s, g;
 LinkedList<E>[] es;

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

 void solve(){
  int[][] d=new int[n][c+1];
  PriorityQueue<P> que=new PriorityQueue<P>();

  for(int i=0; i<n; i++){
   Arrays.fill(d[i], INF);
  }
  d[s][c]=0;
  que.offer(new P(s, c, 0));
  for(; !que.isEmpty();){
   P p=que.poll();
   if(d[p.v][p.c]<p.d){
    continue;
   }
   for(E e : es[p.v]){
    if(d[e.to][p.c]>d[p.v][p.c]+e.cost){
     d[e.to][p.c]=d[p.v][p.c]+e.cost;
     que.offer(new P(e.to, p.c, d[e.to][p.c]));
    }
    if(p.c>0&&d[e.to][p.c-1]>d[p.v][p.c]+e.cost/2){
     d[e.to][p.c-1]=d[p.v][p.c]+e.cost/2;
     que.offer(new P(e.to, p.c-1, d[e.to][p.c-1]));
    }
   }
  }
  int min=INF;
  for(int i=0; i<=c; i++){
   min=min(min, d[g][i]);
  }
  min*=10;
  println(""+min);
 }

 class E{
  int to, cost;

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

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

  P(int v, int c, int d){
   this.v=v;
   this.c=c;
   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 0209 Scene in a Picture

■0209 Scene in a Picture

全探索．

計算量はO(m²n²)だが，100²50²=2.5*10⁷なので余裕．

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, b;  
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[m][m];  
27.    b=new int[n][n];  
28.    for(int j=0; j<m; j++){  
29.     for(int i=0; i<m; i++){  
30.      a[j][i]=sc.nextInt();  
31.     }  
32.    }  
33.    for(int j=0; j<n; j++){  
34.     for(int i=0; i<n; i++){  
35.      b[j][i]=sc.nextInt();  
36.     }  
37.    }  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   int[][][] c=new int[4][n][n];  
44.   for(int j=0; j<n; j++){  
45.    for(int i=0; i<n; i++){  
46.     c[0][j][i]=b[j][i];  
47.     c[1][i][n-1-j]=b[j][i];  
48.     c[2][n-1-j][n-1-i]=b[j][i];  
49.     c[3][n-1-i][j]=b[j][i];  
50.    }  
51.   }  
52.   
53.   int p=m*m;  
54.   for(int i=0; i<4; i++){  
55.    p=min(p, match(c[i]));  
56.   }  
57.   if(p==m*m){  
58.    println("NA");  
59.   }else{  
60.    println((p%m+1)+" "+(p/m+1));  
61.   }  
62.  }  
63.   
64.  int match(int[][] c){  
65.   for(int y=0; y+n<=m; y++){  
66.    for(int x=0; x+n<=m; x++){  
67.     boolean f=true;  
68.     for(int j=0; j<n; j++){  
69.      for(int i=0; i<n; i++){  
70.       f&=c[j][i]==-1||c[j][i]==a[y+j][x+i];  
71.      }  
72.     }  
73.     if(f){  
74.      for(int j=0; j<n; j++){  
75.       for(int i=0; i<n; i++){  
76.        if(c[j][i]!=-1){  
77.         return (y+j)*m+(x+i);  
78.        }  
79.       }  
80.      }  
81.     }  
82.    }  
83.   }  
84.   return m*m;  
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.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
101.   new Main().run();  
102.  }  
103. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int m, n;
 int[][] a, b;

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

 void solve(){
  int[][][] c=new int[4][n][n];
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    c[0][j][i]=b[j][i];
    c[1][i][n-1-j]=b[j][i];
    c[2][n-1-j][n-1-i]=b[j][i];
    c[3][n-1-i][j]=b[j][i];
   }
  }

  int p=m*m;
  for(int i=0; i<4; i++){
   p=min(p, match(c[i]));
  }
  if(p==m*m){
   println("NA");
  }else{
   println((p%m+1)+" "+(p/m+1));
  }
 }

 int match(int[][] c){
  for(int y=0; y+n<=m; y++){
   for(int x=0; x+n<=m; x++){
    boolean f=true;
    for(int j=0; j<n; j++){
     for(int i=0; i<n; i++){
      f&=c[j][i]==-1||c[j][i]==a[y+j][x+i];
     }
    }
    if(f){
     for(int j=0; j<n; j++){
      for(int i=0; i<n; i++){
       if(c[j][i]!=-1){
        return (y+j)*m+(x+i);
       }
      }
     }
    }
   }
  }
  return m*m;
 }

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

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

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

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

Aizu Online Judge 0207 Block

■0207 Block

(xs,ys)から同じ色を持つブロックについてBFS．(xg,yg)が訪問済みであれば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 w, h;  
17.  int sx, sy;  
18.  int gx, gy;  
19.  int[][] a;  
20.   
21.  void run(){  
22.   for(;;){  
23.    w=sc.nextInt();  
24.    h=sc.nextInt();  
25.    if((w|h)==0){  
26.     break;  
27.    }  
28.    sx=sc.nextInt()-1;  
29.    sy=sc.nextInt()-1;  
30.    gx=sc.nextInt()-1;  
31.    gy=sc.nextInt()-1;  
32.    int n=sc.nextInt();  
33.    a=new int[h][w];  
34.    for(int k=0; k<n; k++){  
35.     int c=sc.nextInt();  
36.     int d=sc.nextInt();  
37.     int x=sc.nextInt()-1;  
38.     int y=sc.nextInt()-1;  
39.     for(int j=0; j<2; j++){  
40.      for(int i=0; i<4; i++){  
41.       if(d==0){  
42.        a[y+j][x+i]=c;  
43.       }else{  
44.        a[y+i][x+j]=c;  
45.       }  
46.      }  
47.     }  
48.    }  
49.    solve();  
50.   }  
51.  }  
52.   
53.  void solve(){  
54.   LinkedList<P> que=new LinkedList<P>();  
55.   boolean[][] visited=new boolean[h][w];  
56.   
57.   int[] dx={0, 0, -1, 1};  
58.   int[] dy={-1, 1, 0, 0};  
59.   
60.   que.offer(new P(sx, sy));  
61.   visited[sy][sx]=true;  
62.   
63.   for(; !que.isEmpty();){  
64.    P p=que.poll();  
65.    for(int i=0; i<4; i++){  
66.     P q=new P(p.x+dx[i], p.y+dy[i]);  
67.     if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&a[q.y][q.x]==a[sy][sx]  
68.       &&!visited[q.y][q.x]){  
69.      que.offer(q);  
70.      visited[q.y][q.x]=true;  
71.     }  
72.    }  
73.   }  
74.   println(visited[gy][gx]?"OK":"NG");  
75.  }  
76.   
77.  class P{  
78.   int x, y;  
79.   
80.   P(int x, int y){  
81.    this.x=x;  
82.    this.y=y;  
83.   }  
84.  }  
85.   
86.  void debug(Object... os){  
87.   System.err.println(Arrays.deepToString(os));  
88.  }  
89.   
90.  void print(String s){  
91.   System.out.print(s);  
92.  }  
93.   
94.  void println(String s){  
95.   System.out.println(s);  
96.  }  
97.   
98.  public static void main(String[] args){  
99.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
100.   new Main().run();  
101.  }  
102. }  

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

 void run(){
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   if((w|h)==0){
    break;
   }
   sx=sc.nextInt()-1;
   sy=sc.nextInt()-1;
   gx=sc.nextInt()-1;
   gy=sc.nextInt()-1;
   int n=sc.nextInt();
   a=new int[h][w];
   for(int k=0; k<n; k++){
    int c=sc.nextInt();
    int d=sc.nextInt();
    int x=sc.nextInt()-1;
    int y=sc.nextInt()-1;
    for(int j=0; j<2; j++){
     for(int i=0; i<4; i++){
      if(d==0){
       a[y+j][x+i]=c;
      }else{
       a[y+i][x+j]=c;
      }
     }
    }
   }
   solve();
  }
 }

 void solve(){
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[h][w];

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

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

  for(; !que.isEmpty();){
   P p=que.poll();
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i]);
    if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&a[q.y][q.x]==a[sy][sx]
      &&!visited[q.y][q.x]){
     que.offer(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  println(visited[gy][gx]?"OK":"NG");
 }

 class P{
  int x, y;

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

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

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

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

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

Aizu Online Judge 0203 A New Plan of Aizu Ski Resort

■0203 A New Plan of Aizu Ski Resort

dp[j][i]=(i,j)に到達するまでの滑り方のパターン数
としてDP．
dp[0][i]=
0 - (i,0)に障害物がある
1 - (i,0)に障害物がない
あとは，説明通りに更新していく．dp[n]まで用意しておいて，dp[n-1]とdp[n]の総和が答え．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int 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][m];  
27.    for(int j=0; j<n; j++){  
28.     for(int i=0; i<m; i++){  
29.      a[j][i]=sc.nextInt();  
30.     }  
31.    }  
32.    solve();  
33.   }  
34.  }  
35.   
36.  void solve(){  
37.   long[][] dp=new long[n+1][m];  
38.   for(int i=0; i<m; i++){  
39.    if(a[0][i]==0){  
40.     dp[0][i]=1;  
41.    }  
42.   }  
43.   for(int j=0; j<n-1; j++){  
44.    for(int i=0; i<m; i++){  
45.     switch(a[j][i]){  
46.     case 0:  
47.      if(i-1>=0&&a[j+1][i-1]==0)  
48.       dp[j+1][i-1]+=dp[j][i];  
49.      if(a[j+1][i]!=1)  
50.       dp[j+1][i]+=dp[j][i];  
51.      if(i+1<m&&a[j+1][i+1]==0)  
52.       dp[j+1][i+1]+=dp[j][i];  
53.      break;  
54.     case 2:  
55.      if(j>=n-2||a[j+2][i]!=1)  
56.       dp[j+2][i]+=dp[j][i];  
57.      break;  
58.     }  
59.    }  
60.   }  
61.   long ans=0;  
62.   for(int j=n-1; j<n+1; j++){  
63.    for(int i=0; i<m; i++){  
64.     ans+=dp[j][i];  
65.    }  
66.   }  
67.   println(ans+"");  
68.  }  
69.   
70.  void debug(Object... os){  
71.   System.err.println(Arrays.deepToString(os));  
72.  }  
73.   
74.  void print(String s){  
75.   System.out.print(s);  
76.  }  
77.   
78.  void println(String s){  
79.   System.out.println(s);  
80.  }  
81.   
82.  public static void main(String[] args){  
83.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
84.   new Main().run();  
85.  }  
86. }  

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

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

public class Main{

 Scanner sc=new Scanner(System.in);

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

 int m, n;
 int[][] a;

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

 void solve(){
  long[][] dp=new long[n+1][m];
  for(int i=0; i<m; i++){
   if(a[0][i]==0){
    dp[0][i]=1;
   }
  }
  for(int j=0; j<n-1; j++){
   for(int i=0; i<m; i++){
    switch(a[j][i]){
    case 0:
     if(i-1>=0&&a[j+1][i-1]==0)
      dp[j+1][i-1]+=dp[j][i];
     if(a[j+1][i]!=1)
      dp[j+1][i]+=dp[j][i];
     if(i+1<m&&a[j+1][i+1]==0)
      dp[j+1][i+1]+=dp[j][i];
     break;
    case 2:
     if(j>=n-2||a[j+2][i]!=1)
      dp[j+2][i]+=dp[j][i];
     break;
    }
   }
  }
  long ans=0;
  for(int j=n-1; j<n+1; j++){
   for(int i=0; i<m; i++){
    ans+=dp[j][i];
   }
  }
  println(ans+"");
 }

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

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

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

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

Aizu Online Judge 0202 At Boss's Expense

■0202 At Boss's Expense

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

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, x;  
17.  int[] a;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    x=sc.nextInt();  
23.    if((n|x)==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 max=1000000;  
36.   int p=0;  
37.   int[] prime=new int[max];  
38.   boolean[] isPrime=new boolean[max+1];  
39.   Arrays.fill(isPrime, true);  
40.   isPrime[0]=isPrime[1]=false;  
41.   for(int i=2; i<=max; i++){  
42.    if(isPrime[i]){  
43.     prime[p++]=i;  
44.     for(int j=2*i; j<=max; j+=i){  
45.      isPrime[j]=false;  
46.     }  
47.    }  
48.   }  
49.   boolean[] dp=new boolean[max+1];  
50.   dp[0]=true;  
51.   for(int j=0; j<n; j++){  
52.    for(int i=a[j]; i<=max; i++){  
53.     dp[i]|=dp[i-a[j]];  
54.    }  
55.   }  
56.   int ans=0;  
57.   for(int i=2; i<=x; i++){  
58.    if(dp[i]&&isPrime[i]){  
59.     ans=i;  
60.    }  
61.   }  
62.   if(ans>0){  
63.    println(ans+"");  
64.   }else{  
65.    println("NA");  
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. }  

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, m;  
17.  HashMap<String, Integer> val;  
18.  HashMap<String, LinkedList<String>> recipe;  
19.  String item;  
20.   
21.  void run(){  
22.   for(;;){  
23.    val=new HashMap<String, Integer>();  
24.    recipe=new HashMap<String, LinkedList<String>>();  
25.    n=sc.nextInt();  
26.    if(n==0){  
27.     break;  
28.    }  
29.    for(int i=0; i<n; i++){  
30.     String s=sc.next();  
31.     int d=sc.nextInt();  
32.     val.put(s, d);  
33.    }  
34.    m=sc.nextInt();  
35.    for(int j=0; j<m; j++){  
36.     String s=sc.next();  
37.     int k=sc.nextInt();  
38.     LinkedList<String> list=new LinkedList<String>();  
39.     for(int i=0; i<k; i++){  
40.      String t=sc.next();  
41.      list.add(t);  
42.     }  
43.     recipe.put(s, list);  
44.    }  
45.    item=sc.next();  
46.    solve();  
47.   }  
48.  }  
49.   
50.  void solve(){  
51.   println(dfs(item)+"");  
52.  }  
53.   
54.  int dfs(String s){  
55.   int res=INF;  
56.   if(val.containsKey(s)){  
57.    res=min(res, val.get(s));  
58.   }  
59.   if(recipe.containsKey(s)){  
60.    int sum=0;  
61.    for(String t : recipe.get(s)){  
62.     sum+=dfs(t);  
63.    }  
64.    res=min(res, sum);  
65.   }  
66.   return res;  
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. }  

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なので，多分間に合うだろうという魂胆．

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[][] cost, time;  
17.  int n, m, k;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    m=sc.nextInt();  
23.    if((n|m)==0){  
24.     break;  
25.    }  
26.    cost=new int[m][m];  
27.    time=new int[m][m];  
28.    for(int j=0; j<m; j++){  
29.     fill(cost[j], INF);  
30.     fill(time[j], INF);  
31.    }  
32.    for(int i=0; i<n; i++){  
33.     int a=sc.nextInt()-1;  
34.     int b=sc.nextInt()-1;  
35.     int c=sc.nextInt();  
36.     int t=sc.nextInt();  
37.     cost[a][b]=cost[b][a]=c;  
38.     time[a][b]=time[b][a]=t;  
39.    }  
40.    for(int k=0; k<m; k++){  
41.     for(int i=0; i<m; i++){  
42.      for(int j=0; j<m; j++){  
43.       cost[i][j]=min(cost[i][j], cost[i][k]+cost[k][j]);  
44.       time[i][j]=min(time[i][j], time[i][k]+time[k][j]);  
45.      }  
46.     }  
47.    }  
48.    k=sc.nextInt();  
49.    for(int i=0; i<k; i++){  
50.     int p=sc.nextInt()-1;  
51.     int q=sc.nextInt()-1;  
52.     int r=sc.nextInt();  
53.     if(r==0){  
54.      println(cost[p][q]+"");  
55.     }else{  
56.      println(time[p][q]+"");  
57.     }  
58.    }  
59.   }  
60.  }  
61.   
62.  void debug(Object... os){  
63.   System.err.println(Arrays.deepToString(os));  
64.  }  
65.   
66.  void print(String s){  
67.   System.out.print(s);  
68.  }  
69.   
70.  void println(String s){  
71.   System.out.println(s);  
72.  }  
73.   
74.  public static void main(String[] args){  
75.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
76.   new Main().run();  
77.  }  
78. }  

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

やるだけ．

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 x=sc.nextInt();  
19.    int y=sc.nextInt();  
20.    if((x|y)==0){  
21.     break;  
22.    }  
23.    if(x<y){  
24.     int t=x;  
25.     x=y;  
26.     y=t;  
27.    }  
28.    for(int i=0;; i++){  
29.     if(y==0){  
30.      println(x+" "+i);  
31.      break;  
32.     }  
33.     x=x%y;  
34.     int t=x;  
35.     x=y;  
36.     y=t;  
37.    }  
38.   }  
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. }  

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

やるだけ．

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.    R[] rs=new R[n];  
23.    for(int j=0; j<n; j++){  
24.     rs[j]=new R();  
25.     rs[j].name=sc.next();  
26.     for(int i=0; i<n-1; i++){  
27.      switch(sc.nextInt()){  
28.      case 0:  
29.       rs[j].win--;  
30.       break;  
31.      case 1:  
32.       rs[j].lose++;  
33.       break;  
34.      }  
35.     }  
36.    }  
37.    Arrays.sort(rs);  
38.    for(R r : rs){  
39.     println(r.name);  
40.    }  
41.   }  
42.  }  
43.   
44.  class R implements Comparable<R>{  
45.   int win, lose;  
46.   String name;  
47.   
48.   @Override  
49.   public int compareTo(R r){  
50.    if(win!=r.win){  
51.     return win-r.win;  
52.    }else{  
53.     return lose-r.lose;  
54.    }  
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. }  

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?

やるだけ．

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=5;  
19.    int max=0;  
20.    char c='A';  
21.    for(int i=0; i<n; i++){  
22.     int a=sc.nextInt()+sc.nextInt();  
23.     if(a==0){  
24.      return;  
25.     }  
26.     if(a>max){  
27.      c=(char)('A'+i);  
28.      max=a;  
29.     }  
30.    }  
31.    println(c+" "+max);  
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. }  

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をやるだけ．

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

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