Educational Codeforces Round 66 (Rated for Div. 2) 题解

B. Catch Overflow!

http://codeforces.com/contest/1175/problem/B

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

• for nn — for loop;
• end — every command between "for nn" and corresponding "end" is executed nn times;
• add — adds 1 to xx.

After the execution of these commands, value of xx is returned.

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

Notice that "add" commands might overflow the value of xx! It means that the value of xx becomes greater than 232−1232−1 after some "add" command.

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

If overflow happened then output "OVERFLOW!!!", otherwise print the resulting value of xx.

Input

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

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

• for nn (1≤n≤1001≤n≤100) — for loop;
• end — every command between "for nn" and corresponding "end" is executed nn times;
• add — adds 1 to xx.

Output

If overflow happened during execution of f(0)f(0), then output "OVERFLOW!!!", otherwise print the resulting value of xx.

Examples

input

Copy

9
add
for 43
end
for 10
for 15
add
end
add
end

output

Copy

161

input

Copy

2
for 62
end

output

Copy

0

input

Copy

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

output

Copy

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 nn" 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 xx to go over 232−1232−1.

题意：给出for语句，end语句，add语句，问最后的答案是多少，如果超出1ll<<32-1的范围输出overflow！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1ll<<32;
char s[10];
stack<ll>q1;
ll num;
int main()
{
	q1.push(1);
	int n;
	cin>>n;
	bool flag=0;
	ll ans=0;
	for(int i=1;i<=n;++i)
	{
		cin>>s+1;
		if(s[1]=='f')
		{
			cin>>num;
			q1.push(min(q1.top()*num,N));
		}
		else if(s[1]=='e')	q1.pop();
		else
		{
			if(q1.top()>=N) flag=1;
			ans+=q1.top();
			if(ans>=N) flag=1;
		}
	}
	if(flag||ans>=N) printf("OVERFLOW!!!\n");
	else printf("%lld\n",ans);
}

C. Electrification

http://codeforces.com/contest/1175/problem/

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

You are given nn points a1,a2,…,ana1,a2,…,an on the OXOX axis. Now you are asked to find such an integer point xx on OXOX axis that fk(x)fk(x) is minimal possible.

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

• form a list of distances d1,d2,…,dnd1,d2,…,dn where di=|ai−x|di=|ai−x| (distance between aiai and xx);
• sort list dd in non-descending order;
• take dk+1dk+1 as a result.

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

Input

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

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

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

It's guaranteed that ∑n∑n doesn't exceed 2⋅1052⋅105.

Output

Print TT integers — corresponding points xx which have minimal possible value of fk(x)fk(x). If there are multiple answers you can print any of them.

Example

input

Copy

给 n，k，a数组 n个数据

选一个位置x，d数组是给定a数组减去x的绝对值。问使得d数组第k+1个最小时 x的位置。

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

output

Copy

3
500000000
4

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int n,k;
int a[N];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;++i) cin>>a[i];
		int mx=2e9+10;
		sort(a+1,a+1+n);
		int ans=0;
		for(int i=1;i+k<=n;++i)
		{
			if(a[i+k]-a[i]<mx)
			{
				mx=a[i+k]-a[i];
				ans=a[i];
			}
		}
		printf("%d\n",mx/2+ans);
	}
}

D. Array Splitting

http://codeforces.com/contest/1175/problem/D

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a1,a2,…,ana1,a2,…,an and an integer kk.

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

