Codeworks 5 questions per day (1700 average) - day 6

Pavel and barbecue

Topic translation

【 Title Description 】

Pavel In the barbecue .

share $n$ String barbecue in a row , Each of them is $n$ One of the positions .Pavel I hope every side of every roast can be roasted once in every position .

Pavel There's a full permutation $p$ And a long for $n$ Of 0/1 Sequence $b$.Pavel Each step will be located at $i$ The string of moves to $p_i$ It's about . meanwhile , If $b_i=1$, that Pavel This string will be reversed .

Unfortunately , Not every couple $p$ and $b$ All meet the requirements ,Pavel Want to know at least how many existing $p$ and $b$ In order to meet their goals . Note that the modified sequence should also meet the requirements .

Yi Zheng is like this $p$ and $b$ For all $n$ It's all there .

【 Input format 】

First line a positive integer $n$, The number of kebabs .

The second line $n$ A positive integer , respectively $p_1,p_2,\cdots ,p_n$.

The third line $n$ A positive integer , respectively $b_1,b_2,\cdots ,b_n$.

【 Output format 】

One positive integer per line , Indicates the minimum number of operations .

【 Data scale and agreement 】

$1\le p_i\le n\le 2\times 10^5$,$b_i\in \{0,1\}$

Title Description

Pavel cooks barbecue.

There are n skewers, they lay on a brazier in a row, each on one of n positions.

Pavel wants each skewer to be cooked some time in every of n positions in two directions: in the one it was directed originally and in the reversed direction.

Pavel has a plan: a permutation p and a sequence b_{1},b_{2},…,b_{n} , consisting of zeros and ones.

Each second Pavel move skewer on position i to position p_{i} , and if b_{i} equals 1 then he reverses it.

So he hope that every skewer will visit every position in both directions.

Unfortunately, not every pair of permutation p and sequence b suits Pavel.

What is the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements?

Note that after changing the permutation should remain a permutation as well.

There is no problem for Pavel, if some skewer visits some of the placements several times before he ends to cook.

In other words, a permutation p and a sequence b suit him if there is an integer k ( k>=2n ), so that after k seconds each skewer visits each of the 2n placements.

It can be shown that some suitable pair of permutation p and sequence b exists for any n .

Input format

The first line contain the integer n ( 1<=n<=2·10^{5} ) — the number of skewers.

The second line contains a sequence of integers p_{1},p_{2},…,p_{n} ( 1<=p_{i}<=n ) — the permutation, according to which Pavel wants to move the skewers.

The third line contains a sequence b_{1},b_{2},…,b_{n} consisting of zeros and ones, according to which Pavel wants to reverse the skewers.

Output format

Print single integer — the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements.

Examples #1

The sample input #1

4
4 3 2 1
0 1 1 1

Sample output #1

2

Examples #2

The sample input #2

3
2 3 1
0 0 0

Sample output #2

1

Tips

In the first example Pavel can change the permutation to 4,3,1,2 .

In the second example Pavel can change any element of b to 1 .

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
int n,a[N],s=0,k,ans=0;
bitset<N> sign;
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
    
		scanf("%d",&k);
		s+=k;
	}
	for(int i=1;i<=n;i++){
    
		if(!sign[i]){
    
			int p=a[i];
			sign[i]=1;
			while(!sign[p]){
    
				p=a[p];
			}
			if(p==i){
    
				p=a[i];
				while(!sign[p]){
    
					sign[p]=1;
					p=a[p];
				}
			}
		ans++;
		}
	}
	if(ans==1) ans=0;
	if(s%2) cout<<ans<<endl;
	else cout<<ans+1<<endl;
	return 0;
}

Alyona and mex

Topic translation

Do you have $m$ Intervals , It is required to construct a length of $n$ The sequence of makes this $m$ In two intervals $\text{mex}$ The smallest is the largest （$\text{mex}$ It is defined as the minimum natural number that does not appear in an interval ）.

Title Description

Alyona’s mother wants to present an array of n non-negative integers to Alyona.

The array should be special.

Alyona is a capricious girl so after she gets the array, she inspects m of its subarrays.

Subarray is a set of some subsequent elements of the array.

The i -th subarray is described with two integers l_{i} and r_{i} , and its elements are a[l_{i}],a[l_{i}+1],…,a[r_{i}] .

Alyona is going to find mex for each of the chosen subarrays.

Among these m mexes the girl is going to find the smallest.

She wants this minimum mex to be as large as possible.

You are to find an array a of n elements so that the minimum mex among those chosen by Alyona subarrays is as large as possible.

The mex of a set S is a minimum possible non-negative integer that is not in S .

Input format

The first line contains two integers n and m ( 1<=n,m<=10^{5} ).

The next m lines contain information about the subarrays chosen by Alyona.

The i -th of these lines contains two integers l_{i} and r_{i} ( 1<=l_{i}<=r_{i}<=n ), that describe the subarray a[l_{i}],a[l_{i}+1],…,a[r_{i}] .

