# Educational Codeforces Round 66 (Rated for Div. 2)

## A. From Hero to Zero

time limit per test1 second memory limit per test256 megabytes

You are given an integer 𝑛n and an integer 𝑘k.

In one step you can do one of the following moves:

• decrease 𝑛n by 11;
• divide 𝑛n by 𝑘k if 𝑛n is divisible by 𝑘k.

For example, if 𝑛=27n=27 and 𝑘=3k=3 you can do the following steps: 27→26→25→24→8→7→6→2→1→027→26→25→24→8→7→6→2→1→0.

You are asked to calculate the minimum number of steps to reach 00 from 𝑛n.Input

The first line contains one integer 𝑡t (1≤𝑡≤1001≤t≤100) — the number of queries.

The only line of each query contains two integers 𝑛n and 𝑘k (1≤𝑛≤10181≤n≤1018, 2≤𝑘≤10182≤k≤1018).Output

For each query print the minimum number of steps to reach 00 from 𝑛n in single line.
Exampleinput

2
59 3
1000000000000000000 10

output

8
19

Note

Steps for the first test case are: 59→58→57→19→18→6→2→1→059→58→57→19→18→6→2→1→0.

In the second test case you have to divide 𝑛n by 𝑘k 1818 times and then decrease 𝑛n by 11.

#### 签到题，模拟着除一下

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
ll n,k;
int main(){
int T;cin>>T;
while(T--){
scanf("%lld%lld",&n,&k);
ll ans=-1;
while(n){
ans+=n%k+1; n/=k;
}
printf("%lld\n",ans);
}
}


## B. Catch Overflow!

time limit per test1 second memory limit per test256 megabytes

You are given a function 𝑓f written in some basic language. The function accepts an integer value, which is immediately written into some variable 𝑥x. 𝑥x is an integer variable and can be assigned values from 00 to 232−1232−1. The function contains three types of commands:

• for 𝑛n — for loop;
• end — every command between “for 𝑛n” and corresponding “end” is executed 𝑛n times;

After the execution of these commands, value of 𝑥x is returned.

Every “for 𝑛n” is matched with “end”, thus the function is guaranteed to be valid. “for 𝑛n” can be immediately followed by “end”.”add” command can be outside of any for loops.

Notice that “add” commands might overflow the value of 𝑥x! It means that the value of 𝑥x becomes greater than 232−1232−1 after some “add” command.

Now you run 𝑓(0)f(0) and wonder if the resulting value of 𝑥x is correct or some overflow made it incorrect.

If overflow happened then output “OVERFLOW!!!”, otherwise print the resulting value of 𝑥x.Input

The first line contains a single integer 𝑙l (1≤𝑙≤1051≤l≤105) — the number of lines in the function.

Each of the next 𝑙l lines contains a single command of one of three types:

• for 𝑛n (1≤𝑛≤1001≤n≤100) — for loop;
• end — every command between “for 𝑛n” and corresponding “end” is executed 𝑛n times;

Output

If overflow happened during execution of 𝑓(0)f(0), then output “OVERFLOW!!!”, otherwise print the resulting value of 𝑥x.
Examplesinput

9
for 43
end
for 10
for 15
end
end

output

161

input

2
for 62
end

output

0

input

11
for 100
for 100
for 100
for 100
for 100
end
end
end
end
end

output

OVERFLOW!!!

Note

In the first example the first “add” is executed 1 time, the second “add” is executed 150 times and the last “add” is executed 10 times. Note that “for 𝑛n” can be immediately followed by “end” and that “add” can be outside of any for loops.

In the second example there are no commands “add”, thus the returning value is 0.

In the third example “add” command is executed too many times, which causes 𝑥x to go over 232−1232−1.

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const ll INF=pow(2,32)-1;
ll ans;
stack<ll> s;
int main(){
int n;cin>>n;
s.push(1);
rep(i,1,n){
char op;scanf("%s",op);
if(op=='a'){
if(s.empty()) ans++;
else ans+=s.top();
if(ans>pow(2,32)-1) return puts("OVERFLOW!!!"),0;
}
else if(op=='f'){
ll tem;scanf("%lld",&tem);
if(s.top()*tem<INF) s.push(s.top()*tem);
else s.push(INF+1);
}
else s.pop();
}
printf("%lld\n",ans);
}


## C. Electrification

time limit per test2 seconds memory limit per test256 megabytes

At first, there was a legend related to the name of the problem, but now it’s just a formal statement.

You are given 𝑛n points 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an on the 𝑂𝑋OX axis. Now you are asked to find such an integer point 𝑥x on 𝑂𝑋OX axis that 𝑓𝑘(𝑥)fk(x) is minimal possible.

