2021-11-19
基本数学2
少数と幾何学について議論しましょう.

5階4948ベルトラン姫

https://www.acmicpc.net/problem/4948

質問する

任意の自然数nは、nより大きく、2 n以下の数が少なくとも1つ存在することを示す.
この命題はジョセフ・バートランが1845年に推測したもので、パフヌティ・チェビショフは1850年に証明した.
たとえば、10以上、20以下の小数が4つあります.(11、13、17、19)また、14より大きく28以下の小数が3個ある.(17,19, 23)
自然数nが与えられた場合、nより大きい、2 n以下の数を求めるプログラムを作成します.

入力

入力は、複数のテスト・インスタンスから構成されます.各ボックスは、nを含む行からなる.
入力の最後は0です.

しゅつりょく

各試験例について、出力はnより大きく、2 n以下の少数の数である.

Java 11

import java.util.*;
public class Main {
   public static boolean[] prime = new boolean[246913];
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      get_prime();
      
      while(true) {
         int n;
         n = sc.nextInt();
         
         if(n == 0) break;
         
         int count = 0;
         
         for(int i=n+1; i<=2*n; i++) {
            if(!prime[i])
               count++;
         }
         System.out.println(count);         
      }
   }

   private static void get_prime() {
      prime[0] = prime[1] = true;
      
      for(int i=2; i<=Math.sqrt(prime.length); i++) {
         if(prime[i])
            continue;
         for(int j=i*i; j<prime.length; j+=i) {
            prime[j] = true;
         }
      }
   }
}

2次2581小数

https://www.acmicpc.net/problem/2581

質問する

自然数MとNが与えられた場合、M以上N以下の自然数の中からすべての小数を選択し、これらの小数の和の最大値を探すプログラムを書き出します.
例えばM=60、N=100、60以上100以下の自然数のうち、61、67、71、73、79、83、89、97の計8個があり、これらの数の和は620であり、最大値は61である.

入力

入力された第1行M、第2行N.
MとNは10000以下の自然数であり、MはN以下である.

しゅつりょく

M以上N以下の自然数のうちの少数を探し出し,第1行でその和を出力し,第2行でその中の最大値を出力する.
ただし、M以上N以下の自然数に少数がなければ、1行目に−1が出力される.

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int M;
      M = sc.nextInt();
      int N;
      N = sc.nextInt();
      int sum = 0;
      int min = N;
      int tmp = 0;
      
      for(int i=M; i<=N; i++) {
         tmp = 0;
         for(int j=1; j<=i; j++) {
            if(i%j == 0)
               tmp++;
               }
            if(tmp == 2) {
               sum += i;
               if(min>i)
                  min = i;
               }
            }
      
            if(sum == 0) {
               System.out.println(-1);
            } else {
               System.out.println(sum);
               System.out.println(min);
            }
   }
}

6階9020金バッハ推測

https://www.acmicpc.net/problem/9020

質問する

1より大きい自然数のうち、1と自身を除いて約数のない自然数を少数と呼ぶ.例えば、5は、1と5を除いて約数がないため、少数である.ただし、6=6=2× 3なので少数ではありません.
金バッハの推測は有名な整数論の未解問題であり,2より大きいすべての偶数は2つの素数の和として表すことができる.この数を金バッハ数と呼ぶ.また,偶数を2素数の和として表す式を数の黄金バッハパーティションと呼ぶ.例えば、4=2+2、6=3+3、8=3+5、10=5+5、12=5+7、14=3+11、14=7+7である.10000以下のすべての偶数nについて、黄金バッハパーティションが存在する.
2より大きい偶数nが与えられた場合、nの黄金バッハパーティションを出力するプログラムを作成します.可能なn個のゴールドバッハパーティションが複数ある場合、出力の2つの少数の差が最小である.

入力

第1行は、試験例の個数Tを与える.各試験例は1行で構成され、偶数nが与えられる.

しゅつりょく