Output format

In the first line print single integer — the maximum possible minimum mex.

In the second line print n integers — the array a .

All the elements in a should be between 0 and 10^{9} .

It is guaranteed that there is an optimal answer in which all the elements in a are between 0 and 10^{9} .

If there are multiple solutions, print any of them.

Examples #1

The sample input #1

5 3
1 3
2 5
4 5

Sample output #1

2
1 0 2 1 0

Examples #2

The sample input #2

4 2
1 4
2 4

Sample output #2

3
5 2 0 1

Tips

The first example: the mex of the subarray (1,3) is equal to 3 , the mex of the subarray (2,5) is equal to 3 , the mex of the subarray (4,5) is equal to 2 as well, thus the minumal mex among the subarrays chosen by Alyona is equal to 2 .

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
int n,m,mmin=INT_MAX,l,r;
int main(){
    
	cin>>n>>m;
	for(int i=1;i<=m;i++){
    
		cin>>l>>r;
		mmin=min(mmin,r-l+1);
	}
	cout<<mmin<<endl;
	for(int i=1;i<=n;i++){
    
		cout<<i%mmin<<" ";
	}
	return 0;
}

Masha and geometric depression

Topic translation

Give you an equal ratio sequence , The first item is b1, The common ratio is q, Now? Masha Write this series of equal numbers on the blackboard starting from the first item , Until the absolute value of a term in the sequence is greater than l, Given m It's an integer , If one of the items in the series of equal proportions is equal to this m It's an integer , Will not be written .
ask Masha How many numbers will you write ？ If she can write infinite numbers , Output inf
Be careful ： b1,q May be 0

Title Description

Masha really loves algebra.

On the last lesson, her strict teacher Dvastan gave she new exercise.

You are given geometric progression b defined by two integers b_{1} and q .

Remind that a geometric progression is a sequence of integers b_{1},b_{2},b_{3},… , where for each i>1 the respective term satisfies the condition b_{i}=b_{i-1}·q , where q is called the common ratio of the progression.

Progressions in Uzhlyandia are unusual: both b_{1} and $q$ can equal $0$ .

Also, Dvastan gave Masha $m$ “bad” integers $a_1,a_2,...,a_m$ , and an integer $l$ .

Masha writes all progression terms one by one onto the board (including repetitive) while condition |b_{i}|<=l is satisfied ( |x| means absolute value of x ).

There is an exception: if a term equals one of the “bad” integers, Masha skips it (doesn’t write onto the board) and moves forward to the next term.

But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board.

In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print “inf” in case she needs to write infinitely many integers.

Input format

The first line of input contains four integers b_{1} , q , l , m (- 10^{{9}<=b_{1},q<=10}{9} , 1<=l<=10^{9} , 1<=m<=10^{5} ) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of “bad” integers, respectively.

The second line contains m distinct integers a_{1},a_{2},…,a_{m} (- 10^{{9}<=a_{i}<=10}{9}) — numbers that will never be written on the board.

Output format

Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or “inf” (without quotes) otherwise.

Examples #1

The sample input #1

3 2 30 4
6 14 25 48

Sample output #1

3

Examples #2

The sample input #2

123 1 2143435 4
123 11 -5453 141245

Sample output #2

0

Examples #3

The sample input #3

123 1 2143435 4
54343 -13 6 124

Sample output #3

inf

Tips

In the first sample case, Masha will write integers 3,12,24 .

Progression term 6 will be skipped because it is a “bad” integer.

Terms bigger than 24 won’t be written because they exceed l by absolute value.

In the second case, Masha won’t write any number because all terms are equal 123 and this is a “bad” integer.

In the third case, Masha will write infinitely integers 123 .

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
ll b1,q,l,m,k,ss=0,p=0;
set<ll> s;
int main(){
    
	cin>>b1>>q>>l>>m;
	for(int i=1;i<=m;i++){
    
		scanf("%lld",&k);
		s.insert(k);
	}
	ll b2=b1;
	while(abs(b2)<=l){
    
		p++;
		if(s.find(b2)==s.end()){
    
			ss++;
		}
		b2*=q;
		if(p==1000000){
    
			if(ss!=0&&ss!=1){
    
				ss=-1;
			}
			break;
		}
	}
	if(ss==-1) puts("inf");
	else printf("%lld",ss);
	return 0;
}

Minimal string

Topic translation

Give a string , Stack from front to back , Output the stack sequence with the smallest dictionary order

Title Description

Petya recieved a gift of a string $s$ with length up to $10^5$ characters for his birthday.

He took two more empty strings $t$ and $u$ and decided to play a game. This game has two possible moves:

• Extract the first character of $s$ and append $t$ with this character.
• Extract the last character of $t$ and append $u$ with this character.

Petya wants to get strings $s$ and $t$ empty and string $u$ lexicographically minimal.

You should write a program that will help Petya win the game.

Input format

First line contains non-empty string $s$ ( $1<=|s|<=10^5$ ), consisting of lowercase English letters.

