# CodeForces Round #547 (Div3)

## A. Game 23

time limit per test1 second memory limit per test256 megabytes

Polycarp plays “Game 23”. Initially he has a number 𝑛n and his goal is to transform it to 𝑚m. In one move, he can multiply 𝑛n by 22 or multiply 𝑛n by 33. He can perform any number of moves.

Print the number of moves needed to transform 𝑛n to 𝑚m. Print -1 if it is impossible to do so.

It is easy to prove that any way to transform 𝑛n to 𝑚m contains the same number of moves (i.e. number of moves doesn’t depend on the way of transformation).Input

The only line of the input contains two integers 𝑛n and 𝑚m (1≤𝑛≤𝑚≤5⋅1081≤n≤m≤5⋅108).Output

Print the number of moves to transform 𝑛n to 𝑚m, or -1 if there is no solution.

Examples

input

120 51840


output

7


input

42 42


output

0


input

48 72


output

-1


Note

In the first example, the possible sequence of moves is: 120→240→720→1440→4320→12960→25920→51840.120→240→720→1440→4320→12960→25920→51840. The are 77 steps in total.

In the second example, no moves are needed. Thus, the answer is 00.

In the third example, it is impossible to transform 4848 to 7272.

## 签到题水过，但是我还是WA了一发

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(3e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n,m;sc2(n,m);
if(m%n){
printf("-1\n");
return 0;
}
m/=n;
int ans=0;
while(m%2==0){
m/=2;
ans++;
}
while(m%3==0){
m/=3;
ans++;
}
if(m!=1){
printf("-1\n");
return 0;
}
printf("%d\n",ans);
return 0;
}


## B. Maximal Continuous Rest

time limit per test2 seconds memory limit per test256 megabytes

Each day in Berland consists of 𝑛n hours. Polycarp likes time management. That’s why he has a fixed schedule for each day — it is a sequence 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (each 𝑎𝑖ai is either 00 or 11), where 𝑎𝑖=0ai=0 if Polycarp works during the 𝑖i-th hour of the day and 𝑎𝑖=1ai=1 if Polycarp rests during the 𝑖i-th hour of the day.

Days go one after another endlessly and Polycarp uses the same schedule for each day.

What is the maximal number of continuous hours during which Polycarp rests? It is guaranteed that there is at least one working hour in a day.Input

The first line contains 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — number of hours per day.

The second line contains 𝑛n integer numbers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖≤10≤ai≤1), where 𝑎𝑖=0ai=0 if the 𝑖i-th hour in a day is working and 𝑎𝑖=1ai=1 if the 𝑖i-th hour is resting. It is guaranteed that 𝑎𝑖=0ai=0 for at least one 𝑖i.Output

Print the maximal number of continuous hours during which Polycarp rests. Remember that you should consider that days go one after another endlessly and Polycarp uses the same schedule for each day.
Examples
input

5
1 0 1 0 1


output

2


input

6
0 1 0 1 1 0


output

2


input

7
1 0 1 1 1 0 1


output

3


input

3
0 0 0


output

0


Note

In the first example, the maximal rest starts in last hour and goes to the first hour of the next day.

In the second example, Polycarp has maximal rest from the 44-th to the 55-th hour.

In the third example, Polycarp has maximal rest from the 33-rd to the 55-th hour.

In the fourth example, Polycarp has no rest at all.

## 注意特判一下最后一天的休息时间就好了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n;sc(n);
int a[maxn];
int fir=0,firlen=0,pre=-1,maxx=0,cnt=0;
sc(pre);
if(pre) maxx=1,cnt=1,fir=1,firlen=1;
for(int i=1;i<n;++i){
int x;sc(x);
if(x){
cnt++;
if(fir){
firlen++;
}
if(i==n-1){
cnt+=firlen;
maxx=max(maxx,cnt);
}
}
else{
if(fir){
fir=0;
firlen=cnt;
}
maxx=max(maxx,cnt);
cnt=0;
}
}
printf("%d\n",maxx);
return 0;
}


## C. Polycarp Restores Permutation

time limit per test2 seconds memory limit per test256 megabytes

An array of integers 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn is called a permutation if it contains each number from 11 to 𝑛n exactly once. For example, the following arrays are permutations: [3,1,2][3,1,2], , [1,2,3,4,5][1,2,3,4,5] and [4,3,1,2][4,3,1,2]. The following arrays are not permutations: , [1,1][1,1], [2,3,4][2,3,4].

Polycarp invented a really cool permutation 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn of length 𝑛n. It is very disappointing, but he forgot this permutation. He only remembers the array 𝑞1,𝑞2,…,𝑞𝑛−1q1,q2,…,qn−1 of length 𝑛−1n−1, where 𝑞𝑖=𝑝𝑖+1−𝑝𝑖qi=pi+1−pi.