各テストケースについて、所与のn個のゴールドバッハパーティションを出力する.出力された小数点は先に出力され、スペースで区切られます.

Java 11

import java.util.*;
public class Main {
   public static boolean[] prime = new boolean[10001];
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      get_prime();
      
      int T;
      T = sc.nextInt();
      
      while(T-- > 0) {
         int n;
         n = sc.nextInt();
         int first_partition = n/2;
         int second_partition = n/2;
         
         while(true) {
            if(!prime[first_partition] && !prime[second_partition]) {
               System.out.println(first_partition + " " + second_partition);
               break;
            }
            first_partition--;
            second_partition++;
         }
      }
   }
      
   private static void get_prime() {
      prime[0] = prime[1] = true;
      
      for(int i=2; i<=Math.sqrt(prime.length); i++) {
         if(prime[i])
            continue;
         for(int j=i*i; j<prime.length; j+=i) {
            prime[j] = true;
         }
      }
   }
}

7階1085矩形から脱出

https://www.acmicpc.net/problem/1085

質問する

1つの数は現在(x,y).矩形は各辺の座標軸に平行で、左下の頂点は(0,0)、右上の頂点は(w,h)である.矩形の境界までの距離の最大値を求めるプログラムを作成してください.

入力

最初の行はx,y,w,hを与える.

しゅつりょく

最初の行に問題の答えを出力します.

Java 11

import java.util.*;
public class Main {
   public static boolean[] prime = new boolean[10001];
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int x;
      x = sc.nextInt();
      int y;
      y = sc.nextInt();
      int w;
      w = sc.nextInt();
      int h;
      h = sc.nextInt();
      
      int x_min = Math.min(x, w-x);
      int y_min = Math.min(y, h-y);
      
      System.out.println(Math.min(x_min, y_min));
   }
}

ステップ3009第4点

https://www.acmicpc.net/problem/3009

質問する

3つの点が与えられた場合、4番目の点を検索するプログラムを作成して、軸に平行な長方形を作成します.

入力

3点の座標は1行1つです.座標は1以上、1000以下の整数です.

しゅつりょく

長方形の4点目の座標を出力します.

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int[] coord_1 = { sc.nextInt(), sc. nextInt() } ;
      int[] coord_2 = { sc.nextInt(), sc. nextInt() } ;
      int[] coord_3 = { sc.nextInt(), sc. nextInt() } ;
      
      int x;
      int y;
      
      if(coord_1[0] == coord_2[0]) {
         x = coord_3[0];
      } else if( coord_1[0] == coord_3[0]) {
         x = coord_2[0];
      } else {
         x = coord_1[0];
      }
      
      if (coord_1[1] == coord_2[1]) {
         y = coord_3[1];
      } else if (coord_1[1] == coord_3[1]) {
         y = coord_2[1];
      } else {
         y = coord_1[1];
      }
      System.out.println(x + " " + y);
   }
}

9次4153直角三角形

https://www.acmicpc.net/problem/4153

質問する

過去、エジプト人は各辺が3、4、5の三角形が直角三角形であることを発見した.三角形が直角かどうかは、指定した3辺の長さで区別してください.

入力

入力には複数の試験例が与えられ、最後の行には0 0 0が入力される.各試験例には30000未満の整数が与えられ、各入力はエッジの長さを表す.

しゅつりょく

各入力に対して、直角三角形が正しい場合は「right」を出力し、そうでない場合は「error」を出力します.

Java 11

import java.util.*;
public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      while(true) {
         int x;
         x = sc.nextInt();
         int y;
         y = sc.nextInt();
         int z;
         z = sc.nextInt();
         
         if(x==0 && y==0 && z==0)
            break;
      
         if((x * x + y * y) == z * z) {
            System.out.println("right");
         } else if(x * x == (y * y + z * z)) {
            System.out.println("right");
         } else if(y * y == (z * z + x * x)) {
            System.out.println("right");
         } else {
            System.out.println("wrong");
         }
      }
   }
}