The function 𝑓𝑘(𝑥)fk(x) can be described in the following way:

• form a list of distances 𝑑1,𝑑2,…,𝑑𝑛d1,d2,…,dn where 𝑑𝑖=|𝑎𝑖−𝑥|di=|ai−x| (distance between 𝑎𝑖ai and 𝑥x);
• sort list 𝑑d in non-descending order;
• take 𝑑𝑘+1dk+1 as a result.

If there are multiple optimal answers you can print any of them.Input

The first line contains single integer 𝑇T (1≤𝑇≤2⋅1051≤T≤2⋅105) — number of queries. Next 2⋅𝑇2⋅T lines contain descriptions of queries. All queries are independent.

The first line of each query contains two integers 𝑛n, 𝑘k (1≤𝑛≤2⋅1051≤n≤2⋅105, 0≤𝑘<𝑛0≤k<n) — the number of points and constant 𝑘k.

The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎1<𝑎2<⋯<𝑎𝑛≤1091≤a1<a2<⋯<an≤109) — points in ascending order.

It’s guaranteed that ∑𝑛∑n doesn’t exceed 2⋅1052⋅105.Output

Print 𝑇T integers — corresponding points 𝑥x which have minimal possible value of 𝑓𝑘(𝑥)fk(x). If there are multiple answers you can print any of them.
Exampleinput

3
3 2
1 2 5
2 1
1 1000000000
1 0
4

output

3
500000000
4

#### 如果k=2，那么需要找的是距离最小的两个点，并且中间隔着0个点；如果k=3，那么需要找的是距离最小的两个点，并且中间隔着1个点；如果k=4，那么需要找的是距离最小的两个点，并且中间隔着2个点；……

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const ll INF=0x7fffffff;
int n,k,a[maxn];
int main(){
int T;cin>>T;
while(T--){
scanf("%d%d",&n,&k);
rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+1+n);
int dis=INF,ans=0;
rep(i,1,n){
if(i+k>n) break;
if(a[i+k]-a[i]<dis){
dis=a[i+k]-a[i];
ans=(a[i+k]+a[i])>>1;
}
}
printf("%d\n",ans);
}
}


## D. Array Splitting

time limit per test2 seconds memory limit per test256 megabytes

You are given an array 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an and an integer 𝑘k.

You are asked to divide this array into 𝑘k non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. Let 𝑓(𝑖)f(i) be the index of subarray the 𝑖i-th element belongs to. Subarrays are numbered from left to right and from 11 to 𝑘k.

Let the cost of division be equal to ∑𝑖=1𝑛(𝑎𝑖⋅𝑓(𝑖))∑i=1n(ai⋅f(i)). For example, if 𝑎=[1,−2,−3,4,−5,6,−7]a=[1,−2,−3,4,−5,6,−7] and we divide it into 33 subbarays in the following way: [1,−2,−3],[4,−5],[6,−7][1,−2,−3],[4,−5],[6,−7], then the cost of division is equal to 1⋅1−2⋅1−3⋅1+4⋅2−5⋅2+6⋅3−7⋅3=−91⋅1−2⋅1−3⋅1+4⋅2−5⋅2+6⋅3−7⋅3=−9.

Calculate the maximum cost you can obtain by dividing the array 𝑎a into 𝑘k non-empty consecutive subarrays.Input

The first line contains two integers 𝑛n and 𝑘k (1≤𝑘≤𝑛≤3⋅1051≤k≤n≤3⋅105).

The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (|𝑎𝑖|≤106|ai|≤106).Output

Print the maximum cost you can obtain by dividing the array 𝑎a into 𝑘k nonempty consecutive subarrays.
Examplesinput

5 2
-1 -2 5 -4 8

output

15

input

7 6
-3 0 -1 -2 -2 -4 -1

output

-45

input

4 1
3 -1 6 0

output

8

#### 挺有意思一道题；首先预处理出来一个后缀和，那么首先sum必取，然后选取k-1个后缀和的值，这样必定可以得到符合题目要求的序列；那这样的话，原题就转化为了在n-1个值中取k-1个使得答案最大，直接sort

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e5+100;
const int INF=0x3f3f3f3f;
int n,k,a[maxn];
ll ans=0,sum[maxn];
bool cmp(ll a,ll b){return a>b;}
int main(){
cin>>n>>k;
rep(i,1,n) scanf("%d",&a[i]),ans+=a[i];
dep(i,n,1) sum[i]=sum[i+1]+a[i];
sort(sum+2,sum+1+n,cmp);
rep(i,2,k) ans+=sum[i];
cout<<ans<<endl;
}