Output format

Print resulting string $u$ .

Examples #1

The sample input #1

cab

Sample output #1

abc

Examples #2

The sample input #2

acdb

Sample output #2

abdc

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
char b[N];
string a;
stack<char> s;
int main(){
    
	cin>>a;
	int n=a.size();
	b[n-1]=a[n-1];
	for(int i=n-2;i>=0;i--){
    
		if(a[i]<b[i+1]) b[i]=a[i];
		else b[i]=b[i+1];
	}
	for(int i=0;i<n-1;i++){
    
		s.push(a[i]);
		while(!s.empty()&&s.top()<=b[i+1]){
    
			cout<<s.top();
			s.pop();
		}
	}
	s.push(a[n-1]);
	while(!s.empty()){
    
		cout<<s.top();
		s.pop();
	}
	return 0;
}

Dasha and Very Difficult Problem

Topic translation

The main idea of the topic

 existing a[i],b[i] Two arrays (l<=a[i]<=b[i]<=r), We define p,c Two arrays , among c[i]=b[i]-a[i],p An array is c The relative size of the array , Here you are a and p Array , Put any group that meets b Find out the array . If there is no satisfying , The output ‘-1’( No quotes ).

Input format

 The first line contains 3 It's an integer n,l,r
 among (1<=n<=10^5),(1<=l<=r<=10^9)
 Second behavior n individual a[1],a[2],...,a[n],
 Third act n individual p[1],p[2],...,p[n]
a,p The significance of has been described in the main idea of the topic 

Output format

 A line of qualified b Array ,
 If there is no consistent situation , The output '-1'( No quotes )

Title Description

Dasha logged into the system and began to solve problems.

One of them is as follows:

Given two sequences $a$ and $b$ of length $n$ each you need to write a sequence $c$ of length $n$ , the $i$ -th element of which is calculated as follows: $c_i=b_i-a_i$ .

About sequences $a$ and $b$ we know that their elements are in the range from $l$ to $r$ .

More formally, elements satisfy the following conditions: $l<=a_i<=r$ and $l<=b_i<=r$ .

About sequence $c$ we know that all its elements are distinct.

Dasha wrote a solution to that problem quickly, but checking her work on the standard test was not so easy.

Due to an error in the test system only the sequence $a$ and the compressed sequence of the sequence $c$ were known from that test.

Let’s give the definition to a compressed sequence.

A compressed sequence of sequence $c$ of length $n$ is a sequence $p$ of length $n$ , so that $p_i$ equals to the number of integers which are less than or equal to $c_i$ in the sequence $c$ .

For example, for the sequence $c=[250,200,300,100,50]$ the compressed sequence will be $p=[4,3,5,2,1]$ .

Pay attention that in $c$ all integers are distinct.

Consequently, the compressed sequence contains all integers from $1$ to$n$ inclusively.

Help Dasha to find any sequence $b$ for which the calculated compressed sequence of sequence $c$ is correct.

Input format

The first line contains three integers $n$ , $l$ , $r$$(1<=n<=10^5,1<=l<=r<=10^9)$ — the length of the sequence and boundaries of the segment where the elements of sequences $a$ and $b$ are.

The next line contains $n$ integers $a_{1},a_{2},…,a_{n} $ $ (l<=a_{i}<=r)$ — the elements of the sequence $a$ .

The next line contains $n$ distinct integers $p_1,p_2,...,p_n$$(1<=p_i<=n)$ — the compressed sequence of the sequence $c$ .

Output format

If there is no the suitable sequence $b$ , then in the only line print “-1”.

Otherwise, in the only line print $n$ integers — the elements of any suitable sequence $b$ .

Examples #1

The sample input #1

5 1 5
1 1 1 1 1
3 1 5 4 2

Sample output #1

3 1 5 4 2

Examples #2

The sample input #2

4 2 9
3 4 8 9
3 2 1 4

Sample output #2

2 2 2 9

Examples #3

The sample input #3

6 1 5
1 1 1 1 1 1
2 3 5 4 1 6

Sample output #3

-1

Tips

Sequence $b$ which was found in the second sample is suitable, because calculated sequence $c=[2-3,2-4,2-8,9-9]=[-1,-2,-6,0]$(note that$c_i=b_i-a_i$ ) has compressed sequence equals to $p=[3,2,1,4]$ .

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
ll n,l,r,a[N],p[N],b[N],mmin=INT_MAX,mmax=0;
set<ll> s;
int main(){
    
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n;i++){
    
		scanf("%lld",&p[i]);
	}
	for(int i=1;i<=n;i++){
    
		b[i]=a[i]+p[i];
		mmin=min(mmin,b[i]);
		mmax=max(mmax,b[i]);
	}
	if(mmax-mmin>r-l){
    
		puts("-1");
	}
	else{
    
		ll u=l-mmin;
		for(int i=1;i<=n;i++){
    
			printf("%lld ",b[i]+u);
		}
	}
	return 0;
}