"Wei Lai Cup" 2022 Niuke summer multi school training camp 1 (summary of some topics)

A	Villages: Landlines

link ： Sign in — major IT Written interview preparation platform _ Cattle from
source ： Cattle from
 

Title Description

The game development team NIO Tech releases its debut game, Villages: Landlines. In this game, players develop their villages and enjoy their peaceful country life.

The game Villages: Landlines contains a one-dimensional power system. Initially, there are several power stations and buildings. The goal of the game is to make every power stations and buildings connected together in the power system, forming a connected graph. Players can build some power towers and wires in the game, which are the tools to connect power stations and buildings.

Power stations or buildings can connect to power towers without wires, while power towers must connect to each other by wires. What's more, power stations and buildings can't connect to each other directly, they must connect through power towers.

Assuming that the coordinate of a building is xix_ixi​ and its receiving radius is rir_iri​, all the power towers whose distance from the building is no greater than rir_iri​ are directly connected to it without wires. That is to say, for the power tower located at xxx, it is directly connected to the building at xix_ixi​ without wires if and only if ∣x−xi∣≤ri|x-x_i|\leq r_i∣x−xi​∣≤ri​. Similarly, assuming that the power supply radius of a power station is rsr_srs​, all the power towers whose distance from the power station is no more than rsr_srs​ are directly connected to it without wires. Supposing that the coordinates of two power towers are xAx_AxA​ and xBx_BxB​, players can connect them with the wire, and the length of wire required is ∣xA−xB∣|x_A-x_B|∣xA​−xB​∣. A power tower can be connected to any number (possibly zero) of power towers, buildings and power stations.

In order to make the game more friendly to the rookies, Nostalgia, a member of NIO Tech, decides to develop the power distribution recommendation function. In the case of using any number of power towers, players can choose exactly one power station and several buildings to get an optimal power supply scheme, which uses the shortest total length of wires to complete the power system. However, Nostalgia is not sure whether her scheme is correct, so she needs your help to calculate the total length of wires used in the optimal scheme to determine the correctness of her scheme.

Note that the players can build a new power tower at coordinate xxx even if there exists a power station or a building at xxx. There might be more than one power station or building at the same coordinate.

Input description :

The first line contains a single integer nnn (1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105).

The second line contains two integers xs,rsx_s, r_sxs​,rs​ (−109≤xs≤109,1≤rs≤109-10^9 \leq x_s \leq 10^9, 1\leq r_s\leq 10^9−109≤xs​≤109,1≤rs​≤109) — the coordinate of the power station and its power supply radius.

The iii-th line of the next n−1n-1n−1 lines contains two integers xi,rix_i, r_ixi​,ri​ (−109≤xi≤109,1≤ri≤109-10^9 \leq x_i \leq 10^9, 1\leq r_i\leq 10^9−109≤xi​≤109,1≤ri​≤109) — the coordinate of iii-th building and its receiving radius.

Output description :

Print an integer in a single line, denoting the total length of wires used in the optimal scheme.

Example 1

Input

Copy 5 0 1 0 3 5 1 6 1 9 2

5
0 1
0 3
5 1
6 1
9 2

Output

Copy 1

1

Example 2

Input

Copy 2 -1000000000 1000000000 1000000000 1000000000

2
-1000000000 1000000000
1000000000 1000000000

Output

Copy 0

0

remarks :

For the first sample, one possible optimal scheme is building power towers at 1,3,4,6,71,3,4,6,71,3,4,6,7, and connect the power towers at 333 and 444 with the wire of length 111.

#include<iostream>
#include<string>
#include<stdlib.h>
#include<cstdio>
#include<algorithm>
typedef long long ll;

using namespace std;
struct node
	{
	  ll dis,r,start,endl;
	}p[1000000];

int cmp(node a,node b)// Sort 
{
	return a.start<b.start;
 

}
int main()
{
	
     ll n;
    cin>>n;
	for(int i=0;i<n;i++)
	{
		ll dis,r;
		cin>>dis>>r;
	     p[i].dis=dis;
		 p[i].r=r;
		 p[i].start=dis-r;
		 p[i].endl=dis+r;
	}
	sort(p,p+n,cmp);
	 
	  ll s=0,start,end,start1,end1;
	  start=p[0].start;
	  end=p[0].endl;
	for(ll i=1;i<n;i++)
	{
	 
	   start1=p[i].start;
	   end1=p[i].endl;
	if(start>start1&&end<end1)
	{
	  start=start1;
	  end=end1;
	}
	if(start1>=start&&end>=end1)
		continue;
	if(start<start1){
	   if(end<start1)
	   {
	     s+=start1-end;
		
	   }
	    end=end1;

	}
	if(start1<start)
	{
	 if(end1<start)
	 {
	  s+=start-end1;
	 }
	  start=start1;
	}
	}
	cout<<s<<endl;
    return 0;
}

