catalogue
E. Yang Hui triangle (fill in the blank)
A. Alien calendar
Traces of civilization were found in the depths of a galaxy.
Their counting is also in decimal.
Their civilization also has a calendar. The calendar has only days, without the concept of year and month.
Interestingly, they also use a concept similar to "week",
It's just that their week includes nine days,
For convenience, they are recorded here as: A, B, C H,I
From some materials,
Their 23rd is Sunday E
Their 190th is Sunday A
Their 343251 is Sunday I
It's exciting that they also foresee the "end of the world",
Of course, it's a big number
651764141421415346185
Please calculate the day of the week of this civilization on this distant day?
What you need to submit is a capital letter indicating the day of the week of the civilization,
Don't fill in anything superfluous.
Solution:
package action;
import java.math.BigInteger;
public class demo {
public static void main(String[] args) {
BigInteger x = new BigInteger("651764141421415346185");
BigInteger y = x.mod(new BigInteger("9"));
int z = y.intValue();
System.out.println((char)('A'+z-1));
}
}
B. Interest group
In order to enrich the spare time cultural life of the students, the student union of a university established three interest groups
(hereinafter referred to as group A, group B and group C).
The list of students in each group is in [A.txt], [B.txt] and [C.txt].
Each student's student ID is stored in the file.
Due to the need of work, we now want to know:
How many students participated in both group A and group B, but did not participate in group C?
Please count the number and submit the answer through the browser.
Note: the answer is an integer. Do not submit any redundant content.
Solution:
package action;
public class demo {
public static void main(String[] args) {
int[] a = { 12894792, 92774113, 59529208, 22962224, 2991600, 83340521, 87365045, 40818286, 16400628, 39475245,
55933381, 76940287, 61366748, 95631228, 17102313, 50682833, 61562613, 87002524, 83062019, 51743442,
61977890, 32010762, 69680621, 87179571, 81761697, 32364296, 7833271, 36198035, 26588918, 84046668,
43059468, 73191775, 56794101, 454780, 11141030, 10008994, 35072237, 44945158, 53959980, 75758119,
18560273, 35801494, 42102550, 22496415, 3981786, 34593672, 13074905, 07733442, 42374678, 23452507,
98586743, 30771281, 17703080, 52123562, 5898131, 56698981, 90758589, 18238802, 18217979, 4511837,
75682969, 31135682, 55379006, 42224598, 98263070, 40228312, 28924663, 11580163, 25686441, 45944028,
96731602, 53675990, 3854194, 14858183, 16866794, 40677007, 73141512, 32317341, 56641725, 43123040,
15201174, 62389950, 72887083, 76860787, 61046319, 6923746, 17874548, 46028629, 10577743, 48747364,
5328780, 59855415, 60965266, 20592606, 14471207, 70896866, 46938647, 33575820, 53426294, 56093931,
51326542, 94050481, 80114017, 33010503, 72971538, 22407422, 17305672, 78974338, 93209260, 83461794,
41247821, 26118061, 10657376, 42198057, 15338224, 50284714, 32232841, 26716521, 76048344, 23676625,
62897700, 69296551, 59653393, 38704390, 48481614, 69782897, 26850668, 37471053, 88720989, 51010849,
94951571, 60024611, 29808329, 70377786, 13899299, 9683688, 58218284, 46792829, 97221709, 45286643,
48158629, 57367208, 26903401, 76900414, 87927040, 9926730, 1508757, 15101101, 62491840, 43802529 };
int[] b = { 44894050, 34662733, 44141729, 92774113, 99208727, 91919833, 23727681, 10003409, 55933381, 54443275,
13584702, 96523685, 50682833, 61562613, 62380975, 20311684, 93200452, 23101945, 42192880, 28992561,
18460278, 19186537, 58465301, 01111066, 62680429, 23721241, 20277631, 91708977, 57514737, 3981786,
81541612, 07346443, 93154608, 19709455, 37446968, 17703080, 72378958, 66200696, 30610382, 89586343,
33152171, 67040930, 35696683, 63242065, 99948221, 96233367, 52593493, 98263070, 1418023, 74816705,
89375940, 58405334, 96731602, 84089545, 16866794, 94737626, 01673442, 70548494, 13638168, 8163691,
11106566, 64375392, 40267902, 897705, 56447313, 54532235, 94738425, 66642634, 83219544, 40546096,
66924991, 20592606, 96037590, 73434467, 70896866, 91025618, 57892091, 8487641, 32500082, 84412833,
23311447, 38380409, 79957822, 72971538, 69645784, 91863314, 73099909, 93209260, 83461794, 81378487,
30423273, 22233715, 32232841, 26716521, 03511221, 29196547, 58263562, 56233305, 52547525, 55812835,
87253244, 52484232, 80837360, 94098464, 52028151, 53267501, 66381929, 84381316, 59788467, 9683688,
67082008, 71605255, 80654064, 21434307, 45286643, 76556656, 82465821, 57367208, 79218980, 48460468,
59170479, 46046391, 43043164, 96544490, 83340521, 70837892, 18926791, 40818286, 28936302, 11489524,
51031183, 73860337, 13241219, 9025448, 10718828, 76360986, 26031606, 76558053, 97726139, 46473415,
48406387, 23625539, 86756012, 35164187, 49161302, 78082834, 35072237, 8602486, 29815841, 56562216,
77684187, 81751704, 20160464, 50407962, 27786415, 19893526, 934129, 37759498, 52636463, 25666982,
43262852, 38393436, 2581136, 29323250, 56950657, 5898131, 95286262, 75574581, 54057961, 6703896,
90758589, 57782642, 34492535, 41919697, 6395464, 10993500, 81212949, 34017532, 69569396, 99009936,
57129610, 67401593, 71044018, 62076698, 29533873, 71936325, 86874388, 26545032, 35695544, 30433724,
53127345, 72887083, 25390873, 63711546, 6923746, 27783723, 33199575, 35929698, 16491251, 18276792,
62744775, 92096155, 06336570, 56141974, 73007273, 31416832, 00171057, 64176982, 46938647, 58460388,
69972026, 73724304, 27435484, 51568616, 15531822, 47788699, 11818851, 41594694, 83561325, 43107163,
56965375, 10557343, 26118061, 74650126, 90076467, 10657376, 49901436, 03425162, 61164599, 15797769,
5427896, 14444084, 36795868, 18079449, 59653393, 72942548, 06763077, 33895610, 94892653, 12085268,
65174140, 79567366, 23020126, 74290047, 13498869, 21696323, 27724594, 54941003, 38229841, 7050068 };
int[] c = { 13404901, 39952424, 47847739, 94939581, 13809950, 70966043, 11161555, 17102313, 47079425, 50682833,
74154313, 61562613, 93200452, 37103342, 18479435, 32502597, 36198035, 54210010, 73191775, 48358178,
85544503, 5996766, 54651623, 52113220, 27465181, 23871783, 22496415, 54107041, 65899605, 56528700,
82671109, 61176034, 42374678, 51612628, 63329997, 56591652, 04552733, 12789324, 89586343, 51935014,
38611966, 43916409, 70996050, 98263070, 1418023, 65345049, 21734275, 76846198, 71506230, 833171,
67128139, 41367555, 64769510, 44010700, 16475199, 93164325, 9386162, 95324041, 80688223, 67629139,
79552617, 76219736, 50368644, 45096021, 54972488, 63779011, 28862942, 73145521, 74078605, 66924991,
12806850, 02171001, 70896866, 73434467, 8487641, 44415025, 32500082, 84412833, 83896188, 52243759,
49191410, 38744339, 48079796, 44937032, 06267501, 81866886, 38575984, 25978688, 78974338, 41247821,
12356966, 64842303, 79127158, 2366944, 68000570, 12426275, 96409230, 705972, 8266503, 83820884, 8831807,
43273308, 23216105, 29196547, 95160161, 05553537, 52182214, 32641346, 91553427, 24436506, 77433749,
1979664, 52028151, 88985343, 1761499, 76203088, 63237368, 23405334, 59788467, 9683688, 67755443,
29946533, 12053603, 437479, 15200030, 45286643, 93537527, 82465821, 57367208, 53899751, 15354933,
97760830, 68933762, 80220545, 1892750, 39868288, 21524323, 69716610, 65083815, 78048499, 3227391,
83340521, 87365045, 71720254, 51031183, 89168555, 8503028, 37086236, 25103057, 87002524, 22808816,
80928090, 90741678, 15993372, 99117082, 49938176, 21755083, 86903426, 87830263, 53959980, 75758119,
59781354, 58679691, 25666982, 56307643, 47180521, 62776522, 78136608, 44882734, 90758589, 8075999,
66303819, 23480347, 11580163, 87080118, 18329165, 92514163, 89404632, 92377859, 3912329, 17499963,
59699979, 79876366, 63894807, 37857001, 86003935, 90087123, 29433345, 80298948, 61531153, 61046319,
37839841, 19421134, 48747364, 35196916, 62484573, 59907079, 36845702, 21631642, 72739317, 26283700,
80114017, 76639390, 29154110, 35159758, 47788699, 11818851, 56520669, 36396767, 36031167, 83817428,
10657376, 90076467, 14676452, 11024560, 16327605, 76048344, 14444084, 95452011, 99612346, 65172562,
84813675, 88618282, 38704390, 27998014, 63859011, 33787505, 60024611, 16229880, 13899299, 35240335,
29173227, 45036451, 66177893, 82658333, 43100730, 44520187, 74290047, 85013538, 9926730, 27724594,
95148523, 20503000, 64390907, 26006953, 98116293, 97457666, 29017396, 04634371, 70791589 };
// Participate in a, participate in b, not participate in c
// That is, the array ab has a number without c
int [] temp = new int [a.length];
int num = 0;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
if (a[i] == b[j]) {
temp[num] = a[i];
System.out.println(temp[num]);
num++;
}
}
}
for (int i = 0; i < temp.length; i++) {
for (int j = 0; j < c.length; j++) {
if (temp[i] == c[j]) {
num--;
}
}
}
System.out.println(num);
}
}
C. Card triangle
A. A total of 9 Cards of 2, 3, 4, 5, 6, 7, 8 and 9 are arranged into an equilateral triangle (a is calculated as 1). The sum of each edge is required to be equal.
The following figure is a layout:
A
9 6
4 8
3 7 5 2
There may be many such arrangements.
If we consider the same arrangement after rotation and mirror image, how many different arrangements are there?
Please calculate and submit this figure.
Note: what needs to be submitted is an integer. Do not submit any redundant content.
Solution:
package action;
public class demo {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
dfs(arr, 0, arr.length);
System.out.println(count / 6);
}
static int count = 0;
public static void dfs(int[] arr, int k, int end) {
// End condition
if (k == end) {
int x = arr[0] + arr[1] + arr[2] + arr[3];
int y = arr[3] + arr[4] + arr[5] + arr[6];
int z = arr[6] + arr[7] + arr[8] + arr[0];
if (x == y && x == z) {
count++;
}
return;
}
for (int i = k; i < end; i++) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
dfs(arr, k + 1, end);
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
D. Bearing calculation
A batch of precious metal raw materials are neatly stacked in the high-tech laboratory of Planet X.
The shape and size of each metal raw material are exactly the same, but the weight is different.
Metal materials are strictly stacked into pyramids.
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
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 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
The number represents the weight of the metal block (larger unit of measurement).
The X on the bottom layer represents 30 extremely high-precision electronic scales.
Assuming that the weight of each raw material falls on the two metal blocks below very accurately,
Finally, the weight of all metal blocks is strictly and accurately distributed on the bottom electronic scale.
The unit of measurement of the electronic scale is very small, so the number displayed is very large.
The staff found that the indication of the electronic scale with the smallest reading was 2086458231
Please figure out: what is the indication of the electronic scale with the largest reading?
Note: what needs to be submitted is an integer. Do not fill in any redundant content.
Solution:
package action;
import java.util.Scanner;
public class demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double [][] num = new double[30][30];
for (int i = 0; i < num.length - 1; i++) {
for (int j = 0; j <= i; j++) {
num[i][j] = sc.nextDouble();
}
}
for (int i = 1; i < num.length; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) { // First in each line
num[i][j] += num[i-1][j]/2;
} else if (j == i) { // The last one in this line
num[i][j] += num[i-1][j-1]/2;
} else {
num[i][j] += num[i-1][j-1]/2 + num[i-1][j]/2;
}
}
}
for (int i = 0; i < 30; i++) {
for (int j = 0; j <= i; j++) {
System.out.print(num[i][j]+" ");
}
System.out.println();
}
// Find the maximum and minimum values on line 30
double min = 100000;
double max = 0;
for (int i = 0; i < num[29].length; i++) {
if (num[29][i] > max) {
max = num[29][i];
}
if (num[29][i] < min) {
min = num[29][i];
}
}
long ans = (long) (2086458231/min * max);
System.out.println(ans);
}
}
E. Yang Hui triangle (fill in the blank)
Yang Hui triangle is also called Pascal triangle, which can be seen in many quantitative relations and is very important.
Line 0: 1
Line 1: 1
Line 2: 1
Line 3: 1 3 1
Line 4: 1 4 6 4 1
....
The elements on both sides are 1, and the elements in the middle are the sum of the elements in the upper left corner and the elements in the upper right corner.
We agreed that the row number and column number are counted from 0.
So: the second element in line 6 is 15 and the third element is 20
Intuitively, we need to open up a two-dimensional array. In fact, one-dimensional array can also be competent.
The following program is the solution of "moving" with one-dimensional array.
public class A
{
/ / row and col of Yang Hui triangle
static long f(int row, int col){
if(row<2) return 1;
if(col==0) return 1;
if(col==row) return 1;
long[] a = new long[row+1];
a[0]=1;
a[1]=1;
int p = 2;
while(p<=row){
a[p] = 1;
for( __________________ ) a[q] = a[q] + a[q-1];
p++;
}
return a[col];
}
public static void main(String[] args){
System.out.println(f(6,2));
System.out.println(f(6,3));
}
}
Please carefully analyze the source code and complete the missing code in the underlined part.
Note: submit only the missing code, not the existing code and symbols. And don't submit explanatory text.
Solution:
package action;
public class demo {
// row and col of Yang Hui triangle
static long f(int row, int col){
if(row<2) return 1; // The first two lines are 1
if(col==0) return 1; // The first in each line is 1
if(col==row) return 1; // The last one in each line is 1
long[] a = new long[row+1]; // An array that stores each row of data
a[0]=1; // This can be regarded as the first value and the second value of the first line. When the next line, this will change
a[1]=1;
int p = 2; // Number of rows
while(p<=row){
a[p] = 1; // The last number in this line is 1
for(int q = p - 1;q > 0 ;q--){
a[q] = a[q] + a[q-1]; // In fact, this also calls the data of the previous line
}
p++; // next row
}
return a[col]; // Returns the column value corresponding to this row
}
public static void main(String[] args){
System.out.println(f(6,2));
System.out.println(f(6,3));
}
}
F. Maximum common substring
The maximum common substring is to find the maximum length that can be matched in all substrings of two strings.
For example: "abcdkkk" and "baabcddabc",
The longest common substring that can be found is "abcd", so the maximum common substring length is 4.
The following program is solved by matrix method, which is a more effective solution for the case of small string size.
Please analyze the idea of this solution and complete the missing code in the underlined part.
public class A
{
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] = _______________________ ; // Fill in the blanks
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);
}
}
Note: submit only the missing code, not the existing code and symbols. And don't submit explanatory text.
Solution:
package action;
public class demo {
static int f(String s1, String s2)
{
// Cut two strings into character arrays
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]) { // When this value is equal, then I want to add the number above it and + 1 to get the length of this
a[i][j] = a[i-1][j-1]+1; //Fill in the blanks
if(a[i][j] > max) max = a[i][j]; // Replace maximum common substring
}
}
}
return max;
}
public static void main(String[] args){
int n = f("abcdkkk", "baabcdadabc");
System.out.println(n);
}
}
G. Excel address
The address representation of Excel cells is very interesting. It uses letters to represent column numbers.
For example,
A stands for column 1,
B represents column 2,
Z represents column 26,
AA means column 27,
AB stands for column 28,
BA stands for column 53,
....
Of course, the maximum column number of Excel is limited, so it is not difficult to convert.
If we want to generalize this representation, can we convert large numbers into long sequences of letters?
This topic is to output the corresponding Excel address representation of the input number.
For example,
Input:
26
Then the program should output:
Z
Another example is,
Input:
2054
Then the program should output:
BZZ
We agree that the input integer range [12147483647]
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print like "please input..." Superfluous content.
All code is placed in the same source file. After debugging, the copy is submitted to the source code.
Do not use package statements. Do not use jdk1 7 and above.
The name of the Main class must be: Main, otherwise it will be treated as an invalid code.
Solution:
package action;
import java.util.Scanner;
public class demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int [] litter = new int[10]; // Bit storage value
int n = sc.nextInt();
int num = 1; // Which number
while (n != 0) {
if (n % 26 == 0) { // If it can be divided completely, it is z
litter[num] = 26 + 64; // 65 is A
n -= 1;
} else {
litter[num] = n % 26 + 64;
}
n /= 26;
num++;
}
// Flashback printing
for (int i = num - 1; i > 0; i--) {
System.out.print((char)litter[i]);
}
}
}
H. Horse drawn cart
When you were young, did you play card games?
There is a game called "horse drawn cart". The rules are very simple, but it is very attractive to children.
The rules are briefly described as follows:
Suppose the children participating in the game are A and B. at the beginning of the game, they get the random card sequence as follows:
Party A: [K, 8, X, K, A, 2, A, 9, 5, A]
Party B: [2, 7, K, 5, J, 5, Q, 6, K, 4]
Where X means "10", we ignore the suit of cards.
Starting from Party A, a and B play cards in turn.
When it's a player's turn to play, he takes one from the head of his card queue, puts it on the table and presses it on the top card (if any).
In this example, the game process:
A out of K, B out of 2, a out of 8, B out of 7, a out of X. at this time, the sequence on the table is:
K,2,8,7,X
When it's B's turn to play, his card K is the same as the K in the card sequence on the table, so win back the cards including K and between the two KS and put them at the end of his own card team. Note: for the convenience of operation, the order of placing cards is opposite to that on the table.
At this time, the cards in the hands of A and B are:
Party A: [K, A, 2, A, 9, 5, A]
Party B: [5, J, 5, Q, 6, K, 4, K, X, 7, 8, 2, K]
The winning side continues to play. That is, B goes on to 5, A goes on to K, B goes on to J, A goes on to A, B goes on to 5, and wins again.
5,K,J,A,5
At this time, the cards in the hands of both parties:
Party A: [2, A, 9, 5, A]
Party B: [Q, 6, K, 4, K, X, 7, 8, 2, K, 5, A, J, K, 5]
Note: more often, the winning party can't win all the cards on the table, but take the same card point and its middle part. But in any case, the winning party continues to play cards. Sometimes it is allowed to win again just after playing cards.
When a party loses the last card in his hand, but cannot win the card from the table, the game ends immediately.
For the initial hand of this example, A will lose in the end, while B's last hand is:
9K2A62KAX58K57KJ5
The task of this question is to know the initial card order of both sides and calculate the card order in the hands of the winning party at the end of the game. When the game cannot end, output - 1.
The input is 2 lines and 2 strings, which respectively represent the initial card sequence in the hands of A and B.
The output is 1 line and 1 string, indicating the card sequence in the hand of the party who plays first and wins last.
For example,
Input:
96J5A898QA
6278A7Q973
Then the program should output:
2J9A7QA6Q6889977
Another example,
Input:
25663K6X7448
J88A5KJXX45A
Then the program should output:
6KAJ458KXAX885XJ645
We agreed that the length of the input string should not exceed 30
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print like "please input..." Superfluous content.
All code is placed in the same source file. After debugging, the copy is submitted to the source code.
Do not use package statements. Do not use jdk1 7 and above.
The name of the Main class must be: Main, otherwise it will be treated as an invalid code.
Solution:
package action;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class demo {
static char temp;
static boolean ok = true;
static boolean flag = true;
static ArrayList<Character> a = new ArrayList<Character>();
static ArrayList<Character> b = new ArrayList<Character>();
static ArrayList<Character> onging = new ArrayList<Character>();
public static void main(String[] args) {
String str;
Scanner input = new Scanner(System.in);
// input
str = input.next();
for (char cha : str.toCharArray()) {
a.add(cha);
}
str = input.next();
for (char cha : str.toCharArray()) {
b.add(cha);
}
input.close();
// implement
// true means to continue playing cards, and false means to have no row
while (ok) {
// flag is the key point for me to switch
if (flag) {
ok = underway(a, onging);
if (ok) {
flag = sourse(flag, a, onging);
}
} else {
ok = underway(b, onging);
if (ok) {
flag = sourse(flag, b, onging);
}
}
}
// Print
if (flag) {
Iterator<Character> it = b.iterator();
while (it.hasNext()) {
System.out.print(it.next());
}
} else {
Iterator<Character> it = a.iterator();
while (it.hasNext()) {
System.out.print(it.next());
}
}
}
// play
public static boolean underway(ArrayList<Character> x, ArrayList<Character> onging) {
temp = x.remove(0);
onging.add(temp);
// If one of them has no cards or has a winning situation (in which the cards can be taken away)
if (x.size() == 0 && onging.lastIndexOf(temp) == onging.indexOf(temp)) {
return false;
}
return true;
}
// I need to verify every time I play cards
public static boolean sourse(boolean flag, ArrayList<Character> x, ArrayList<Character> onging) {
if (onging.size() != 0) {
// The location update description of temp appears, and another temp appears. Continue to execute after taking the card; On the contrary, if the same situation does not appear, it will be executed by individuals
if (onging.lastIndexOf(temp) == onging.indexOf(temp)) {
return !flag;
}
int end = onging.indexOf(temp) - 1;
// Add the middle of lastIndex---Index to x and remove it from ongoing at the same time
while (onging.size() - 1 != end) {
int onMax = onging.size() - 1;
x.add(onging.get(onMax));
onging.remove(onMax);
}
}
return flag;
}
}
1. Frog jumping cup
The popular pet of Planet X is frog, which generally has two colors: white and black.
The inhabitants of Planet X like to put them in a row of tea cups so that they can watch them jump around.
As shown in the figure below, there is a row of cups. The one on the left is empty, and the cup on the right has a frog in each.
*WWWBBB
Among them, the letter W represents the white frog, B represents the black frog, and * represents the empty cup.
The frogs of Planet X have some hobbies. They only do one of three actions:
1. Jump into the adjacent empty cup.
2. Jump into the empty cup with one other frog (whatever color).
3. Jump into an empty cup across two other frogs (any color).
For the situation shown in the figure above, only one step can jump to the situation shown in the figure below:
WWW*BBB
The task of this question is to know the initial situation. It takes at least a few steps to jump to another target situation.
The input is 2 lines and 2 strings, indicating the initial situation and target situation.
The output is required to be an integer indicating at least how many steps of frog jump are required.
For example:
Input:
*WWBB
WWBB*
Then the program should output:
2
Another example is,
Input:
WWW*BBB
BBB*WWW
Then the program should output:
10
We agreed that the length of the input string should not exceed 15
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print like "please input..." Superfluous content.
All code is placed in the same source file. After debugging, the copy is submitted to the source code.
Do not use package statements. Do not use jdk1 7 and above.
The name of the Main class must be: Main, otherwise it will be treated as an invalid code.
Solution:
package action;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class demo {
static String start;
static String end;
static Queue<State> q = new LinkedList<>();
static Set<String> set = new HashSet<>();// Filter paper repeat queue mode
static int[] dir = { 1, 2, 3, -1, -2, -3 };// Six states, - 3 means jumping three distances to the left
public static String swap(int a, int b, String str) {// Exchange characters at a and b in str
char cs[] = str.toCharArray();
char temp = cs[a];
cs[a] = cs[b];
cs[b] = temp;
str = new String(cs);
return str;
}
public static int bfs(String now, int pos, int step) {
q.add(new State(now, pos, step));
while (!q.isEmpty()) {
State curState = q.poll();
if (curState.pattern.equals(end))
return curState.step;
if (set.contains(curState.pattern)) {
continue;
} else {
set.add(curState.pattern);
}
for (int i = 0; i < dir.length; i++) {// Six states
int nextPos = curState.pos + dir[i];// Position of the next empty cup
if (nextPos < curState.pattern.length() && nextPos >= 0) {// It has to be in a legal position
String temp = curState.pattern;// Record the current queue status
String nextPattern = swap(curState.pos, nextPos, temp);// Exchange and generate a new queue mode
State nextState = new State(nextPattern, nextPos, curState.step + 1);
if (!set.contains(nextPattern))
q.add(nextState);
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
start = sc.nextLine();
end = sc.nextLine();
sc.close();
int pos = 0;
for (int i = 0; i < start.length(); i++) {
if (start.charAt(i) == '*') {
pos = i;
break;
}
}
System.out.println(bfs(start, pos, 0));
}
}
class State {
String pattern;// Current queue mode
int pos;// *Index of
int step;// Number of steps from the initial queue mode to the current queue mode
public State(String now, int pos, int step) {
this.pattern = now;
this.pos = pos;
this.step = step;
}
}
J. Graphic typesetting
Xiao Ming needs to add N pictures to a document, of which the width of the ith picture is Wi and the height is Hi.
Assuming that the width of the paper is M, the document editing tool used by Xiao Ming will automatically typeset the pictures in the following ways:
1. The tool will arrange as many pictures as possible in one line within the width M according to the picture order. The height of the row is the height of the highest picture in the row.
For example, if 3x4, 2x2 and 3x3 pictures are printed successively on the paper with M=10, the effect is as shown in the following figure, and the height of this line is 4.
(the column ruler is above the dividing line, and the typesetting area is below the dividing line; the rectangle composed of numbers is the layout occupied by the x picture)
0123456789
----------
111
111 333
11122333
11122333
2. If the remaining width of the current line is greater than 0 and less than the next picture, the next picture will be scaled to the remaining width of the current line (rounded up by the height), and then placed in the current line. For example, add another 4x9 picture. Since the remaining width is 2, the picture will be compressed to 2x5 and then placed at the end of the first line. At this time, the height of the row is 5:
0123456789
----------
44
111 44
111 33344
1112233344
1112233344
3. If the remaining width of the current line is 0, the tool will continue to typeset the remaining pictures from the next line until all the pictures are processed. At this time, the sum of the total height of all lines is the typesetting height of the N pictures. For example, after adding 11x1, 5x5 and 3x4 pictures, the effect is shown in the following figure, and the total height is 11:
0123456789
----------
44
111 44
111 33344
1112233344
1112233344
5555555555
66666
66666777
66666777
66666777
66666777
Now, due to the high typesetting height, the order of pictures cannot be changed. Xiao Ming had to select one of the N pictures and delete it to reduce the total height. He hopes that the layout height of the remaining N-1 pictures will be the lowest in the original order. Can you find out what the lowest height is?
Input:
The first line contains two integers M and N, representing the paper width and the number of pictures, respectively.
Next, there are N rows, with 2 integers wi and hi in each row, indicating that the size of the ith graph is Wi*Hi.
For 30% data, 1 < = n < = 1000
For 100% data, 1 < = n < = 100000, 1 < = m, WI, hi < = 100
Output:
An integer indicating the minimum typesetting height after deleting a picture.
Sample input:
4 3
2 2
2 3
2 2
Sample output:
2
Another example,
Sample input:
2 10
4 4
4 3
1 3
4 5
2 1
2 3
5 4
5 3
1 5
2 4
Sample output:
17
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 2000ms
Please output in strict accordance with the requirements, and do not print like "please input..." Superfluous content.
All code is placed in the same source file. After debugging, the copy is submitted to the source code.
Do not use package statements. Do not use jdk1 7 and above.
The name of the Main class must be: Main, otherwise it will be treated as an invalid code.
Solution:
package action;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class demo {
public static void main(String[] arg) {
solve();
}
static StringTokenizer ST;
static BufferedReader BR;
static PrintWriter PW;
static String next() {
while (ST == null || !ST.hasMoreTokens()) {
try {
ST = new StringTokenizer(BR.readLine());
} catch (Exception e) {
// TODO: handle exception
throw new RuntimeException(e);
}
}
return ST.nextToken();
}
static int nextInt() {
return Integer.parseInt(next());
}
public static void solve() {
BR = new BufferedReader(new InputStreamReader(System.in));
PW = new PrintWriter(System.out);
int m = nextInt(), n = nextInt();
Pair a[] = new Pair[n + 10];
Triple cr[] = new Triple[n + 10];
cr[0] = new Triple();
// The state added to the i-th block is processed forward, and Triple remembers the lower right coordinate (x,y) of the i-th block and the scaled height h of the i-th block
for (int i = 1; i <= n; i++) {
// establish
Triple tmp = new Triple(cr[i - 1]);
// If you don't change this line, change it
if (tmp.x == m)
tmp.x = tmp.h = 0;
// New input width and height
a[i] = new Pair(nextInt(), nextInt());
cr[i] = new Triple();
Pair b = Change(a[i], m - tmp.x);
// Save current location
cr[i].x = tmp.x + b.x;
cr[i].h = Math.max(tmp.h, b.y);
cr[i].y = cr[i].h + tmp.y - tmp.h;
}
Triple A[] = new Triple[m];
Triple B[] = new Triple[m];
for (int i = 0; i < m; i++) {
A[i] = new Triple();
B[i] = new Triple();
}
int ans = cr[n].y;
// Try each one
for (int i = n; i >= 1; i--) {
// Deal with deleting the answer of block i ah
Triple pre = cr[i - 1];
int ah;
if (pre.x == m) {
ah = pre.y + B[0].y;
} else {
ah = pre.y - pre.h + B[pre.x].y - B[pre.x].h + Math.max(pre.h, B[pre.x].h);
}
ans = Math.min(ans, ah);
// Reverse DP, process the i to n blocks and place them from position (0,j)
for (int j = 0; j < m; j++) {
Pair b = Change(a[i], m - j);
Triple tmp;
// I'll change my line after this
if (j + b.x == m)
tmp = new Triple(0, B[0].y, 0);
// If you don't change lines, it's still this
else
tmp = new Triple(B[j + b.x]);
A[j].h = Math.max(b.y, tmp.h);
A[j].y = A[j].h + tmp.y - tmp.h;
}
for (int j = 0; j < m; j++)
B[j] = new Triple(A[j]);
}
PW.print(ans);
PW.close();
}
// If the x of a is small, it returns a, otherwise it returns
static Pair Change(Pair A, int x) {
if (A.x <= x)
return new Pair(A);
return new Pair(x, (A.y * x + A.x - 1) / A.x);
}
}
class Pair implements Comparable<Pair> {
int x, y;
Pair() {
}
Pair(Pair A) {
x = A.x;
y = A.y;
}
Pair(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Pair A) {
return x == A.x ? y - A.y : x - A.x;
}
}
class Triple {
int x, y, h;
Triple() {
}
Triple(int x, int y, int h) {
this.x = x;
this.y = y;
this.h = h;
}
Triple(Triple A) {
x = A.x;
y = A.y;
h = A.h;
}
@Override
public String toString() {
return String.valueOf(x) + " " + String.valueOf(y) + " " + String.valueOf(h);
}
}
