Codeworks 5 questions per day (average 1500) - day 23

Tile Painting

Topic translation

Brief introduction

There is one by $n$ The length of the tile is $n$ Way .

For two tiles $i,j$, If $ |i-j| > 1 $ And $n$$\text{mod}$$|i-j|=0$ , Then their colors must be the same .

Find out how many tiles of different colors can be used at most , And meet the above requirements .

Input format

One positive integer per line $n(1\le n\le 10^{12})$.

Output format

Output a positive integer , Indicates the number of tiles of different colors that can be used at most , Make it meet the above requirements .

Title Description

Ujan has been lazy lately, but now has decided to bring his yard to good shape.

First, he decided to paint the path from his house to the gate.

The path consists of $n$ consecutive tiles, numbered from $1$ to $n$ .

Ujan will paint each tile in some color.

He will consider the path aesthetic if for any two different tiles with numbers $i$ and $j$ , such that $|j-i|$ is a divisor of $n$ greater than $1$ , they have the same color.

Formally, the colors of two tiles with numbers $i$ and $j$ should be the same if $|i-j|>1$ and $n\mathrm{mod}|i-j|=0$ (where $x\mathrm{mod}y$ is the remainder when dividing $x$ by $y$ ).

Ujan wants to brighten up space. What is the maximum number of different colors that Ujan can use, so that the path is aesthetic?

Input format

The first line of input contains a single integer $n$ ( $1\le n\le 10^{12}$ ), the length of the path.

Output format

Output a single integer, the maximum possible number of colors that the path can be painted in.

Examples #1

The sample input #1

4

Sample output #1

2

Examples #2

The sample input #2

5

Sample output #2

5

Tips

In the first sample, two colors is the maximum number.

Tiles $1$ and $3$ should have the same color since $4\mathrm{mod}|3-1|=0$ .

Also, tiles $2$ and $4$ should have the same color since $4\mathrm{mod}|4-2|=0$ .

In the second sample, all five colors can be used.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll n;
vector<ll>a;
int main(){
    
	cin>>n;
	for(ll i=2;i*i<=n;i++)
        if(n%i==0)
        {
    
            a.push_back(i);
            while(n%i==0) n/=i;
        }
    if(n!=1) a.push_back(n);
    sort(a.begin(),a.end());
    if(a.size()==1) printf("%lld\n",a.front());
    else if(a.empty()) printf("%lld\n",n);
    else puts("1");
 return 0;
}

Boxers

Topic translation

Title Description ：

Yes $n$ A boxer , The first $i$ The weight of a boxer is $a_i$. Each of them can change their weight by no more than 1（ Weight cannot equal zero , in other words , It must remain positive ）., Weight is always an integer .
You need to choose the largest boxing team according to the number of people , Make the weight of each boxer in the team unique .
Write a program , For a given weight $a_i$, Find out the maximum possible number of boxers in the team . After some changes , The weight of all boxers does not exceed 150001.

Input format ：

The first line contains an integer $n$($1\le n\le 150000$), That is, the number of boxers . The second line contains $n$ It's an integer $a_1$,$a_2$,…,$a_n$($1\le ai\le 150000$), among $a_i$ For the first time $i$ Weight of a boxer .

Output format ：

Output the maximum possible number of people in the team .

Title Description

There are $n$ boxers, the weight of the $i$ -th boxer is $a_i$ .

Each of them can change the weight by no more than $1$ before the competition (the weight cannot become equal to zero, that is, it must remain positive). Weight is always an integer number.

It is necessary to choose the largest boxing team in terms of the number of people, that all the boxers’ weights in the team are different (i.e. unique).

Write a program that for given current values ​ $a_i$ will find the maximum possible number of boxers in a team.

It is possible that after some change the weight of some boxer is $150001$ (but no more).

Input format

The first line contains an integer $n$ ( $1\le n\le 150000$ ) — the number of boxers.

The next line contains $n$ integers $a_1,a_2,\dots ,a_n$ , where $a_i$ ( $1\le a_i\le 150000$ ) is the weight of the $i$ -th boxer.

Output format

Print a single integer — the maximum possible number of people in a team.

Examples #1

The sample input #1

