Codeforces Beta Round #30

Codeforces Beta Round #30 9/25(0:00~2:00)

1週間振り．

■A. Accounting
□問題
3つの整数A,B,n(|A|,|B|≦1000, 1≦n≦10)が与えられる．
AXⁿ=Bとなる整数Xが存在するか判定し，存在する場合はその内の1つの解を求めよ．

□解法
場合分けをきっちりやればOK．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class A{  
9.     Scanner sc=new Scanner(System.in);  
10.   
11.     void run(){  
12.         int a=sc.nextInt();  
13.         int b=sc.nextInt();  
14.         int n=sc.nextInt();  
15.         if(a*b>0){  
16.             a=Math.abs(a);  
17.             b=Math.abs(b);  
18.             for(int x=1;; x++){  
19.                 int c=a*(int)Math.pow(x, n);  
20.                 if(c==b){  
21.                     println(""+x);  
22.                     break;  
23.                 }else if(c>b){  
24.                     println("No solution");  
25.                     break;  
26.                 }  
27.             }  
28.         }else if(a*b<0){  
29.             if(n%2==0){  
30.                 println("No solution");  
31.                 return;  
32.             }  
33.             a=Math.abs(a);  
34.             b=Math.abs(b);  
35.             for(int x=1;; x++){  
36.                 int c=a*(int)Math.pow(x, n);  
37.                 if(c==b){  
38.                     println("-"+x);  
39.                     break;  
40.                 }else if(c>b){  
41.                     println("No solution");  
42.                     break;  
43.                 }  
44.             }  
45.         }else{  
46.             if(a==0&&b==0){  
47.                 println("1");  
48.             }else if(a==0){  
49.                 println("No solution");  
50.             }else{  
51.                 println("0");  
52.             }  
53.         }  
54.     }  
55.   
56.     void println(String s){  
57.         System.out.println(s);  
58.     }  
59.   
60.     void print(String s){  
61.         System.out.print(s);  
62.     }  
63.   
64.     public static void main(String[] args){  
65.         new A().run();  
66.     }  
67. }  

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

    void run(){
        int a=sc.nextInt();
        int b=sc.nextInt();
        int n=sc.nextInt();
        if(a*b>0){
            a=Math.abs(a);
            b=Math.abs(b);
            for(int x=1;; x++){
                int c=a*(int)Math.pow(x, n);
                if(c==b){
                    println(""+x);
                    break;
                }else if(c>b){
                    println("No solution");
                    break;
                }
            }
        }else if(a*b<0){
            if(n%2==0){
                println("No solution");
                return;
            }
            a=Math.abs(a);
            b=Math.abs(b);
            for(int x=1;; x++){
                int c=a*(int)Math.pow(x, n);
                if(c==b){
                    println("-"+x);
                    break;
                }else if(c>b){
                    println("No solution");
                    break;
                }
            }
        }else{
            if(a==0&&b==0){
                println("1");
            }else if(a==0){
                println("No solution");
            }else{
                println("0");
            }
        }
    }

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

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

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

■B. Codeforces World Finals
□問題
Bobの生年月日(BD.BM.BY)とコンテストの開催年月日(DD.MM.YY)が与えられる．コンテストの開催年月日にはBobが18才以上となっているようにBobの生年月日を並び替える(BD，BM，BYをそれぞれ並び替える)ことは出来るか．

□解法
6通り全ての並び替えに対し，それが生年月日であるか+18才以上になるかという条件チェックをちゃんとやったつもりでしたが，堕ちました．

□コード
自主規制

■C. Shooting Gallery
□問題
n個のターゲットがある．ターゲットiはそれぞれ座標(x_i, y_i)，出現時刻t_i，命中率p_iを持つ．プレイヤーは，任意の位置からスタートできるが，座標c_iからc_jへ移動するのには，|c_j-c_i|だけの時間がかかる．最適な行動をとった時，ターゲットの破壊個数の期待値は最大いくらになるか．

□解法
まず，t_iでソートします．ターゲットiを破壊し最適な行動をとった時の最大期待値E_iは，
E_i=p_i+MAX_{j(tj-ti≧|cj-ci|)}E_j
となります．
ですので，t_iが大きいものからE_iを求めていき，全て求め終わった後，最も大きいE_iが答えとなります．

□コード

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5. import static java.lang.Math.*;  
6. import static java.util.Arrays.*;  
7.   
8. public class C{  
9.     Scanner sc=new Scanner(System.in);  
10.   
11.     int n;  
12.     R[] rs;  
13.   
14.     double EPS=1e-6;  
15.   
16.     void run(){  
17.         n=sc.nextInt();  
18.         rs=new R[n];  
19.         for(int i=0; i<n; i++){  
20.             R r=new R();  
21.             r.x=sc.nextInt();  
22.             r.y=sc.nextInt();  
23.             r.t=sc.nextInt();  
24.             r.p=sc.nextDouble();  
25.             rs[i]=r;  
26.         }  
27.         Arrays.sort(rs, new Comparator<R>(){  
28.             @Override  
29.             public int compare(R r1, R r2){  
30.                 return r2.t-r1.t;  
31.             }  
32.         });  
33.         for(int j=0; j<n; j++){  
34.             R r=rs[j];  
35.             r.E+=r.p;  
36.             for(int i=j+1; i<n; i++){  
37.                 R s=rs[i];  
38.                 double d=Math.sqrt((r.x-s.x)*(r.x-s.x)+(r.y-s.y)*(r.y-s.y));  
39.                 if(d<r.t-s.t+EPS){  
40.                     s.E=Math.max(s.E, r.E);  
41.                 }  
42.             }  
43.         }  
44.         double ans=0;  
45.         for(R r : rs){  
46.             ans=Math.max(ans, r.E);  
47.         }  
48.         println(""+ans);  
49.     }  
50.   
51.     class R{  
52.         int x, y, t;  
53.         double p;  
54.         double E;  
55.     }  
56.   
57.     void println(String s){  
58.         System.out.println(s);  
59.     }  
60.   
61.     void print(String s){  
62.         System.out.print(s);  
63.     }  
64.   
65.     public static void main(String[] args){  
66.         new C().run();  
67.     }  
68. }  

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

    double EPS=1e-6;

    void run(){
        n=sc.nextInt();
        rs=new R[n];
        for(int i=0; i<n; i++){
            R r=new R();
            r.x=sc.nextInt();
            r.y=sc.nextInt();
            r.t=sc.nextInt();
            r.p=sc.nextDouble();
            rs[i]=r;
        }
        Arrays.sort(rs, new Comparator<R>(){
            @Override
            public int compare(R r1, R r2){
                return r2.t-r1.t;
            }
        });
        for(int j=0; j<n; j++){
            R r=rs[j];
            r.E+=r.p;
            for(int i=j+1; i<n; i++){
                R s=rs[i];
                double d=Math.sqrt((r.x-s.x)*(r.x-s.x)+(r.y-s.y)*(r.y-s.y));
                if(d<r.t-s.t+EPS){
                    s.E=Math.max(s.E, r.E);
                }
            }
        }
        double ans=0;
        for(R r : rs){
            ans=Math.max(ans, r.E);
        }
        println(""+ans);
    }

    class R{
        int x, y, t;
        double p;
        double E;
    }

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

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

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

■Result
○×○××
1636p
151位

■Rating
1759 -> 1709

さらにRatingダウン．Bを落としたのが痛かった…．