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
紫コーダーになりました．