Let the cost of division be equal to ∑i=1n(ai⋅f(i))∑i=1n(ai⋅f(i)). For example, if a=[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 aa into kk non-empty consecutive subarrays.

Input

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

The second line contains nn integers a1,a2,…,ana1,a2,…,an (|ai|≤106|ai|≤106).

Output

Print the maximum cost you can obtain by dividing the array aa into kk nonempty consecutive subarrays.

Examples

input

Copy

给定n，k，

数组a  n个数据。问如何将数组a连续分成k块。总价值是所有数的当前数乘上当前数所在块的序号  之和。

问最大值

 

做法。处理前缀和+排序（只排1~n-1）。k*sum[n]  然后依次减去前k-1个小的前缀和。因为k*sum[n]的时候可能多乘了一些本该是乘1 or  2  or...k-1的，所以比sum[n]第一小的减一次   比sum[n]第二小的减两次，就成功的实现了 比sum[n]第一小乘了 k-1，比sum[n]第二小乘k-2

5 2
-1 -2 5 -4 8

output

Copy

15

input

Copy

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

output

Copy

-45

input

Copy

4 1
3 -1 6 0

output

Copy

8

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll sum[N];
int n,k;
int main()
{
	cin>>n>>k; 
	for(int i=1;i<=n;++i)
	{
		ll x;
		cin>>x;
		sum[i]=sum[i-1]+x;
	}
	sort(sum+1,sum+n);
	ll ans=k*sum[n];
	//printf("ans:%lld\n",ans);
	for(int i=1;i<k;++i)
	{
		ans-=sum[i];
	}
	printf("%lld\n",ans);
}

/*
5
4
1 2 3 4
5 
1 2 3 4 5
6
1 2 3 4 5 6
*/

D. New Year and the Permutation Concatenation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Let nn be an integer. Consider all permutations on integers 11 to nn in lexicographic order, and concatenate them into one big sequence pp. For example, if n=3n=3, then p=[1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1]p=[1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1]. The length of this sequence will be n⋅n!n⋅n!.

Let 1≤i≤j≤n⋅n!1≤i≤j≤n⋅n! be a pair of indices. We call the sequence (pi,pi+1,…,pj−1,pj)(pi,pi+1,…,pj−1,pj) a subarray of pp. Its length is defined as the number of its elements, i.e., j−i+1j−i+1. Its sum is the sum of all its elements, i.e., ∑jk=ipk∑k=ijpk.

You are given nn. Find the number of subarrays of pp of length nn having sum n(n+1)2n(n+1)2. Since this number may be large, output it modulo 998244353998244353 (a prime number).

Input

The only line contains one integer nn (1≤n≤1061≤n≤106), as described in the problem statement.

Output

Output a single integer — the number of subarrays of length nn having sum n(n+1)2n(n+1)2, modulo 998244353998244353.

Examples

input

Copy

3

output

Copy

9

input

Copy

4

output

Copy

56

input

Copy

10

output

Copy

30052700

Note

In the first sample, there are 1616 subarrays of length 33. In order of appearance, they are:

[1,2,3][1,2,3], [2,3,1][2,3,1], [3,1,3][3,1,3], [1,3,2][1,3,2], [3,2,2][3,2,2], [2,2,1][2,2,1], [2,1,3][2,1,3], [1,3,2][1,3,2], [3,2,3][3,2,3], [2,3,1][2,3,1], [3,1,3][3,1,3], [1,3,1][1,3,1], [3,1,2][3,1,2], [1,2,3][1,2,3], [2,3,2][2,3,2], [3,2,1][3,2,1].

Their sums are 66, 66, 77, 66, 77, 55, 66, 66, 88, 66, 77, 55, 66, 66, 77, 66. As n(n+1)2=6n(n+1)2=6, the answer is 99.

来自https://www.cnblogs.com/pkgunboat/archive/2018/12/31/10201676.html

思路（非官方题解）：官方题解下面有种方法是：There is also a simple recurrence counting the same answer, found by arsijo:d(n)=(d(n−1)+(n−1)!−1)⋅n，我比赛时是用这个方法。

如官方题解思路，有两种n长度的子序列符合【和为n*(n-1)/2】：
第一种为n！个组成序列的排列；
第二种为一部分在一个排列中，另一部分在下一个排列中的排列。
显而易见，第一种有n！种情况，那下面来推第二种：

对于一个n长度的排列，假设我们先固定前k个元素，那么对于包含这些前k个元素固定的片段，是一系列①前k个元素固定；②后n-k个元素按照字典序从小到大的排列连接而成的，假设这一系列排列的数量为m。

发现这个有什么用呢？现在取出上面那段片段，我们来寻找里面排列为③使用一个排列后n-k个元素④使用下一个排列前k个元素的排列的数量，在上面片段中，能找到的排列都满足，而又由于这些排列夹在上面排列两两之间，可得数量为m-1。（就像对于一个队伍的小朋友，假设两两之间插入一个小朋友，那么插入小朋友的数量为原队伍小朋友的数量-1）。
那么有没有漏网之鱼呢？答案是没有。这个草稿纸上画下，你就明白了。m中满足条件的有m-1种，说明只有一种是不满足的。对于假设考虑只满足③的，那么片段的第一个排列是不满足的，考虑只满足④的话，片段的最后一个排列是不满足的。就不展开了。（不会暴露楼主不想打，，，咔咔）

现在还有一个问题，就是m未知，现在来求m：
由①，则有A(n,n-k)种；
而对于①的每种情况
由②，有k!种，又由解释需要-1，则有(k!-1)种情况。
至此可以得到一个重要的信息，列为③使用一个排列后n-k个元素④使用下一个排列前k个元素的排列的数量 = A(n,n-k)*(k!-1)。

知道上述公式后，来求答案：
k∈[1,n]；
当k=n时，其实就是组成序列的排列，所以用组成序列排列的公式：n！；
当k!=n时，用上面得出的公式A(n,n-k)*(k!-1)；
因此答案是n!+∑(k from 1 to n-1) [A(n,n-k)×(k!-1)]。
来自 原文：https://blog.csdn.net/aiqiyizz/article/details/85530211  https://blog.csdn.net/aiqiyizz/article/details/85530211

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const ll mod=998244353;
ll a[N],b[N];

int main()
{
	int n;
	cin>>n;
	a[0]=b[n]=1;
	for(int i=n;i>=1;i--)
	{
		a[n-i+1]=1ll*i*a[n-i]%mod;
	}
	int j=1;
	for(int i=n-1;i>=1;--i)
	{
		b[i]=1ll*j*b[i+1]%mod;
		++j;
	}
	/*for(int i=1;i<=n;i++) printf("%lld ",a[i]);puts("");
	for(int i=1;i<=n;i++) printf("%lld ",b[i]);puts("");*/
	ll ans=0;
	for(int i=1;i<n;++i)
	{
		ans=(ans+a[i]*(b[i]-1)%mod)%mod;
	}
	printf("%lld\n",(ans+a[n])%mod);
}