# 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;
• add — adds 1 to ?x.

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;
• add — adds 1 to ?x.

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;
}


0 评论