Codeworks 5 questions per day (1700 for each) - the third day

Number of Ways

Topic translation

Title Description
You get an array a, contain n A digital a[1],a[2],a[3],…,a[n].

Now you have to find a way to divide it into three parts , Make the sum of all the numbers in each share equal .

In short , You need to find a number pair (i,j), bring

input data

The first line is an integer n(1<=n<=500000), Indicates how many numbers are in the sequence .

The next line has n Number , respectively a[1],a[2],a[3],…,a[n].

Output data

One line, one integer , That satisfies the condition (i,j) Total of .

Title Description

You’ve got array a[1],a[2],…,a[n] , consisting of n integers.

Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.

More formally, you need to find the number of such pairs of indices i,j (2<=i<=j<=n-1) , that .

Input format

The first line contains integer n (1<=n<=5·10^{5}) , showing how many numbers are in the array.

The second line contains n integers a[1] , a[2] , …, a[n] (|a[i]|<=10^{9}) — the elements of array a .

Output format

Print a single integer — the number of ways to split the array into three parts with the same sum.

Examples #1

The sample input #1

5
1 2 3 0 3

Sample output #1

2

Examples #2

The sample input #2

4
0 1 -1 0

Sample output #2

1

Examples #3

The sample input #3

2
4 1

Sample output #3

0

#include<bits/stdc++.h>
using namespace std; 
const int N=1e6+5;
typedef long long ll;
ll n,k=0,s=0,a[N],kk;
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&kk);	
		a[i]=a[i-1]+kk;
	}
	if(a[n]%3!=0){
    
		puts("0");
		return 0;
	}
	for(int i=1;i<=n;i++){
    
		if(i>1&&i<n&&a[i]==a[n]*2/3){
    
			s+=k;
		}
		if(a[i]==a[n]/3){
    
			k++;
		}
	}
	cout<<s<<endl;
	return 0;
}

No to Palindromes!

Topic translation

Give you a length of N String of , Only the first p English letters , Ensure that the input is a subsequence without a length of 2 Or the length is greater than 2 The palindrome of .

Let you find the first one larger than the original string dictionary order : There is no subsequence of length 2 Or the length is greater than 2 The solution of palindrome string of . If it doesn't exist , Output NO.

Title Description

Paul hates palindromes.

He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and s doesn’t contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string s of length n .

Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.

Input format

The first line contains two space-separated integers: n and p ( 1<=n<=1000 ; 1<=p<=26 ).

The second line contains string s , consisting of n small English letters. It is guaranteed that the string is tolerable (according to the above definition).

Output format

If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print “NO” (without the quotes).

Examples #1

The sample input #1

3 3
cba

Sample output #1

NO

Examples #2

The sample input #2

3 4
cba

Sample output #2

cbd

Examples #3

The sample input #3

4 4
abcd

Sample output #3

abda

Tips

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i , such that s_{1}=t_{1} , …, s_{i}=t_{i} , s_{i+1}>t_{i+1} .

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+5;
typedef long long ll;
int n,p,k,u;
char s[N];
bool check(int v){
    
    if(v>=1&&s[v]==s[v-1])
        return false;
    if(v>=2&&s[v]==s[v-2])
        return false;
    return true;
}
int main(){
    
	cin>>n>>p;
	cin>>s;
	k=n-1;
	while(1){
    
		if(k>=n){
    
			cout<<s<<endl;
			return 0;
		}
		if(k<0){
    
			puts("NO");
			return 0;
		}
		if(s[k]-'a'==p-1){
    
			s[k]='a'-1;
			k--;
		}
		else{
    
			u=(s[k]-'a'+1)%p;
			s[k]='a'+u;
			if(check(k)) k++;
		}
	}
	puts("NO");
	return 0;
}

Bits

Topic translation

- n Group inquiry , Give an interval at a time l, r, You need to output the binary representation in this interval 1 The largest number of 

-  If there are multiple answers , The one with the smallest output 

- (n \leq10^4, 0\leq l, r \leq10^{18})

effect

• $n$ Group inquiry , Give an interval at a time $l,r$, You need to output the binary representation in this interval 1 The largest number of

• If there are multiple answers , The one with the smallest output

• $(n\le 10^4,0\le l,r\le 10^{18})$

Title Description

Let’s denote as the number of bits set (‘1’ bits) in the binary representation of the non-negative integer x .

You are given multiple queries consisting of pairs of integers l and r .

For each query, find the x , such that l<=x<=r , and is maximum possible. If there are multiple such numbers find the smallest of them.

Input format

Let’s denote as the number of bits set (‘1’ bits) in the binary representation of the non-negative integer x .

You are given multiple queries consisting of pairs of integers l and r .

For each query, find the x , such that l<=x<=r , and is maximum possible. If there are multiple such numbers find the smallest of them.

Output format

For each query print the answer in a separate line.

Examples #1

The sample input #1

3
1 2
2 4
1 10

Sample output #1

1
3
7

Tips

Let’s denote as the number of bits set (‘1’ bits) in the binary representation of the non-negative integer x .

You are given multiple queries consisting of pairs of integers l and r .

For each query, find the x , such that $ l<=x<=r , and is maximum possible.

If there are multiple such numbers find the smallest of them.

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+5;
typedef long long ll;
ll t,l,r,i;
int main(){
    
	cin>>t;
	while(t--){
    
		scanf("%lld%lld",&l,&r);
		for(i=1;(l|i)<=r;i<<=1) l|=i;
		printf("%lld\n",l);
	}
	return 0;
}

Platforms

Topic translation

Title Description ： Given on a coordinate axis n A board , The space occupied by each board is [(k-1)m,(k-1)m+l]（l<m）, A frog from the origin 0 Take off , Each jump d Far away , Ask where the frog will fall in the end （ Fall on the board and end the jump ）
Input ： Four integers in a row n,d,m,l
Output ： An integer , That is, the last landing point of the frog
1<=n,d,m,l<=10^6
l<m

Title Description

In one one-dimensional world there are n platforms.

Platform with index k (platforms are numbered from 1) is a segment with coordinates [(k-1)m,(k-1)m+l] , and l<m .

Grasshopper Bob starts to jump along the platforms from point 0 , with each jump he moves exactly d units right.

Find out the coordinate of the point, where Bob will fall down.

The grasshopper falls down, if he finds himself not on the platform, but if he finds himself on the edge of the platform, he doesn’t fall down.

Input format

The first input line contains 4 integer numbers n , d , m , l ( 1<=n,d,m,l<=10^{6},l<m ) — respectively: amount of platforms, length of the grasshopper Bob’s jump, and numbers m and l needed to find coordinates of the k -th platform: [(k-1)m,(k-1)m+l] .

Output format

Output the coordinates of the point, where the grosshopper will fall down.

Don’t forget that if Bob finds himself on the platform edge, he doesn’t fall down.

Examples #1

The sample input #1

2 2 5 3

Sample output #1

4

Examples #2

The sample input #2

5 4 11 8

Sample output #2

20

#include<iostream>
#include<algorithm>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,d,m,l,s;
int main(){
    
	cin>>n>>d>>m>>l;
	for(ll i=1;i<=n;i++){
    
		if(s<(i-1)*m) break;
		while(s<=(i-1)*m+l){
    
			s=((i-1)*m+l)/d*d+d;
		}
	}
	cout<<s<<endl;
    return 0;
}