第8回ブルーブリッジカップ省試合(Java B)
101068 ワード
public class A {
public static void main(String[] args) {
double sum = 180.90 * 0.88 + 10.25 * 0.65 + 56.14 * 0.9 + 104.65 * 0.9 + 100.30 * 0.88 + 297.15 * 0.5
+ 26.75 * 0.65 + 130.62 * 0.5 + 240.28 * 0.58 + 270.62 * 0.8 + 115.87 * 0.88 + 247.34 * 0.95
+ 73.21 * 0.9 + 101.00 * 0.5 + 79.54 * 0.5 + 278.44 * 0.7 + 199.26 * 0.5 + 12.97 * 0.9 + 166.30 * 0.78
+ 125.50 * 0.58 + 84.98 * 0.9 + 113.35 * 0.68 + 166.57 * 0.5 + 42.56 * 0.9 + 81.90 * 0.95 + 131.78 * 0.8
+ 255.89 * 0.78 + 109.17 * 0.9 + 146.69 * 0.68 + 139.33 * 0.65 + 141.16 * 0.78 + 154.74 * 0.8
+ 59.42 * 0.8 + 85.44 * 0.68 + 293.70 * 0.88 + 261.79 * 0.65 + 11.30 * 0.88 + 268.27 * 0.58
+ 128.29 * 0.88 + 251.03 * 0.8 + 208.39 * 0.75 + 128.88 * 0.75 + 62.06 * 0.9 + 225.87 * 0.75
+ 12.89 * 0.75 + 34.28 * 0.75 + 62.16 * 0.58 + 129.12 * 0.5 + 218.37 * 0.5 + 289.69 * 0.8;
System.out.println(sum);
System.out.println(5200);
}
}
2.カードの三角形A、2,3,4,5,6,7,8,9の9枚のカードが正三角形に並んでいます(Aは1で計算します).各辺の和が等しいことを要求します.下図は1つの並べ方です.このような並べ方が多いかもしれません.回転、ミラーリングを考慮して同じものを同じものとすると、全部で何種類の異なる並べ方がありますか.この数字を計算して提出してください.注意:整数を提出しなければなりません.余分な内容を提出しないでください.
A
9 6
4 8
3 7 5 2
考え方:まずこの9枚の札を1次元の配列として全配列して、それから回転、鏡像の後で同じ計算の1種のため、それでは私達は知ることができて、回転は3回回転することができて、だから3種類の情況は1種を計算して、3で割る必要があって、鏡像は2種類の情況があって、だから2種類の情況は1種を計算して、2で割る必要があります
public class B {
static long sum = 0;
// ， ， ， ， 3， ， 2
public static void fun(int a[], int n) {
if (n == 9) {
test(a);
return;//
} else
for (int i = n; i < 9; i++) {
int temp = a[i];
a[i] = a[n];
a[n] = temp;
fun(a, n + 1);
int tamp = a[i];
a[i] = a[n];
a[n] = tamp;
}
}
public static void test(int[] a) {
int l1 = a[0] + a[1] + a[2] + a[3];
int l2 = a[3] + a[4] + a[5] + a[6];
int l3 = a[6] + a[7] + a[8] + a[0];
if (l1 == l2 && l1 == l3) {
sum++;
}
}
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
fun(a, 0);
System.out.println(sum / 3 / 2);//144
}
}
3.圧力計算X星のハイテク実験室には、ある貴重な金属原料がきちんと積み上げられている.各金属原料の外形、寸法は完全に一致しているが、重量は異なる.金属材料は厳格に金字塔の形に積み上げられている.7 5 8 7 8 8 9 2 7 2 8 1 4 9 1 8 1 8 8 4 1 7 9 6 1 4 5 4 5 6 5 5 6 9 5 6 5 5 4 7 9 3 5 5 1 7 5 7 9 7 4 7 3 3 1 4 6 4 5 5 8 8 3 2 4 3 1 1 3 3 1 6 6 5 5 4 4 2 9 9 9 2 1 9 1 9 2 9 5 7 9 4 3 3 7 7 9 3 6 1 3 8 8 3 7 3 6 8 1 5 3 9 5 8 3 8 1 8 3 3 8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9 8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4 2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9 7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6 9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3 5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9 6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4 2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4 7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6 1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3 2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8 8 7 7 7 7 7 7 7 7 5 2 7 9 9 9 1 9 6 6 5 3 9 3 5 7 3 5 5 4 8 7 6 8 7 6 8 5 5 4 7 7 4 7 7 4 6 9 2 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 1 1 1 2 6 1 4 3 4 1 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X(計量単位が大きい).一番下の層のXは30台の極めて高い精度の電子秤を表している.各原料の重量が非常に正確に平均的に下の2つの金属塊に落ちていると仮定し、最後に、すべての金属塊の重量が最下層の電子秤に厳格に正確に平分されている.電子秤の計量単位が小さいので、表示されている数字が大きい.従業員は発見したこのうち、読数が最も小さい電子秤の示数は:2086458231です.読数が最も大きい電子秤の示数はいくらですか.注意:提出する必要があるのは整数で、余分な内容を記入しないでください.
考え方:ピラミッドをこのような三角形に変えることができます.
public class C {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
double[][] a = new double[30][30];
for (int i = 0; i < 29; ++i) {
for (int j = 0; j <= i; ++j) {
a[i][j] = cin.nextInt();
}
}
for (int i = 1; i < 30; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0) {
a[i][j] += (double) a[i - 1][j] / 2;
} else {
a[i][j] += (double) a[i - 1][j] / 2 + (double) a[i - 1][j - 1] / 2;
}
}
}
Arrays.sort(a[29]);//
// 5 ， 20 ， 4
// 2086458231， a[29][0] ，
//
System.out.println(2086458231 / a[29][0] * a[29][29]);//72665192664
}
}
5.採数位タイトル:数位を取って1つの整数のk位の数字を求めるには多くの方法がある.以下の方法が1つです.
public class E {
static int len(int x) {
if (x < 10) {
return 1;
}
return len(x / 10) + 1;
}
// x k
static int f(int x, int k) {
if (len(x) - k == 0) {
return x % 10;
}
return f(x / 10, k); //
// return x k 10， k ， 10 ， k ，
}
public static void main(String[] args) {
int x = 23513;
System.out.println(f(x, 3));
}
}
6.最大共通サブストリング最大共通サブストリング長問題は、2つのストリングのすべてのサブストリングの中で一致できる最大長を求めることである.例えば、「abcdkkk」と「baabcdabc」では、最も長い共通サブストリングが「abcd」であるため、最大共通サブストリング長は4である.次のプログラムはマトリクス法を用いて解くが,これは列の規模が大きくない場合に有効な解法である.この解法の考え方を分析し,スクライブ部分で欠落したコードを補完してください.
public class F {
static int f(String s1, String s2) {
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[][] a = new int[c1.length + 1][c2.length + 1];
int max = 0;
for (int i = 1; i < a.length; ++i) {//
for (int j = 1; j < a[i].length; ++j) {//
if (c1[i - 1] == c2[j - 1]) {
a[i][j] = a[i - 1][j - 1] + 1;//
if (a[i][j] > max) {
max = a[i][j];
}
}
}
}
return max;
}
public static void main(String[] args) {
int n = f("abcdkkk", "baabcdadabc");
System.out.println(n);
}
}
7.日付の問題明ちゃんは歴史文献を整理しています.これらの歴史文献には多くの日付が現れている.明ちゃんはこれらの日付が1960年1月1日から2059年12月31日まであることを知っています.明ちゃんが困っているのは、これらの日付のフォーマットが非常に統一されていないことです.年/月/日を採用している人もいれば、月/日/年を採用している人もいれば、日/月/年を採用している人もいます.さらに厄介なことに,年も上位2桁を省略しているため,文献上の1つの日付に対応する可能性のある日付が多く存在する.例えば02/03/04は、2002年03月04日、2004年02月03日、または2004年03月02日である可能性があります.文献上の日付を与えて、明ちゃんがどのような可能性のある日付が対応しているかを判断するのに役立ちますか?「AA/BB/CC」形式の日付を入力します.(0<=A,B,C<=9)出力は、「yyyy-MM-dd」形式の複数の異なる日付を出力します.複数の日付を朝から晩まで並べます.サンプル入力02/03/04サンプル出力2002-03-04 2004 2004-02-03 2004-03 02-02リソース約定:ピークメモリ消費(仮想マシン含む)<256 M CPU消費<1000 ms要求通りに厳格に出力し、「入力...」のような余分な内容を蛇足で印刷しないでください.
考え方:この問題は、閏年、二月の日数の違いを判断し、並べ替えを出力すればTreeSetで解決できる
import java.util.Scanner;
import java.util.TreeSet;
public class G {
//
static int a, b, c;
static int date[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
public static boolean isRun(int y) {
return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
}
public static boolean nianyueri(int x, int y, int z) {
if (x >= 0 && x <= 59) {
a += 2000;
} else {
a += 1900;
}
if (isRun(x)) {
date[2] = 29;
}
if (y < 1 || y > 12) {// 1 12
return false;
}
if (z < 1 || z > 31) {// 1 31
return false;
}
if (z > date[y]) {// ， 31， 28
return false;
}
return true;
}
public static boolean yuerinian(int x, int y, int z) {
if (z >= 0 && z <= 59) {
c += 2000;
} else {
c += 1900;
}
if (isRun(z)) {
date[2] = 29;
}
if (x < 1 || x > 12) {
return false;
}
if (y < 1 || y > 31) {
return false;
}
if (y > date[x]) {
return false;
}
return true;
}
public static boolean riyuenian(int x, int y, int z) {
if (z >= 0 && z <= 59) {
c += 2000;
} else {
c += 1900;
}
if (isRun(z)) {
date[2] = 29;
}
if (y < 1 || y > 12) {
return false;
}
if (x < 1 || x > 31) {
return false;
}
if (x > date[y]) {
return false;
}
return true;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
TreeSet<String> set = new TreeSet<String>();
String s = cin.nextLine();
char[] ch = s.toCharArray();
a = (ch[0] - '0') * 10 + (ch[1] - '0');
b = (ch[3] - '0') * 10 + (ch[4] - '0');
c = (ch[6] - '0') * 10 + (ch[7] - '0');
date[2] = 28;
if (nianyueri(a, b, c)) {
if (b < 10) {
if (c < 10) {
set.add(a + "-0" + b + "-0" + c);
} else {
set.add(a + "-0" + b + "-" + c);
}
} else if (c < 10) {
set.add(a + "-" + b + "-0" + c);
} else {
set.add(a + "-" + b + "-" + c);
}
}
a = (ch[0] - '0') * 10 + (ch[1] - '0');
b = (ch[3] - '0') * 10 + (ch[4] - '0');
c = (ch[6] - '0') * 10 + (ch[7] - '0');
date[2] = 28;
if (yuerinian(a, b, c)) {
if (a < 10) {
if (b < 10) {
set.add(c + "-0" + a + "-0" + b);
} else {
set.add(c + "-0" + a + "-" + b);
}
} else if (b < 10) {
set.add(c + "-" + a + "-0" + b);
} else {
set.add(c + "-" + a + "-" + b);
}
}
a = (ch[0] - '0') * 10 + (ch[1] - '0');
b = (ch[3] - '0') * 10 + (ch[4] - '0');
c = (ch[6] - '0') * 10 + (ch[7] - '0');
date[2] = 28;
if (riyuenian(a, b, c)) {
if (b < 10) {
if (a < 10) {
set.add(c + "-0" + b + "-0" + a);
} else {
set.add(c + "-0" + b + "-" + a);
}
} else if (a < 10) {
set.add(c + "-" + b + "-0" + a);
} else {
set.add(a + "-" + b + "-" + c);
}
}
String[] ans = set.toArray(new String[set.size()]);
// Object[] ans = set.toArray();
for (String x : ans) {
System.out.println(x);
}
}
}
9.チョコレートの子供の日にK人の子供が明ちゃんの家に来ました.明ちゃんは大切なチョコレートを出して子供たちをもてなした.明ちゃんは全部でN枚のチョコレートを持っていて、その中のi枚目はHix Wiの四角い格子からなる長方形です.公平のために、明ちゃんはこのN枚のチョコレートの中からK枚のチョコレートを切って子供たちに分ける必要があります.カットしたチョコレートは満足する必要があります:1.形状は正方形、辺長は整数2である.同じ大きさ、例えば6 x 5のチョコレートは、2 x 2のチョコレート6枚または3 x 3のチョコレート2枚を切ることができる.もちろん子供たちが望んでいるチョコレートはできるだけ大きくして、Hiさんの最大の辺の長さを計算してもらえますか?入力第1行は、2つの整数NおよびKを含む.(1<=N,K<=100000)以下のN行は、行ごとに2つの整数HiおよびWiを含む.(1<=Hi,Wi<=100000)入力は、子供1人につき少なくとも1 x 1のチョコレートが得られることを保証する.出力出力出力カットされた正方形チョコレートの最大可能なエッジ長.サンプル入力:2 10 6 5 5 6サンプル出力:2リソース約定:ピークメモリ消費(仮想マシン含む)<256 M CPU消費<1000 ms要求通りに出力してください.「入力してください」のような余分な内容を蛇足せずに印刷してください.プログラムを送信するときは、所望の言語タイプとコンパイラタイプを選択することに注意してください.
考え方:最も直接的なのは暴力で、辺長は100000から小さい探しに行って、初めて題意を満たす時、探し出す辺長も最大です.システムが提出したのは75点で、データの規模が大きい場合は明らかにタイムアウトします.以下は暴力解法です.
public class I {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int k = cin.nextInt();
int[] h = new int[n];
int[] w = new int[n];
for (int i = 0; i < n; ++i) {
h[i] = cin.nextInt();
w[i] = cin.nextInt();
}
for (int len = 100000; len >= 1; --len) {
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += (h[i] / len) * (w[i] / len);
}
if (cnt >= k) {
System.out.println(len);
return;
}
}
}
}
そして、midが要求に合っているかどうかを判断するたびに、midが要求に合っているかどうかを判断し、このmidを保存して、右の区間に探します.すなわちstart=mid+1です.できるだけチョコレートの大きいものを探しますから、midが満足していない場合は、左の区間にend=mid-1を探します.提出はなぜ75点しかないのか分からないが、指摘を求めて、以下は二分コードだ.
import java.util.Scanner;
public class I {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int k = cin.nextInt();
int[] h = new int[n];
int[] w = new int[n];
for (int i = 0; i < n; ++i) {
h[i] = cin.nextInt();
w[i] = cin.nextInt();
}
int start = 1;
int end = 100000;
int ans = 0;
while (start <= end) {
int mid = (start + end) / 2;
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += (h[i] / mid) * (w[i] / mid);
}
if (cnt >= k) {
start = mid + 1;
ans = mid;
} else {
end = mid - 1;
}
}
System.out.println(ans);
}
}
10.K倍区間は長さNの数列、A 1,A 2,...ANを与え、そのうちの1段の連続するサブシーケンスAi,Ai+1,...Aj(i<=j)の和がKの倍数であれば、この区間[i,j]をK倍区間と呼ぶ.数列に全部で何個のK倍区間があるか求められますか?入力第1行は、2つの整数NおよびKを含む.(1<=N、K<=100000)以下のN行は、行ごとに1つの整数Aiを含む.(1<=Ai<=100000)K倍区間の数を表す整数を出力する.たとえば、入力:5 2 1 2 3 4 5プログラム出力:6リソース約定:ピークメモリ消費(仮想マシンを含む)<256 M CPU消費<2000 ms要求通りに出力してください.「入力してください」のような余分な内容を蛇足せずに印刷してください.プログラムを送信するときは、所望の言語タイプとコンパイラタイプを選択することに注意してください.
考え方:この暴力法は言うまでもなく、区間問題で考えやすいのは接頭辞和だが、この問題は接頭辞和の上で数論の知識を利用して最適化しなければならないようだ.菜鶏は接頭辞と水しか使えなくなった.
public class J {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int k = cin.nextInt();
int[] a = new int[n + 5];
int[] pre = new int[n + 5];
pre[0] = 0;
for (int i = 1; i <= n; ++i) {
a[i] = cin.nextInt();
pre[i] = (pre[i - 1] + a[i]);
}
long sum = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
if ((pre[j] - pre[i - 1]) % k == 0) {
sum++;
}
}
}
System.out.println(sum);
}
}
次は大物のコードです...
import java.util.Scanner;
public class J {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int a[] = new int[n + 1];
for (int i = 0; i < n; i++)
a[i] = sc.nextInt();
a[0] = a[0] % k;
for (int i = 1; i < n; i++)
a[i] = ((a[i] % k) + a[i - 1]) % k;
long sum = 0;
int b[] = new int[n + 1];
for (int i = 0; i < n; i++)
sum += b[a[i]]++;
System.out.println(sum + b[0]);
}
}