Given 𝑛n and 𝑞=𝑞1,𝑞2,…,𝑞𝑛−1q=q1,q2,…,qn−1, help Polycarp restore the invented permutation.Input

The first line contains the integer 𝑛n (2≤𝑛≤2⋅1052≤n≤2⋅105) — the length of the permutation to restore. The second line contains 𝑛−1n−1 integers 𝑞1,𝑞2,…,𝑞𝑛−1q1,q2,…,qn−1 (−𝑛<𝑞𝑖<𝑛−n<qi<n).Output

Print the integer -1 if there is no such permutation of length 𝑛n which corresponds to the given array 𝑞q. Otherwise, if it exists, print 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn. Print any such permutation if there are many of them.
Examples
input

3
-2 1


output

3 1 2

input

5
1 1 1 1


output

1 2 3 4 5

input

4
-1 2 2


output

-1

## 令第一个数为t，则之后第二到n个数即为t+输入的n-1个数的前缀和。比赛的时候因为n没有开long long WA了五发，真难受

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
ll n;scanf("%lld",&n);
int a[maxn];
ll tot=0;
a=0;
for(int i=1;i<n;++i){
sc(a[i]);
a[i]+=a[i-1];
tot+=a[i];
}
ll tem=n*(n+1)/2;
tem-=tot;
tem/=n;
set<int> s;
int flag=0;
for(int i=0;i<n;++i){
s.insert(a[i]+tem);
if(a[i]+tem>n||a[i]+tem<1){
flag=1;
break;
}
}
if(s.size()!=n) flag=1;
if(flag)printf("-1\n");
else{
for(int i=0;i<n;++i){
printf(i==0?"%lld":" %lld",tem+a[i]);
}
}
return 0;
}


## D. Colored Boots

time limit per test2 seconds memory limit per test256 megabytes

There are 𝑛n left boots and 𝑛n right boots. Each boot has a color which is denoted as a lowercase Latin letter or a question mark (‘?’). Thus, you are given two strings 𝑙l and 𝑟r, both of length 𝑛n. The character 𝑙𝑖li stands for the color of the 𝑖i-th left boot and the character 𝑟𝑖ri stands for the color of the 𝑖i-th right boot.

A lowercase Latin letter denotes a specific color, but the question mark (‘?’) denotes an indefinite color. Two specific colors are compatibleif they are exactly the same. An indefinite color is compatible with any (specific or indefinite) color.

For example, the following pairs of colors are compatible: (‘f’, ‘f’), (‘?’, ‘z’), (‘a’, ‘?’) and (‘?’, ‘?’). The following pairs of colors are notcompatible: (‘f’, ‘g’) and (‘a’, ‘z’).

Compute the maximum number of pairs of boots such that there is one left and one right boot in a pair and their colors are compatible.

Print the maximum number of such pairs and the pairs themselves. A boot can be part of at most one pair.Input

The first line contains 𝑛n (1≤𝑛≤1500001≤n≤150000), denoting the number of boots for each leg (i.e. the number of left boots and the number of right boots).

The second line contains the string 𝑙l of length 𝑛n. It contains only lowercase Latin letters or question marks. The 𝑖i-th character stands for the color of the 𝑖i-th left boot.

The third line contains the string 𝑟r of length 𝑛n. It contains only lowercase Latin letters or question marks. The 𝑖i-th character stands for the color of the 𝑖i-th right boot.Output

Print 𝑘k — the maximum number of compatible left-right pairs of boots, i.e. pairs consisting of one left and one right boot which have compatible colors.

The following 𝑘k lines should contain pairs 𝑎𝑗,𝑏𝑗aj,bj (1≤𝑎𝑗,𝑏𝑗≤𝑛1≤aj,bj≤n). The 𝑗j-th of these lines should contain the index 𝑎𝑗aj of the left boot in the 𝑗j-th pair and index 𝑏𝑗bj of the right boot in the 𝑗j-th pair. All the numbers 𝑎𝑗aj should be distinct (unique), all the numbers 𝑏𝑗bj should be distinct (unique).

If there are many optimal answers, print any of them.
Examples
input

10 codeforces dodivthree

output

5 7 8 4 9 2 2 9 10 3 1

input

7 abaca?b zabbbcc

output

5 6 5 2 3 4 6 7 4 1 2

input

9 bambarbia hellocode

output

0


input

10 code?????? ??????test

output

10 6 2 1 6 7 3 3 5 4 8 9 7 5 1 2 4 10 9 8 10

