Blue bridge cup over the years the real title and Analysis .

A： Square ten digits （ difficulty ：*）.

from 0~9 this 10 Number (s) not repeated 、 No omission , It can make up a lot of 10 Digit number .
And a lot of it happens to be squared （ It's the square of a number ）.

such as ：1026753849, It's the smallest square of them .

Please find out what the largest square is ？

Be careful ： What you need to submit is a 10 Digit number , Don't fill in any superfluous information .

analysis ：

All permutations give all permutations ,
To do something about each situation Check that will do

AC Code ：

public class Main {

public static long ans = 0;
public static int arr[] = {
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
public static void tolong() {

long t = 0;
for (int i = 0; i < 10; i++) {

t *= 10;
t += arr[i];
}
long x = (long) Math.sqrt(t);
if (x * x == t)
ans = Math.max(ans, t);
}
public static void qpl(int k) {

if (k >= arr.length)
tolong();
else {

for (int i = k; i < arr.length; i++) {

int t = arr[i];
arr[i] = arr[k];
arr[k] = t;
qpl(k + 1);
t = arr[i];
arr[i] = arr[k];
arr[k] = t;
}
}
}
public static void main(String[] args) {

qpl(0);
System.out.println(ans);
}
}

B： Life game （ difficulty ：****）.

Conway life game is English mathematician John · Horton · Conway is in 1970 Cellular automata invented in .
This game is in an infinite size 2D On the grid .

At the beginning , In each of these little squares lives a living or dead cell .
At the next moment, the state of each cell is determined by the cell state of the eight cells around it .

say concretely ：

1. When the current cell is alive , When the surrounding is below 2 individual （ It doesn't contain 2 individual ） When you live with cells , The cell becomes dead .（ The number of simulated lives is scarce ）
2. When the current cell is alive , When there is 2 Or 3 When we have a living cell , The cell remains the same .
3. When the current cell is alive , When there is 3 When there are more than living cells , The cell becomes dead .（ Too much simulated life ）
4. When the current cell is dead , When there is 3 When we have a living cell , The cell becomes viable . （ Simulation reproduction ）

All cells in the current generation were treated with the above rules at the same time , You can get the next generation of cell maps . Continue to process the cell map of this generation according to the rules , You can get a cell map of the next generation , Go round and begin again .

What we are going to discuss in this topic is a very special pattern , It's called "Gosper glider gun"：

Suppose that the initial state above is the first 0 generation , May I ask 1000000000( One billion ) How many living cells are there ？

Be careful ： We assume that cellular machines are infinite 2D On the grid , It's not just the space drawn in the title .
Of course , For distant places , Its initial state is all dead cells .

Be careful ： You need to submit an integer , Don't fill in extra content .

analysis ：

This question is more complicated , Need to have a keen observation , There are also some basis for number theory .
First, we iterate the state hundreds of times , Then observe the rules
And then it's easy to discover every 30 The next iteration is a cycle （ this TM Who can find out ？？？）
Then save the period array , According to a billion times, you can .

AC Code ：

// The following procedure is divided into two paragraphs
// The first paragraph seeks the period
// The second paragraph seeks results

import java.util.HashSet;
public class B Life game mod {

public static int maxn=1000;
public static char map[][]=new char [maxn][maxn];
public static char now[][]=new char [maxn][maxn];
public static char c[][]={

{
'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',},
{
'.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','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','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.','.',}
};
public static HashSet<String> set=new HashSet<String>();
public static String tos(){

StringBuilder sBuilder=new StringBuilder();
for(int i=0;i<maxn;i++){

for(int j=0;j<maxn;j++){

sBuilder.append(map[i][j]);
}
}
return sBuilder.toString();
}
public static void next(){

for(int i=1;i<maxn-1;i++){

for(int j=1;j<maxn-1;j++){

int cnt=0;
for(int x=-1;x<2;x++){

for(int y=-1;y<2;y++){

if(x==0&&y==0)continue;
if(map[i+x][j+y]=='X')cnt++;
}
}
if(map[i][j]=='X'){

if(cnt==2||cnt==3)now[i][j]='X';
else now[i][j]='.';
}else{

if(cnt==3)now[i][j]='X';
else now[i][j]='.';
}
}
}
for(int i=1;i<maxn-1;i++){

for(int j=1;j<maxn-1;j++){

map[i][j]=now[i][j];
}
}
}
public static int comput(){

int sum=0;
for(int i=0;i<maxn;i++){

for(int j=0;j<maxn;j++){

if(map[i][j]=='X')sum++;
}
}
return sum;
}
public static void main(String[] args) {

for(int i=0;i<maxn;i++){

for(int j=0;j<maxn;j++){

map[i][j]='.';
}
}
for(int i=0;i<c.length;i++){

for(int j=0;j<c[i].length;j++){

map[maxn/2+i][maxn/2+j]=c[i][j];
}
}
String string=tos();
int cnt=0,sum=0,cur=0;
while(!set.contains(string)){

set.add(string);
cnt++;
sum=comput();
next();
string=tos();
cur=comput();
System.out.print(cur-sum+",");
if(cnt%30==0){

System.out.println();
}
}
System.out.println(cnt+" "+set.size());
}
}

public class Main {

public static int mod[] = {
 3, 4, 5, 3, -7, 7, -3, 13, -19, 6, 2, 4, 1, 1, -14, 2, 3, 6, 1, 0, 0, -5, 11, -17, 7,
-3, 0, 3, -2, -7 };
public static void main(String[] args) {

long ans = 36;
for (int i = 1; i < mod.length; i++)
mod[i] += mod[i - 1];
ans += (1000000000 / 30) * mod[mod.length - 1];
ans += mod[1000000000 % 30 - 1];
System.out.println(ans);
}
}

C： Tree display （ difficulty ：*）.

The classification structure can be represented vividly by tree . such as ： A typical example is the file system .

The nodule in the tree is paternal . We were showing , Indent the child to the right （ Use spaces , No tab）, And add the necessary connectors , In order to make the hierarchical relationship more striking .

The following code is for this purpose , Please read the source code carefully , And fill in the missing code in the underlined section .

import java.util.*;
class MyTree
{

private Map<String, List<String>> map_ch = new HashMap<String, List<String>>();
private Map<String,String> map_pa = new HashMap<String,String>();
public void add(String parent, String child)
{

map_pa.put(child, parent);
List<String> lst = map_ch.get(parent);
if(lst==null){

lst = new ArrayList<String>();
map_ch.put(parent, lst);
}
lst.add(child);
}
public String get_parent(String me){

return map_pa.get(me);
}
public List<String> get_child(String me){

return map_ch.get(me);
}
private String space(int n)
{

String s = "";
for(int i=0; i<n; i++) s += ' ';
return s;
}
private boolean last_child(String x){

String pa = map_pa.get(x);
if(pa==null) return true;
List<String> lst = map_ch.get(pa);
return lst.get(lst.size()-1).equals(x);
}
public void show(String x){

String s = "+--" + x;
String pa = x;
while(true){

pa = map_pa.get(pa);
if(pa==null) break;
s = ___________________________________ ; // Fill in the blanks 
}
System.out.println(s);
}
public void dfs(String x){

show(x);
List<String> lst = map_ch.get(x);
if(lst==null) return;
for(String it: lst){

dfs(it);
}
}
}
public class TreeView
{

public static void main(String[] args)
{

MyTree tree = new MyTree();
tree.add("root", "dog");
tree.add("root", "cat");
tree.add("root", "duck");
tree.add("dog", "AAdog");
tree.add("dog", "BBdog");
tree.add("dog", "CCdog");
tree.add("AAdog", "AAdog01");
tree.add("AAdog", "AAdog02");
tree.add("cat", "XXcat");
tree.add("cat", "YYcat");
tree.add("XXcat","XXcat-oo");
tree.add("XXcat","XXcat-qq");
tree.add("XXcat-qq", "XXcat-qq-hahah");
tree.add("duck", "TTduck");
tree.add("TTduck", "TTduck-001");
tree.add("TTduck", "TTduck-002");
tree.add("TTduck", "TTduck-003");
tree.add("YYcat","YYcat.hello");
tree.add("YYcat","YYcat.yes");
tree.add("YYcat","YYcat.me");
tree.dfs("root");
}
}

For the test data in the question , Output results :

Be careful , Just fill in the missing code in the underlined part , Don't copy existing code or symbols .

analysis ：

Observe the topic and find that we only need to do a string splicing work ,
And we looked at the picture and found ,
When this node is the last node of the parent node , There is no need for |, Other situations are |
So we speculate that the splicing is s=(last_child(pa)?" “:”|")+space(4)+s;

AC Code ：

Can't hand in the question , But the results are correct

package JAVA2017;
import java.util.*;
public class C Tree display {

public static void main(String[] args) {

MyTree tree = new MyTree();
tree.add("root", "dog");
tree.add("root", "cat");
tree.add("root", "duck");
tree.add("dog", "AAdog");
tree.add("dog", "BBdog");
tree.add("dog", "CCdog");
tree.add("AAdog", "AAdog01");
tree.add("AAdog", "AAdog02");
tree.add("cat", "XXcat");
tree.add("cat", "YYcat");
tree.add("XXcat", "XXcat-oo");
tree.add("XXcat", "XXcat-qq");
tree.add("XXcat-qq", "XXcat-qq-hahah");
tree.add("duck", "TTduck");
tree.add("TTduck", "TTduck-001");
tree.add("TTduck", "TTduck-002");
tree.add("TTduck", "TTduck-003");
tree.add("YYcat", "YYcat.hello");
tree.add("YYcat", "YYcat.yes");
tree.add("YYcat", "YYcat.me");
tree.dfs("root");
}
}
class MyTree {

private Map<String, List<String>> map_ch = new HashMap<String, List<String>>();
private Map<String, String> map_pa = new HashMap<String, String>();
public void add(String parent, String child) {

map_pa.put(child, parent);
List<String> lst = map_ch.get(parent);
if (lst == null) {

lst = new ArrayList<String>();
map_ch.put(parent, lst);
}
lst.add(child);
}
public String get_parent(String me) {

return map_pa.get(me);
}
public List<String> get_child(String me) {

return map_ch.get(me);
}
private String space(int n) {

String s = "";
for (int i = 0; i < n; i++)
s += ' ';
return s;
}
private boolean last_child(String x) {

String pa = map_pa.get(x);
if (pa == null)
return true;
List<String> lst = map_ch.get(pa);
return lst.get(lst.size() - 1).equals(x);
}
public void show(String x) {

String s = "+--" + x;
String pa = x;
while (true) {

pa = map_pa.get(pa);
if (pa == null)
break;
// Also on the 
// s=(map_pa.get(pa)==null||get_child(map_pa.get(pa)).indexOf(pa)==get_child(map_pa.get(pa)).size()-1?" ":"| ")+s;
s=(last_child(pa)?" ":"|")+space(4)+s;
// s = ___________________________________ ; // Fill in the blanks 
}
System.out.println(s);
}
public void dfs(String x) {

show(x);
List<String> lst = map_ch.get(x);
if (lst == null)
return;
for (String it : lst) {

dfs(it);
}
}
}

D： Little calculator （ difficulty ：**）.

Analog program calculator , Enter the instructions in turn , The instructions that may contain are

1. Numbers ：‘NUM X’,X For a string containing only uppercase letters and numbers , Represents a number in the current radix
2. Operation instruction ：‘ADD’,‘SUB’,‘MUL’,‘DIV’,‘MOD’, Respectively, it means adding and subtracting , Division of business , Remainder by Division
3. The instruction of the conversion of the base ：‘CHANGE K’, Convert the current base to K Base number (2≤K≤36)
4. Output instruction ：‘EQUAL’, Output the result in current system
5. Reset command ：‘CLEAR’, Clear the current number

Instructions are given according to the following rules ：
Numbers , Operation instructions are not given continuously , The instruction of the conversion of the base , Output instruction , Reset instructions may be given continuously
The first digit after an operation instruction , Represents the number involved in the operation . And there will be no operation instruction and output instruction between the operation instruction and the digit
The first digit that appears after the reset command , Represents the base value . And there will be no operation instruction and output instruction between the reset instruction and the first digit
Binary conversion instructions can appear anywhere

During the operation, the intermediate variables are all nonnegative integers , And less than 2^63.
In capital ’A’_{'Z’ Express 10}35

[ Input format ]
The first 1 That's ok ：1 individual n, Indicates the number of instructions
The first 2…n+1 That's ok ： Each line gives an instruction . The sequence of instructions must be ’CLEAR’ For a start , And meet the instruction rules

[ Output format ]
Give each time in turn ’EQUAL’ The result

[ The sample input ]
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL

[ Sample output ]
2040

Additional explanation ：

1. n Range of values : 1<= n < 50000
2. The initial default base is decimal

analysis ：

The simple problem of dealing with calculators ,
For data storage , We only use decimal storage
If you need output , And then convert the decimal system to the corresponding R Base number
Then we define two variables nums[2] It can be used to store data
Take different measures for each different operation + - * / % operation

But here's the thing , Output of the M-ary to use capital output , Otherwise the result is not correct ,
Such as abc Should be written as ABC

AC Code ：

import java.util.Scanner;
// Case sensitive 
public class Main {

public static long nums[]=new long[2];
public static int p=0,r=10;
public static String op;
public static void comput(){

if(op.equals("ADD")){

nums[0]+=nums[1];
}else if(op.equals("SUB")){

nums[0]-=nums[1];
}else if(op.equals("MUL")){

nums[0]*=nums[1];
}else if(op.equals("DIV")){

nums[0]/=nums[1];
}else if(op.equals("MOD")){

nums[0]%=nums[1];
}
nums[1]=0;
p=0;
}
public static void oper(String s[]){

if(s[0].equals("NUM")){

nums[p]=Long.parseLong(s[1], r);
if(p==1) comput();
}else if(s[0].equals("CHANGE")){

r=Integer.parseInt(s[1]);
}else if(s[0].equals("EQUAL")){

System.out.println(Long.toString(nums[0], r).toUpperCase());
}else if(s[0].equals("CLEAR")){

nums[p]=0;
}else{

p=(p+1)%2;
op=s[0];
}
}
public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
int n=sc.nextInt();sc.nextLine();
String s[];
while(n-->0){

s=sc.nextLine().split(" ");
oper(s);
}
}
}

E： Fill in the letter game （ difficulty ：***）.

Xiao Ming often plays LOL Addiction to games , Once he wanted to challenge K The master , lo K The master said ：
“ Let's play a game of blanks and letters first , If you can't win me , Just stop playing LOL 了 ”.

K The master drew a line on the paper n Lattice , Ask Xiao Ming and him to fill in the letters alternately .

also ：

1. When it's someone's turn to fill in , You can only fill in a blank L or O
2. Who first made the letters up “LOL” The words... , Who wins .
3. If all the lattices are filled with , Still can't make up LOL, And draw .

Xiao Ming tried several times and lost , He is ashamed of , I hope you can use the computer to help him solve the mystery .

The input format of this question is ：
first line , Numbers n（n<10）, It means that there is n An initial situation .
Next ,n That's ok , One string per line , To show the beginning of the situation .
such as ：

Request output n A digital , To show that for each situation , If Xiao Ming fills in first , When K When the master always uses the best move , Xiao Ming's best result .
1 It means that you can win
-1 It means you have to lose
0 It means that it can be flattened

for example ,

analysis ：

Let's define a Map, Used to store status and results ,
For every unsolved problem , We can take two options for each location ,
programme 1, place L
programme 2, place O
And then iterate down in a sequence ,
Theoretically, the time complexity of analysis is very high , But it passed all the data ...

AC Code ：

import java.util.*;
public class Main {

static Map<String, Integer> map = new HashMap<String, Integer>();
// -1: Must lose ,0: It ends in a draw , 1: It will win 
static int f(char[] x) {

String s = new String(x);
if (map.get(s) != null)
return map.get(s);
if (s.contains("LOL")) {

map.put(s, -1);
return -1;
}
if (s.contains("*") == false) {

map.put(s, 0);
return 0;
}
boolean ping = false;
for (int i = 0; i < x.length; i++) {

if (x[i] == '*') {

try {

x[i] = 'L';
int t = f(x);
if (t < 0) {

map.put(s, 1);
return 1;
}
if (t == 0)
ping = true;
x[i] = 'O';
t = f(x);
if (t < 0) {

map.put(s, 1);
return 1;
}
if (t == 0)
ping = true;
} finally {

x[i] = '*';
}
}
}
if (ping) {

map.put(s, 0);
return 0;
}
map.put(s, -1);
return -1;
}
static int game(String s) {

map.clear();
return f(s.toCharArray());
}
public static void main(String[] args) {

Scanner scan = new Scanner(System.in);
int n = Integer.parseInt(scan.nextLine().trim());
for (int i = 0; i < n; i++) {

System.out.println(game(scan.nextLine().trim()));
}
}
}

F： Interval shift （ difficulty ：*****）.

There is... On the axis n Closed interval ：D1,…,Dn.
And the interval Di Use a pair of integers [ai, bi] To describe , Satisfy ai < bi.
The sum of the lengths of these intervals is known to be at least 10000.
therefore , By moving these intervals appropriately , You can always make them “ and ” Cover [0, 10000]—— in other words [0, 10000] Every point in this interval falls in at least one interval .
You want to find a way to move , So that the displacement of the interval with the largest displacement difference is the smallest .

say concretely , Suppose you will Di Move to [ai+ci, bi+ci] This position . You want to make maxi{|ci|} Minimum .

【 Input format 】
The first line of input contains an integer n, Represents the number of intervals .
Next there is n That's ok , Each row 2 It's an integer ai, bi, Separated by a space , Indicates the interval [ai, bi].
Make sure that the sum of the lengths of the intervals is at least 10000.

【 Output format 】
Output a number , Answer . If the answer is an integer , Output only the integer part . If the answer is not an integer , The output is rounded to one decimal place .

【 The sample input 】
2
10 5010
4980 9980

【 Sample output 】
20

【 Sample explanation 】
The first interval moves to the left 10; The second interval moves to the right 20.

【 The sample input 】
4
0 4000
3000 5000
5001 8000
7000 10000
【 Sample output 】
0.5
【 Sample explanation 】
The first 2 Move the interval to the right 0.5; The first 3 Move the interval to the left 0.5 that will do .

【 Data scale and agreement 】
about 30% The evaluation case of ,1 <= n <= 10;
about 100% The evaluation case of ,1 <= n <= 10000,0 <= ai < bi <= 10000.

analysis ：

Interval compression algorithm , To be updated
I forgot to remember to urge me later ....

AC Code ：