4
3 2 4 1

Sample output #1

4

Examples #2

The sample input #2

6
1 1 1 4 4 4

Sample output #2

5

Tips

In the first example, boxers should not change their weights — you can just make a team out of all of them.

In the second example, one boxer with a weight of $1$ can be increased by one (get the weight of $2$ ), one boxer with a weight of $4$ can be reduced by one, and the other can be increased by one (resulting the boxers with a weight of $3$ and $5$ , respectively).

Thus, you can get a team consisting of boxers with weights of $5,4,3,2,1$ .

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,k,a[N],mmax=0,s=0;
int main(){
    
	cin>>n;
	for(ll i=1;i<=n;i++){
    
		scanf("%d",&k);
		a[k]++;
		mmax=max(mmax,k);
	}
	for(int i=1;i<=mmax+1;i++){
    
		if(a[i-1]) a[i-1]--,s++;
		else if(a[i]) a[i]--,s++;
		else if(a[i+1]) a[i+1]--,s++;
	}
	cout<<s<<endl;
 return 0;
}

Zero Array

Topic translation

Given a sequence of Numbers $n(2\le n\le 10^5)$, You can operate on the sequence any time . Operation is defined as ：

• Select two numbers in the sequence $a_i$,$a_j$$(i\ne j,1\le a_i,a_j\le 10^9)$, Subtract their values respectively $1$.

Find the... Of the sequence after several operations $n$ Is it possible that all the numbers are $0$. If possible, output $YES$, Otherwise output $NO$.

Title Description

You are given an array $a_1,a_2,\dots ,a_n$ .

In one operation you can choose two elements $a_i$ and $a_j$ ( $i\ne j$ ) and decrease each of them by one.

You need to check whether it is possible to make all the elements equal to zero or not.

Input format

The first line contains a single integer $n$ ( $2\le n\le 10^5$ ) — the size of the array.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 10^9$ ) — the elements of the array.

Output format

Print “YES” if it is possible to make all elements zero, otherwise print “NO”.

Examples #1

The sample input #1

4
1 1 2 2

Sample output #1

YES

Examples #2

The sample input #2

6
1 2 3 4 5 6

Sample output #2

NO

Tips

In the first example, you can make all elements equal to zero in $3$ operations:

• Decrease $a_1$ and $a_2$ ,
• Decrease $a_3$ and $a_4$ ,
• Decrease $a_3$ and $a_4$

In the second example, one can show that it is impossible to make all elements equal to zero.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll n,k,s=0,mmax=0;
int main(){
    
	cin>>n;
	for(ll i=1;i<=n;i++){
    
		scanf("%lld",&k);
		s+=k;
		mmax=max(mmax,k);
	}
	if(s%2==1||s<2*mmax) puts("NO");
	else puts("YES");
 return 0;
}

RGB Substring (easy version)

Topic translation

The only difference is the range of data .
Here you are. $q$ Group inquiry （$1\le q\le 2000$）
Each group will first give you one $n$ And a $k$（$1\le k\le n\le 2000$）
The next line is a string $s$（ Data assurance $s$ Only capital letters $R$、$G$、$B$ form , Input data to ensure all $s$ Length and $ \le 2000$）\; Now\; I\; ask\; you\; how\; many\; times\; to\; modify\; at\; least$s$Letters\; in\; （\; Only\; one\; letter\; can\; be\; modified\; at\; a\; time\; ）,\; Can\; make$s$A\; substring\; of\; is\; a\; string$RGBRGBRGB…$The\; string\; of\; ,\; At\; the\; same\; time,\; the\; length\; of\; the\; substring$ \ge k$.

Title Description

The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is ‘R’, ‘G’ or ‘B’.

You are also given an integer $k$ .

Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$ , and is also a substring of the infinite string “RGBRGBRGB …”.

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1=b_i$ , $a_2=b_{i+1}$ , $a_3=b_{i+2}$ , …, $a_{|a|}=b_{i+|a|-1}$ .

For example, strings “GBRG”, “B”, “BR” are substrings of the infinite string “RGBRGBRGB …” while “GR”, “RGR” and “GGG” are not.

You have to answer $q$ independent queries.