D	Mocha and Railgun

link ： Sign in — major IT Written interview preparation platform _ Cattle from
source ： Cattle from
 

There is a candy store near Mocha's school. It's said that the storekeeper, Dagashiya, can cast the railgun spell. To be the most powerful Mahou Shoujo, Mocha asks Dagashiya to teach her the railgun spell.

To test her mastery of this spell, Mocha creates a circular wall CCC whose center is (0,0)(0,0)(0,0). The railgun spell has a base segment ABABAB with length 2d2d2d. When it is cast, a point PPP on the circular wall will be destroyed if and only if it meets the following conditions:
 

1. The projection of point PPP on line ABABAB lies on the segment ABABAB (inclusive).
2. A,B,PA,B,PA,B,P make a counterclockwise turn, that is to say AB→×AP→>0\overrightarrow{AB} \times \overrightarrow{AP} > 0AB×AP>0.

Mocha chooses a point QQQ which strictly lies in the circle and sets QQQ as the center of the base segment. Then Mocha will choose an angle α\alphaα arbitrarily and rotate the base segment around QQQ by α\alphaα. Because Mocha is a rookie of the spell, the endpoints of the base segment will always lie in CCC strictly, which means the distance from QQQ to the wall CCC is greater than ddd.

Mocha wants to know the maximum length of the wall that can be destroyed in one cast.

You can see the note for better understanding.

Input description :

The first line is an integer TTT (1≤T≤1051\leq T\leq 10^51≤T≤105) — the number of test cases.

In each test case, the first line is an integer rrr (1≤r≤1091\leq r\leq 10^91≤r≤109) — the radius of the circular wall CCC.

The next line contains three integers xQ,yQ,dx_Q,y_Q,dxQ​,yQ​,d — the coordinates of the point QQQ and a half of the length of the base segment.

Output description :

For each test case, print a real number in a single line, denoting the maximum length of the wall that Mocha can destroy in one cast. Your answer will be considered equal to the correct answer when their absolute or relative error doesn't exceed 10−610^{-6}10−6.

Example 1

Input

Copy 1 2 0 0 1

1
2
0 0 1

Output

Copy 2.094395102393

2.094395102393

remarks :

In the picture above, the blue lines are the boundaries of the railgun spell. The red arc is the wall being destroyed.

#include<iostream>
#include<string>
#include<stdlib.h>
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef long long ll;

using namespace std;
const double PI=acos(-1.0);// accuracy 
int main()
{
	double n;
	cin>>n;
	for(int i=0;i<n;i++)
	 {
	  double r;
	  cin>>r;
	  double x,y,d,x1,y1,x2,y2;
	  double q1=0,q;
	  cin>>x>>y>>d;
     q=sqrt(x*x+y*y);
	  x1=q-d;
	  y1=y-d;
	  x2=q+d;
	  y2=y+d;
	  q1=(acos(x1/r)-acos(x2/r))*r;
	printf("%.8f\n",q1);
	}
    return 0;
}

G	Lexicographical Maximum

link ： Sign in — major IT Written interview preparation platform _ Cattle from
source ： Cattle from
 

Eibwen is a newbie in Python.

You might know that when you input a number in the command line, your Python program will receive a string containing that number instead of a number that can be used to calculate. This is an interesting feature that a newbie might not know.

Eibwen wants to find the maximum of some given numbers, so he writes a program to sort the list of the numbers and print the last element in the sorted list. However, as a newbie, Eibwen doesn't know the feature. He actually sorts the list of number strings in lexicographical order and prints the last string in the list.

Now Eibwen runs his program, inputs all the integers from 111 to nnn, and finds his program really slow. Could you help him find out the expected output of his program?

Input description :

The only line contains an integer nnn (1≤n≤1010000001\leq n\leq 10^{1000000}1≤n≤101000000) — the size of Eibwen's input.

Output description :

Print the expected output of Eibwen's program in a single line, which actually is the lexicographically maximum from 111 to nnn.

Example 1

Input

Copy 616

616

Output

Copy 99

99

#include<iostream>
#include<string>
#include<stdlib.h>
#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;
string a;
int main()
{
  while(cin>>a)
  {
   ll len=a.size();
   ll t,flag=1;
   for(ll i=0;i<len-1;i++)
	   {if(a[i]=='9')
       continue;
	   else
		   flag=0;
            break;
   }
   if(flag==1)
	   cout<<a<<endl;
   else
	   for(int i=0;i<len-1;i++)
	    {
	    cout<<9;
	   }
	   cout<<endl;
  }
   
    return 0;
}