Codeforces Beta Round #69 (Div. 2 Only)

Codeforces Beta Round #69 (Div. 2 Only)

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

A. Panoramixs Prediction

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

view plainprint?

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

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

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

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

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

 int m, n;

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

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

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

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

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

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

B. Depression

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

view plainprint?

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

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

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

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

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

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

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

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

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

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

C. Heroes

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

view plainprint?

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

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

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

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

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

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

 void run(){
  int m=7;

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

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

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

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

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

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

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

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

D. Falling Anvils

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

view plainprint?

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

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

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

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

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

 int t;
 double a, b;

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

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

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

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

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

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