Input format

The first line of the input contains one integer $q$ ( $1\le q\le 2000$ ) — the number of queries.

Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ( $1\le k\le n\le 2000$ ) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters ‘R’, ‘G’ and ‘B’.

It is guaranteed that the sum of $n$ over all queries does not exceed $2000$ ( $\sum n\le 2000$ ).

Output format

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string “RGBRGBRGB …”.

Examples #1

The sample input #1

3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

Sample output #1

1
0
3

Tips

In the first example, you can change the first character to ‘R’ and obtain the substring “RG”, or change the second character to ‘R’ and obtain “BR”, or change the third, fourth or fifth character to ‘B’ and obtain “GB”.

In the second example, the substring is “BRG”.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,k,q;
int main(){
    
	cin>>q;
	while(q--){
     
	string s;
		scanf("%d%d",&n,&k);
		cin>>s;
		int w=k,mmin=INT_MAX,t=0,ss=0;
		while(w<=n){
    
			for(int j=t;j<w;j++){
    
				if(j%3==0&&s[j]!='R') ss++;
				if(j%3==1&&s[j]!='G') ss++;
				if(j%3==2&&s[j]!='B') ss++;
			}
			mmin=min(mmin,ss),ss=0;
			for(int j=t;j<w;j++){
    
				if(j%3==0&&s[j]!='G') ss++;
				if(j%3==1&&s[j]!='B') ss++;
				if(j%3==2&&s[j]!='R') ss++;
			}
			mmin=min(mmin,ss),ss=0;
			for(int j=t;j<w;j++){
    
				if(j%3==0&&s[j]!='B') ss++;
				if(j%3==1&&s[j]!='R') ss++;
				if(j%3==2&&s[j]!='G') ss++;
			}
			mmin=min(mmin,ss),ss=0;
			t++,w++;
		}
		cout<<mmin<<endl;
	}
 return 0;
}

Robot Breakout

Topic translation

Topic translation

Yes $n$ A robot is on a plane , The first $i$ The position of the robot is $(X_i,Y_i)$.

In design , The first $i$ Operations that a robot can perform ：

1. Location slave $(X_i,Y_i)$ Turn into $(X_i-1,Y_i)$.

2. Location slave $(X_i,Y_i)$ Turn into $(X_i,Y_i+1)$.

3. Location slave $(X_i,Y_i)$ Turn into $(X_i+1,Y_i)$.

4. Location slave $(X_i,Y_i)$ Turn into $(X_i,Y_i-1)$.

But the design has defects , Some robots may not be able to perform some of the above operations .

You need to find a point $(A,H)$, bring $n$ Every robot can reach $(A,H)$ . Be careful , The initial position is $(A,H)$ It's also arrival , And for $A,H$ The scope of is limited —— $-10^5\le A,H\le 10^5$.

Input format

There are several groups of data in this question .

The first line of the entire input , It's an integer $q(1\le q\le 10^5)$ , Represents the number of data groups .

For each set of data , The first line has an integer $n$ , Indicates the number of robots .

Next $n$ That's ok , Each row $6$ It's an integer $X_i,Y_i,f_1,f_2,f_3,f_4(-10^5\le X_i,Y_i\le 10^5,0\le f_1,f_2,f_3,f_4\le 1)$.$X_i,Y_i$ Represents the coordinates of the robot ,$f_1,f_2,f_3,f_4$ Separate indication control $i$ The above of robots $4$ Whether the functions are available . If $f_{ahak}=1(1\le ahak\le 4)$, It means No $ahak$ Functions are available , Otherwise, it is not available .

Output format

For each set of data , If there is no solution , Output $0$.

otherwise , Output $A,H$, It means that all robots can reach $(A,H)$.

Title Description

$n$ robots have escaped from your laboratory!

You have to find them as soon as possible, because these robots are experimental, and their behavior is not tested yet, so they may be really dangerous!

Fortunately, even though your robots have escaped, you still have some control over them.

First of all, you know the location of each robot: the world you live in can be modeled as an infinite coordinate plane, and the $i$ -th robot is currently located at the point having coordinates ( $x_i$ , $y_i$ ).

Furthermore, you may send exactly one command to all of the robots.