## 开52个队列存每个字母在原串中的位置，然后先找相同字母，再从s1中的问号匹配s2中的字母，再用s2中的问号匹配s1中的字母，最后匹配两个串中还剩下的问号。（打比赛的时候用的vector，疯狂tle，赛后改成queue就124ms过了，这。。。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
map<char,int> m;
FF(i,26) m[i+'a']=i;
m['?']=26;
int n; sc(n);
getchar();
string s1,s2;
getline(cin,s1);
getline(cin,s2);
queue<int> v1,v2;
FF(i,n){
v1[m[s1[i]]].push(i+1);
v2[m[s2[i]]].push(i+1);
}
int ans1[maxn],ans2[maxn],index=0;
int ans=0;
FF(i,26){
int minx=min(v1[i].size(),v2[i].size());
ans+=minx;
FF(j,minx){
ans1[index]=v1[i].front(); v1[i].pop();
ans2[index++]=v2[i].front(); v2[i].pop();
}
}
if(v1.size()){
FF(i,26){
while(v2[i].size()&&v1.size()){
ans1[index]=v1.front(); v1.pop();
ans2[index++]=v2[i].front(); v2[i].pop();
ans++;
}
}
}
if(v2.size()){
FF(i,26){
while(v1[i].size()&&v2.size()){
ans1[index]=v1[i].front(); v1[i].pop();
ans2[index++]=v2.front(); v2.pop();
ans++;
}
}
}
if(v1.size()&&v2.size()){
int minx=min(v1.size(),v2.size());
ans+=minx;
FF(j,minx){
ans1[index]=v1.front(); v1.pop();
ans2[index++]=v2.front(); v2.pop();
}
}
pr(ans);
FF(i,index){
printf("%d %d\n",ans1[i],ans2[i]);
}
return 0;
}


## E. Superhero Battle

time limit per test2 seconds memory limit per test256 megabytes

A superhero fights with a monster. The battle consists of rounds, each of which lasts exactly 𝑛n minutes. After a round ends, the next round starts immediately. This is repeated over and over again.

Each round has the same scenario. It is described by a sequence of 𝑛n numbers: 𝑑1,𝑑2,…,𝑑𝑛d1,d2,…,dn (−106≤𝑑𝑖≤106−106≤di≤106). The 𝑖i-th element means that monster’s hp (hit points) changes by the value 𝑑𝑖di during the 𝑖i-th minute of each round. Formally, if before the 𝑖i-th minute of a round the monster’s hp is ℎh, then after the 𝑖i-th minute it changes to ℎ:=ℎ+𝑑𝑖h:=h+di.

The monster’s initial hp is 𝐻H. It means that before the battle the monster has 𝐻H hit points. Print the first minute after which the monster dies. The monster dies if its hp is less than or equal to 00. Print -1 if the battle continues infinitely.Input

The first line contains two integers 𝐻H and 𝑛n (1≤𝐻≤10121≤H≤1012, 1≤𝑛≤2⋅1051≤n≤2⋅105). The second line contains the sequence of integers 𝑑1,𝑑2,…,𝑑𝑛d1,d2,…,dn (−106≤𝑑𝑖≤106−106≤di≤106), where 𝑑𝑖di is the value to change monster’s hp in the 𝑖i-th minute of a round.Output

Print -1 if the superhero can’t kill the monster and the battle will last infinitely. Otherwise, print the positive integer 𝑘k such that 𝑘k is the first minute after which the monster is dead.
Examples
input

1000 6 -100 -200 -300 125 77 -4

output

9


input

1000000000000 5 -1 0 0 0 0

output

4999999999996


input

10 4 -3 -6 5 4

output

-1

## 贪心，模拟每轮打怪兽的过程，如果打完一轮之后hp小于一轮中最大能打掉的hp则在下一轮中就能打死，否则继续打一轮。-1的情况比较好判断

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(2e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
ll a[maxn]; ll h;
ll n;scanf("%lld%lld",&h,&n);
scanf("%lld",&a);
ll minx=a;
rep(i,1,n-1){
scanf("%lld",&a[i]);
a[i]+=a[i-1];
minx=min(minx,a[i]);
}
if(a[n-1]>=0&&h+minx>0){
printf("-1\n");exit(0);
}

ll ans=0;
if(a[n-1]==0||minx+h<=0){
FF(i,n){
if(h+a[i]<=0){
ans=i+1;
break;
}
}
printf("%lld\n",ans);
return 0;
}
ll tem=h+minx;
ll f=tem/(-a[n-1]);
if(tem%(-a[n-1])>0)
f++;
ans+=f*n;
h+=f*a[n-1];
if(h){
FF(i,n){
if(h+a[i]<=0){
ans+=(i+1);
break;
}
}
}
printf("%lld\n",ans);
return 0;
}


## F2. Same Sum Blocks (Hard)

time limit per test3 seconds memory limit per test256 megabytes

