Studio project 4
practice
Fighting method of eminent monk
Description
In ancient times, eminent monks were often invited to do things in funeral activities. After the ceremony, sometimes there will be interesting programs of "fighting Dharma of eminent monks" to relieve the depressed atmosphere.
The general steps of the program are as follows: first, use grain (usually rice) to "draw" several steps on the ground (indicating N-level floating slaughter). A number of young monks randomly "stood" on a certain step. People must stand on the highest step, and no one else is allowed. (as shown in Figure 1)
Two mages participating in the game command a little monk to walk up any multi-level steps, but they will be blocked by the little monk standing on the high-level steps and cannot cross. Two little monks cannot stand on the same step, nor can they move to the lower step.
The two mages issued instructions in turn. Finally, all the little monks will be squeezed on the high steps and can no longer move upward. If it is the turn of a mage to command and he cannot continue to move, the game ends and the mage admits defeat.
For the known number of steps and the distribution position of young monks, please calculate how the mage who sends the first instruction should make a decision to ensure victory.
Input
The input data is a line of N integers separated by spaces, indicating the position of the little monk. The number of steps starts from 1, so the position of the last little monk is the total number of steps. (n < 100, total number of steps < 1000)
Output
The output is a line of two integers separated by spaces: A and B, indicating that the little monk in position a is moved to position B. If there are multiple solutions, the solution with smaller a value will be output; if there is no solution, -1 will be output.
Sample Input 1
1 5 9
Sample Output 1
1 4
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
#Nim game problem, take two monks as a group, and then XOR,
#In this example: 3, 3.
# Take XOR, XOR is not 0, win first, XOR is 0, lose first.
#So we just need to judge whether XOR is 0
h = list(map(int, input().split()))
hlen = len(h)
d = [0 for _ in range(hlen - 1)]
for i in range(1, hlen):
d[i - 1] = h[i] - h[i - 1] - 1
sum = 0
for i in range(0, hlen - 1, 2):
sum ^= d[i]
# print(sum)
if sum == 0:
print(-1)
else:
for i in range(hlen - 1):
step = 1
while True:
# print(h)
if h[i] + step >= h[i + 1]:
break
d[i] -= step
if (i != 0):
d[i - 1] += step
sum = 0
for s in range(0, hlen - 1, 2):
sum ^= d[s]
if sum == 0:
print(h[i], h[i] + step)
break
d[i] += step
if i != 0:
d[i - 1] -= step
step += 1
Horizontal printing binary tree
Description
Binary trees can be used for sorting. The principle is very simple: when adding a new node to a sorted binary tree, compare it with the root node first. If it is small, it will be handed over to the left subtree for further processing, otherwise it will be handed over to the right subtree.
When an empty subtree is encountered, the node is placed in that position.
For example, the input sequence of 108 5 7 12 4 should be built into a binary tree, as shown in the figure below Indicates blank.
...|-12
10-|
...|-8-|
...|...|-7
...|-5-|
...|-4
Requirements of this topic: establish a sorted binary tree according to the known numbers, and print the binary tree horizontally in the standard output.
Input
The input data is a line of N integers separated by spaces. N < 100, each number does not exceed 10000.
There are no duplicate numbers in the input data.
Output
Output the horizontal representation of the sorted binary tree. In order to facilitate the marking program to compare the number of spaces, please replace the spaces with periods:
Sample Input 1
...|-12
10-|
...|-8-|
...|...|-7
...|-5-|
...|-4
Sample Output 1
10 5 20
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
class DNode:
def __init__(self, data, depth, parent, lchild=None, rchild=None):
self.data = data
self.depth = depth
self.parent = parent
self.lchild = lchild
self.rchild = rchild
class BiTree:
def __init__(self):
self.root = None
def insert(self, value, node=None, depth=0):
if not self.root:
self.root = DNode(value, depth, None)
return
if not node:
node = self.root
depth += 1
if value < node.data:
if not node.lchild:
node.lchild = DNode(value, depth, node)
else:
self.insert(value, node.lchild, depth)
else:
if not node.rchild:
node.rchild = DNode(value, depth, node)
else:
self.insert(value, node.rchild, depth)
def L(n):
return len(str(n))
def centre(node, visit):
if not node:
return
centre(node.rchild, visit)
visit(node)
centre(node.lchild, visit)
def P(node, parents):
if node.parent:
parents.append(node.parent)
P(node.parent, parents)
def TreePrint(node):
flag = ""
parents = []
P(node, parents)
for i in range(len(parents)-1, -1, -1):
p = parents[i]
nodelen = 0
if p.parent:
nodelen+=1
if p.lchild or p.rchild:
nodelen+=1
nodelen+=L(p.data)
flag += "."*nodelen
if i > 0:
# Vertical lines are added when crossing left and right, and points are used instead
if node.data < p.data and node.data > parents[i-1].data:
flag += "|"
elif node.data > p.data and node.data < parents[i-1].data:
flag += "|"
else:
flag += "."
if node.parent:
flag += "|-"
flag += str(node.data)
if node.lchild or node.rchild:
flag += "-|"
print(flag)
n = list(map(int, input().split()))
tree = BiTree()
for i in n:
tree.insert(i)
centre(tree.root, TreePrint)
Minister's travel expenses
Description
A long time ago, the kingdom of T prospered unprecedentedly. In order to better manage the country, the Kingdom has built a large number of expressways to connect the capital and the major cities in the kingdom.
In order to save money, the ministers of T country have formulated a set of excellent construction scheme after thinking, so that any big city can reach directly from the capital or indirectly through other big cities. At the same time, if you do not repeatedly pass through big cities, the scheme from the capital to each big city is unique.
J is an important Minister of state T. he patrols among major cities and observes the people's conditions. Therefore, from one city to another has become J's most common thing. He has a money bag, which is used to store the travel expenses between cities.
Smart J found that if he didn't stop to repair in a city, in the process of continuous travel, the toll he spent was related to the distance he had traveled. In the kilometer from kilometer x to kilometer x+1 (x is an integer), the toll he spent was so much as x+10. In other words, it costs 11 to walk one kilometer and 23 to walk two kilometers.
Minister J wants to know: what is the maximum cost of all possible travel expenses when he starts from one city and doesn't rest in the middle to another city?
Input
The first line of input contains an integer n, which represents the number of cities in Kingdom T, including the capital
Cities are numbered from 1. City 1 is the capital.
Next, line n-1 describes the expressway in country T (the expressway in country T must be n-1)
Three integers Pi, Qi and Di in each line indicate that there is a highway between city Pi and city Qi, with a length of Di kilometers.
Output
An integer is output to indicate the maximum travel cost of minister J.
Sample Input 1
5
1 2 2
1 3 1
2 4 5
2 5 4
Sample Output 1
135
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
Minister J costs 135 to travel from city 4 to city 5.
cnt=0
node=0
def dfs(v,k): #Perform dfs search
global cnt
global node
global vis
if k>cnt:
cnt=k
node=v
for i in range(len(E[v])):
if vis[E[v][i][0]]==False: #dfs is conducted for all points that have not been visited
vis[E[v][i][0]]=True #Mark
print(E[v][i][0])
dfs(E[v][i][0],k+E[v][i][1])
vis[E[v][i][0]]=False #to flash back
n=int(input())
E=[[] for i in range(n+1)]
vis=[False for i in range(n+1)]
for i in range(n-1):
x,y,z=map(int,input().split())
E[x].append((y,z))
E[y].append((x,z)) #Connect the points in the form of list array
vis[1]=True
dfs(1,0) #Find the node farthest from 1
vis[1]=False
cnt=0
vis[node]=True
dfs(node,0) #Starting from the node, find the farthest point, which is the farthest distance required
res=0
for i in range(1,cnt+1):
res+=i+10
print(res)
Number not available
Description
Xiao Ming opened a candy store. He is ingenious: wrap the fruit candy into two kinds: a bag of 4 and a bag of 7. Candy can't be unpacked.
When a child comes to buy sugar, he uses these two kinds of packaging to combine. Of course, some candies cannot be combined, such as buying 10 candies.
You can test it with a computer. In this case, the maximum quantity you can't buy is 17. Any number greater than 17 can be combined with 4 and 7.
The requirement of this question is to find the maximum number that cannot be combined when the quantity of two packages is known.
Input
Two positive integers, indicating the number of sugars in each package (no more than 1000)
Output
A positive integer indicating the maximum number of sugar that cannot be bought
Sample Input 1
4 7
Sample Output 1
17
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
a, b = map(int, input().split()) print(a*b-a-b)
Consecutive interval number
Description
Xiao Ming has been thinking about such a strange and interesting question these days:
How many consecutive intervals are there in a full permutation of 1~N? The definition of the serial interval here is:
If all the elements in the interval [L, R] (i.e. the L-th to r-th elements of this arrangement) can get a "continuous" sequence with a length of R-L+1 after incremental sorting, it is called this interval serial interval.
When N is very small, Xiao Ming can quickly calculate the answer, but when N becomes large, the problem is not so simple. Now Xiao Ming needs your help.
Input
The first line is a positive integer n (1 < = n < = 50000), indicating the scale of the full arrangement.
The second line is N different numbers PI (1 < = Pi < = N), indicating a full arrangement of these N numbers.
Output
Output an integer representing the number of different consecutive intervals.
Sample Input 1
4
3 2 4 1
Sample Output 1
7
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 50000;
int a[maxn];
int main(void)
{
int n,cnt=0;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
int minn=a[i],maxn=a[i];
for(int j=i;j<n;j++)
{
if(a[j]<minn) minn=a[j];
if(a[j]>maxn) maxn=a[j];
if(maxn-minn+1==j-i+1) cnt++;
}
}
printf("%d",cnt);
return 0;
}
test
Farm sunshine
Description
Planet X is very special. Its rotation speed is the same as its revolution speed, so the sun always shines at a fixed angle.
Recently, in order to develop interstellar tourism, planet X rented its space location to tourists from country Y to bask in the sun. Each rental space is a disk-shaped cloud floating in the air (the disk is parallel to the ground). Of course, this will block part of the sun, and the blocked land plants cannot grow.
The task of this question is to calculate the area of land suitable for crop growth on a farm.
Input
The first row of input data contains two integers a and b, indicating that the length and width of a farm are a and b respectively. At this time, the range of the farm is a rectangular area surrounded by coordinates (0, 0, 0), (a, 0, 0), (a, b, 0), (0, b, 0).
The second line contains a real number G, which represents the angle of sunlight. For simplicity, we assume that the sunlight is perpendicular to the width of the farm. At this time, the included angle between the sunlight and the length of the farm is g degrees. At this time, the projection point of a point in space (x, y, z) on the ground should be (x + z * ctg(g degrees), y, 0), where ctg(g degrees) represents the cotangent value corresponding to G degrees.
The third line contains a non negative integer n, which represents the number of air rentals.
The next n lines describe each rental. The i-th row contains four integers Xi, Yi, Zi and RI, indicating that the center of the i-th rental color cloud is at (xi, yi, zi) and the radius of the circle is ri.
Output
It is required to output a real number, round off and retain two significant figures to indicate the area of land on the farm where crops can grow.
Sample Input 1
10 10
90.0
1
5 5 10 5
Sample Output 1
21.46
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
#include <bits/stdc++.h>
using namespace std;
#define pdd pair<double,double>
#define l first
#define r second
const int N = 100;
double eps = 1e-6;
int n;
double a,b,x[N],y[N],r[N];
double f(double xi){
priority_queue<pdd,vector<pdd>,greater<pdd> > pq;
for(int i = 0;i < n;++i){
double y1 =r[i]*r[i]-(x[i]-xi)*(x[i]-xi);
if(y1 < eps)continue;
y1 = sqrt(y1);
pq.push(pdd(max(0.0,y[i]-y1),min(b,y[i]+y1)));
}
double ret = 0,last = 0;
while(!pq.empty()){
pdd seg = pq.top();pq.pop();
if(seg.l > last)ret += seg.r - seg.l,last = seg.r;
else if(seg.r > last)ret += seg.r - last,last = seg.r;
}
return ret;
}
double simpson(double l,double r){
double mid = (l+r)/2;
return (r-l)*(f(l)+4*f(mid)+f(r))/6;
}
double integral(double l,double r,double crt){
double mid = (l+r)/2.0,L = simpson(l,mid),R = simpson(mid,r);
if(fabs(crt-L-R)<eps)return L+R;
return integral(l,mid,L) + integral(mid,r,R);
}
int main(){
double ctg;
cin >> a >> b >> ctg >> n;
ctg = 1.0/tan(ctg/180.0*M_PI);
for(int i = 0;i < n;++i){
double z;cin >> x[i] >> y[i] >> z >> r[i];
x[i] += z * ctg;
}
priority_queue<pdd,vector<pdd>,greater<pdd> > pq;
for(int i = 0;i < n;++i){
if(r[i]==0)continue;
pq.push(pdd(max(0.0,x[i]-r[i]),min(a,x[i]+r[i])));
}
double last = 0,res = 0;
while(!pq.empty()){
pdd seg = pq.top();pq.pop();
if(seg.l > last)res += integral(seg.l,seg.r,simpson(seg.l,seg.r)),last = seg.r;
else if(seg.r > last)res += integral(last,seg.r,simpson(last,seg.r)),last = seg.r;
}
printf("%.2f\n",a*b-res);
return 0;
}
Flip a coin
Description
Xiao Ming is playing a coin flipping game.
There are some coins in a row on the table. We use * for the front and o for the back (lowercase letters, not zero).
For example, the possible situation is: OO * OO
If you flip the two coins on the left at the same time, it becomes: oooo***oooo
Now Xiao Ming's question is: if you know the initial state and the target state to be achieved, you can only flip two adjacent coins at the same time, how many times should you flip at least for a specific situation?
We agreed that flipping two adjacent coins is called one-step operation
Input
Two lines of equal length strings represent the initial state and the target state to be achieved respectively. Length of each line < 1000
Output
An integer representing the minimum number of operation steps.
Sample Input 1
. **********
oo
Sample Output 1
5
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
start=input()
end=input()
n=len(start)
flag=0
judge=[start[i]==end[i] for i in range(n)]#Compare the two inputs, True if they are the same, False if they are different
#print(judge)
for i in range(n-1):#As long as the greedy algorithm is different, it is the opposite
if not judge[i]:
judge[i]=True
judge[i+1]=not judge[i+1]
flag+=1
print(flag)
# a = True
# print(a)
# b = not a
# print(b)
Wrong note
Description
A secret related unit has issued a certain bill and wants to recover it all at the end of the year.
Each ticket has a unique ID number. The ID numbers of all bills throughout the year are continuous, but the starting number of ID is randomly selected.
Due to the negligence of the staff, an error occurred when entering the ID number, resulting in a broken ID and a duplicate ID.
Your task is to find out the ID of the broken number and the ID of the duplicate number through programming.
It is assumed that hyphenation cannot occur in the maximum and minimum numbers.
Input
The program is required to first input an integer n (n < 100) to represent the number of subsequent data lines.
Then read in N rows of data.
The data length of each line is different. It is several (no more than 100) positive integers (no more than 100000) separated by spaces. Please note that there may be redundant spaces in and at the end of the line. Your program needs to be able to handle these spaces.
Each integer represents an ID number.
Output
The program is required to output 1 line, including two integers m, N, separated by spaces.
Where, m represents the broken ID and n represents the duplicate ID
Sample Input 1
2
5 6 8 11 9
10 12 9
Sample Output 1
7 9
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
n = int(input())
ID = []
for i in range(n):
data = list(map(int, input().split()))
ID = ID + data
# print(ID)
ID.sort()
for i in range(ID[0], ID[-1]):
# for i in ID:
if i in ID:
ID.remove(i)
if i in ID:
n = i
else:
m = i
print(m, n)
Band fraction
Description
100 can be expressed as a fractional form: 100 = 3 + 69258 / 714.
It can also be expressed as: 100 = 82 + 3546 / 197.
Note: in the band fraction, the numbers 1 ~ 9 appear respectively and only once (excluding 0).
Like this band fraction, 100 has 11 representations.
Input
Read a positive integer n (n < 1000 * 1000) from the standard input
Output
The program outputs the number, and the numbers 1 ~ 9 are used to form all kinds of numbers represented by fractions without repetition or omission.
Note: it is not required to output each representation. Only the number of representations is counted!
Sample Input 1
100
Sample Output 1
11
Hint
HINT: time limit: 1.0s memory limit: 256.0MB
num = 0
n = int(input())
for i in range(1,n):
j = 1
while True:
x = (n-i)*j
l = int(len(str(x))+len(str(i))+len(str(j)))
s = str(i)+str(x)+str(j)
if l >= 10:
break
else:
if l == 9 and s.__contains__('1') and s.__contains__('2') and s.__contains__('3') and s.__contains__('4'):
if s.__contains__('5') and s.__contains__('6') and s.__contains__('7') and s.__contains__('8') and s.__contains__('9'):
num += 1
j += 1
print(num)