The command should contain two integer numbers $X$ and $Y$ , and when each robot receives this command, it starts moving towards the point having coordinates ( $X$ , $Y$ ).

The robot stops its movement in two cases:

• either it reaches ( $X$ , $Y$ );
• or it cannot get any closer to ( $X$ , $Y$ ).

Normally, all robots should be able to get from any point of the coordinate plane to any other point.

Each robot usually can perform four actions to move. Let’s denote the current coordinates of the robot as ( $x_c$ , $y_c$ ).

Then the movement system allows it to move to any of the four adjacent points:

1. the first action allows it to move from ( $x_c$ , $y_c$ ) to ( $x_c-1$ , $y_c$ );
2. the second action allows it to move from ( $x_c$ , $y_c$ ) to ( $x_c$ , $y_c+1$ );
3. the third action allows it to move from ( $x_c$ , $y_c$ ) to ( $x_c+1$ , $y_c$ );
4. the fourth action allows it to move from ( $x_c$ , $y_c$ ) to ( $x_c$ , $y_c-1$ ).

Unfortunately, it seems that some movement systems of some robots are malfunctioning.

For each robot you know which actions it can perform, and which it cannot perform.

You want to send a command so all robots gather at the same point.

To do so, you have to choose a pair of integer numbers $X$ and $Y$ so that each robot can reach the point ( $X$ , $Y$ ). Is it possible to find such a point?

Input format

The first line contains one integer $q$ ( $1\le q\le 10^5$ ) — the number of queries.

Then $q$ queries follow.

Each query begins with one line containing one integer $n$ ( $1\le n\le 10^5$ ) — the number of robots in the query.

Then $n$ lines follow, the $i$ -th of these lines describes the $i$ -th robot in the current query: it contains six integer numbers $x_i$ , $y_i$ , $f_{i,1}$ , $f_{i,2}$ , $f_{i,3}$ and $f_{i,4}$ ( $-10^5\le x_i,y_i\le 10^5$ , $0 \le f_{i, j} \le 1 $ ).

The first two numbers describe the initial location of the $i$ -th robot, and the following four numbers describe which actions the $i$ -th robot can use to move ( $f_{i,j}=1$ if the $i$ -th robot can use the $j$ -th action, and $f_{i,j}=0$ if it cannot use the $j$ -th action).

It is guaranteed that the total number of robots over all queries does not exceed $10^5$ .

Output format

You should answer each query independently, in the order these queries appear in the input.

To answer a query, you should do one of the following:

• if it is impossible to find a point that is reachable by all $n$ robots, print one number $0$ on a separate line;
• if it is possible to find a point that is reachable by all $n$ robots, print three space-separated integers on the same line: $1$$X$$Y$ , where $X$ and $Y$ are the coordinates of the point reachable by all $n$ robots.

Both $X$ and $Y$ should not exceed $10^5$ by absolute value; it is guaranteed that if there exists at least one point reachable by all robots, then at least one of such points has both coordinates not exceeding $10^5$ by absolute value.

Examples #1

The sample input #1

4
2
-1 -2 0 0 0 0
-1 -2 0 0 0 0
3
1 5 1 1 1 1
2 5 0 1 0 1
3 5 1 0 0 0
2
1337 1337 0 1 1 1
1336 1337 1 1 0 1
1
3 5 1 1 1 1

Sample output #1

1 -1 -2
1 2 5
0
1 -100000 -100000

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
int n,q;
int main(){
    
	cin>>q;
	while(q--){
     
		scanf("%d",&n);
		int minx=-1e5,maxx=1e5,miny=-1e5,maxy=1e5;
		for(int i=1;i<=n;i++){
    
			int x,y,a,b,c,d;
			scanf("%d%d",&x,&y);
			scanf("%d%d%d%d",&a,&b,&c,&d);
			if(!a) minx=max(minx,x);
			if(!c) maxx=min(maxx,x);
			if(!b) maxy=min(maxy,y);
			if(!d) miny=max(miny,y);
 		}
 		if(minx>maxx||miny>maxy) puts("0");
 		else printf("1 %d %d\n",minx,miny);
	}
 return 0;
}