This problem is given in two editions, which differ exclusively in the constraints on the number 𝑛n.

You are given an array of integers 𝑎,𝑎,…,𝑎[𝑛].a,a,…,a[n]. A block is a sequence of contiguous (consecutive) elements 𝑎[𝑙],𝑎[𝑙+1],…,𝑎[𝑟]a[l],a[l+1],…,a[r] (1≤𝑙≤𝑟≤𝑛1≤l≤r≤n). Thus, a block is defined by a pair of indices (𝑙,𝑟)(l,r).

Find a set of blocks (𝑙1,𝑟1),(𝑙2,𝑟2),…,(𝑙𝑘,𝑟𝑘)(l1,r1),(l2,r2),…,(lk,rk) such that:

• They do not intersect (i.e. they are disjoint). Formally, for each pair of blocks (𝑙𝑖,𝑟𝑖)(li,ri) and (𝑙𝑗,𝑟𝑗(lj,rj) where 𝑖≠𝑗i≠j either 𝑟𝑖<𝑙𝑗ri<lj or 𝑟𝑗<𝑙𝑖rj<li.
• For each block the sum of its elements is the same. Formally,𝑎[𝑙1]+𝑎[𝑙1+1]+⋯+𝑎[𝑟1]=𝑎[𝑙2]+𝑎[𝑙2+1]+⋯+𝑎[𝑟2]=a[l1]+a[l1+1]+⋯+a[r1]=a[l2]+a[l2+1]+⋯+a[r2]=⋯=⋯=𝑎[𝑙𝑘]+𝑎[𝑙𝑘+1]+⋯+𝑎[𝑟𝑘].a[lk]+a[lk+1]+⋯+a[rk].
• The number of the blocks in the set is maximum. Formally, there does not exist a set of blocks (𝑙′1,𝑟′1),(𝑙′2,𝑟′2),…,(𝑙′𝑘′,𝑟′𝑘′)(l1′,r1′),(l2′,r2′),…,(lk′′,rk′′)satisfying the above two requirements with 𝑘′>𝑘k′>k.

The picture corresponds to the first example. Blue boxes illustrate blocks.

Write a program to find such a set of blocks.Input

The first line contains integer 𝑛n (1≤𝑛≤15001≤n≤1500) — the length of the given array. The second line contains the sequence of elements 𝑎,𝑎,…,𝑎[𝑛]a,a,…,a[n] (−105≤𝑎𝑖≤105−105≤ai≤105).Output

In the first line print the integer 𝑘k (1≤𝑘≤𝑛1≤k≤n). The following 𝑘k lines should contain blocks, one per line. In each line print a pair of indices 𝑙𝑖,𝑟𝑖li,ri (1≤𝑙𝑖≤𝑟𝑖≤𝑛1≤li≤ri≤n) — the bounds of the 𝑖i-th block. You can print blocks in any order. If there are multiple answers, print any of them.
Examples
input

7 4 1 2 2 1 5 3

output

3 7 7 2 3 4 5

input

11 -5 -4 -3 -2 -1 0 1 2 3 4 5

output

2 3 4 1 1

input

4 1 1 1 1

output

4 4 4 1 1 2 2 3 3

## 练习STL的一道好题啊，贪心算法，首先枚举每两个点之间的距离，存到一个map里，第一维存距离，第二维开一个vector，压入左右坐标，这样存完n*n个距离之后将每个距离的vector按照r升序排列，从前往后找，遇到当前点的l>前一个点的r时，符合条件的区间++，上一个点的r更新。遍历完所有的距离之后就能找到答案；

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(2e3)+100
#define mod int(1e9)+7
using namespace std;
struct node{
int l,r;
};
int cmp(node a,node b){
return a.r<b.r;
}
map<int,vector<node>> mp;
int main(){
int n;sc(n);
int a; //前缀和
a=0;
rep(i,1,n){
sc(a[i]);
a[i]+=a[i-1];
}
rep(i,1,n){
rep(j,i,n){
mp[a[j]-a[i-1]].pb({i,j});//距离，左右点坐标
}
}
int ans=0;int pos=0;
for(auto it=mp.begin();it!=mp.end();++it){
sort(it->S.begin(),it->S.end(),cmp);//将当前距离的所有坐标按r升序排
int cnt=0;int rr=0;
for(int i=0;i<it->S.size();++i){
if(it->S[i].l>rr){
cnt++;rr=it->S[i].r;
}
}
if(cnt>ans){
ans=cnt;pos=it->F;
}
}
printf("%d\n",ans);
int rr=0;
for(int i=0;i<mp[pos].size();++i){
if(mp[pos][i].l>rr){
printf("%d %d\n",mp[pos][i].l,mp[pos][i].r);
rr=mp[pos][i].r;
}
}
return 0;
}