Educational Codeforces Round 86 (Rated for Div. 2)

---

Enter $\looparrowright$

A. Road To Zero

You are given two integers $x$ and $y$. You can perform two types of operations:
Pay a dollars and increase or decrease any of these integers by $1$. For example, if $x=0$ and $y=7$ there are four possible outcomes after this operation:$x=0, y=6$;$x=0, y=8$;$x=−1, y=7$;$x=1, y=7.$
Pay b dollars and increase or decrease both integers by $1$. For example, if $x=0$ and $y=7$ there are two possible outcomes after this operation: $x=−1, y=6$;$x=1, y=8.$
Your goal is to make both given integers equal zero simultaneously, i.e. $x=y=0$. There are no other requirements. In particular, it is possible to move from $x=1$, $y=0$ to $x=y=0$.
Calculate the minimum amount of dollars you have to spend on it.

Input

The first line contains one integer $t$ $(1≤t≤100)$ — the number of testcases.
The first line of each test case contains two integers $x$ and $y$ $(0≤x,y≤10^9)$.
The second line of each test case contains two integers $a$ and $b$ $(1≤a,b≤10^9)$.

Output

For each test case print one integer — the minimum amount of dollars you have to spend.

Example

input

2
1 3
391 555
0 0
9 4

output

1337
0

Note

In the first test case you can perform the following sequence of operations: first, second, first. This way you spend $391$$+$$555$$+$$391$$=$$1337$ dollars.
In the second test case both integers are equal to zero initially, so you don’t have to spend money.

Translation

给两个数 $x,y$。花费 $a$ 的代价可以进行操作 $1$：选择 $x,y$ 其中的一个数将其增加或者减少 $1$。花费 $b$ 的代价可以进行操作 $2 $：将 $x,y$ 都增加或者减少 $1$。求将 $x,y$ 都置为 $0$ 的最底花费。

Idea

由于 $x,y\ge 0$ ，所以先进行几次操作 $2$，直到 $\min(x,y)$ 为 $0$ ，接着再执行几次操作 $1$，直到 $\max(x,y)$ 为 $0$ ，那么就能用最少的操作次数达到目的。但是最高效率并不意味着最低花费，我们可以将操作 $2$ 视为执行了两次操作 $1$，那么如果两次操作 $1$ 的花费低于操作 $2$ ，那么执行两次操作 $1$ 才能达到最低花费的目的。也就是说，如果两次操作 $1$ 的花费低于操作 $2$，那么就用两次操作 $1$ 的代价代替一次操作 $2$ 的代价。

Code

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
using namespace std;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		ll x,y,a,b;
		scanf("%lld%lld%lld%lld",&x,&y,&a,&b);
		printf("%lld\n",min(x,y)*min(a*2,b)/*取最小*/+abs(y-x)*a);
	}
	return 0;
}

B. Binary Period

Let’s say string $s$ has period $k$ if $s_i=s_{i+k}$ for all $i$ from $1$ to $|s|−k$ ($|s|$ means length of string $s$) and $k$ is the minimum positive integer with this property.
Some examples of a period: for $s=“0101”$ the period is $k=2$, for $s=“0000”$ the period is $k=1$, for $s=“010”$ the period is $k=2$, for $s=“0011”$ the period is $k=4$.
You are given string $t$ consisting only of $0$’s and $1$’s and you need to find such string $s$ that:
String $s$ consists only of $0$’s and $1$’s;
The length of $s$ doesn’t exceed $2⋅|t|$;
String $t$ is a subsequence of string $s$;
String $s$ has smallest possible period among all strings that meet conditions $1—3$.
Let us recall that $t$ is a subsequence of $s$ if $t$ can be derived from $s$ by deleting zero or more elements (any) without changing the order of the remaining elements. For example, $t=“011”$ is a subsequence of $s=“10101”$.

Input

The first line contains single integer $T$$ (1≤T≤100)$ — the number of test cases.
Next T lines contain test cases — one per line. Each line contains string $t$$ (1≤|t|≤100)$ consisting only of $0$’s and $1$’s.

Output

Print one string for each test case — string $s$ you needed to find. If there are multiple solutions print any one of them.

Example

input

4
00
01
111
110

output

00
01
11111
1010

Note

In the first and second test cases, $s=t$ since it’s already one of the optimal solutions. Answers have periods equal to $1$ and $2$, respectively.
In the third test case, there are shorter optimal solutions, but it’s okay since we don’t need to minimize the string $s$. String $s$ has period equal to $1$.

Translation

给一个 $01$ 串 $t$，输出一个 $01$ 串 $s$。要求 $|s|\le 2\times |t|$，$t$ 是 $s$ 的子序列，$s_i=s_{i+k}$ 且要求 $k$ 最小。

Idea

显然，如果 $t=1111111\cdots $ 或 $t=000000\cdots$ ，那么 $t $ 本身就符合条件 $1-3$，且此时的 $k=1$ ，是最小的。若 $t$ 中出现了 $0$ 和 $1$，我们可以在 $t$ 中添加一些字符得到 $s$ ，这样做的好处是 $t$ 自然会成为 $s$ 的子序列；我们让 $s$ 成为 $0$ 和 $1$ 交替的串，即 $s=10101010\cdots$ 或 $s=01010101\cdots$ ，此时的 $s$ 必然满足条件，且此时的 $k=2$ ，是最小的。

Code

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		string s;
		cin>>s;
		int i;
		if(s.find('1')==s.npos) cout<<s;//全为0
		else if(s.find('0')==s.npos) cout<<s;//全为1
		else
		{
			for(i=0;i<s.length()-1;i++)
			{
				if(s[i]==s[i+1])//添加字符
				{
					if(s[i]=='0') s.insert(i+1,1,'1');
					else s.insert(i+1,1,'0');
				}
			}
			cout<<s;
		}
		putchar('\n');
	}
	return 0;
}

C. Yet Another Counting Problem

You are given two integers $a$ and $b$, and $q$ queries. The $i$-th query consists of two numbers $l_i$ and $r_i$, and the answer to it is the number of integers $x$ such that $l_i≤x≤r_i$, and $($$x$$\bmod a$$)$$\bmod b$$≠$$($$x$$\bmod b$$)$$\bmod a$. Calculate the answer for each query.
Recall that $y\bmod z$ is the remainder of the division of $y$ by $z$. For example, $5$$\bmod3$$=$$2$, $7$$\bmod8$$=$$7$$, $$9$$\bmod 4$$=$$1$, $9$$\bmod 9$$=$$0$.

Input

The first line contains one integer $t$ $(1≤t≤100)$ — the number of test cases. Then the test cases follow.
The first line of each test case contains three integers $a$, $b$ and $q$ $($$1$$≤$$a$$,$$b$$≤$$200$$;$$ 1$$≤$$q$$≤$$500$$)$.
Then $q$ lines follow, each containing two integers $l_i$ and $r_i$ $(1≤l_i≤r_i≤10^{18})$ for the corresponding query.

Output

For each test case, print $q$ integers — the answers to the queries of this test case in the order they appear.

Example

input

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

output

0 0 0 2 4
0 91

Translation

给定两个数 $a,b$ ，在 $q$ 次询问中，每次给一个区间 $W=[l_i,r_i]$，求集合 $\{$$x\in W|($$x$$\bmod a$$)$$\bmod b$$≠$$($$x$$\bmod b$$)$$\bmod a$$\}$ 中的元素个数。

Idea

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int i;
	int n=a*b/__gcd(a,b);
	int ans;
	for(i=1;i<=3*n;i++)
	{
		if(i%a%b!=i%b%a) ans=1;
		else ans=0;
		cout<<i<<' '<<ans<<endl;
	}
	return 0;
}

从第三行起，输出的左边是 $x$ ，右边代表 $($$x$$\bmod a$$)$$\bmod b$$≠$$($$x$$\bmod b$$)$$\bmod a$ 的真假。

如图，$($$x$$\bmod a$$)$$\bmod b$$≠$$($$x$$\bmod b$$)$$\bmod a$ 的分布是按照 $\operatorname{lcm}(a, b)$ 长度循环的。也就是说，我们只需要知道 $[1,\operatorname{lcm}(a, b)]$ 内的分布情况，就能得到任意区间的分布情况。因此查询是 $O(1)$ 的。
考虑一个前缀和函数 $query(p)$ 代表 $[1,p]$ 内符合条件 $($$x$$\bmod a$$)$$\bmod b$$≠$$($$x$$\bmod b$$)$$\bmod a$ 的 $x$ 的个数。对于询问 $[l_i,r_i]$，只需要输出 $query(r_i)-query(l_i-1)$。直接用数组存这个前缀和显然是不现实的，我们要利用前面找到的规律。由于分布基于 $[1,\operatorname{lcm}(a, b)]$ 循环，那么就可以求出 $[1,\operatorname{lcm}(a, b)]$ 内的前缀和 $ans[i]$；当查询 $[1,p]$ 的前缀和时，由于每段长度为 $\operatorname{lcm}(a, b)$ 的区间分布相同，$[1,p]$ 内首先就有贡献 $\frac{p}{\operatorname{lcm}(a, b)}\times ans[\operatorname{lcm}(a,b)]$ ，剩余的部分中，有 $ans[p\bmod\operatorname{lcm}(a,b)]$ ，因此 $[1,p]$ 内的总贡献为$\frac{p}{\operatorname{lcm}(a, b)}\times ans[\operatorname{lcm}(a,b)]+ans[p\bmod\operatorname{lcm}(a,b)]$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll ans[40003];
ll l,r;
int a,b,q;
ll n;
void init()//得到[1,lcm(a,b)]的前缀和
{
	int i;
	for(i=0;i<=n;i++)
	{
		if(i%a%b==i%b%a) ans[i]=0;
		else ans[i]=1;
	}
	for(i=1;i<=n;i++) ans[i]+=ans[i-1];
}
ll query(ll p) {return p/n*ans[n]+ans[p%n];}//得到[1,p]的前缀和
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		int i;
		scanf("%d%d%d",&a,&b,&q);
		n=a*b/__gcd(a,b);//循环节
		init();
		while(q--)
		{
			scanf("%lld%lld",&l,&r);
			printf("%lld ",query(r)-query(l-1));//查询
		}
		putchar('\n');
	}
	return 0;
}

D. Multiple Testcases

So you decided to hold a contest on Codeforces. You prepared the problems: statements, solutions, checkers, validators, tests… Suddenly, your coordinator asks you to change all your tests to multiple testcases in the easiest problem!
Initially, each test in that problem is just an array. The maximum size of an array is $k$. For simplicity, the contents of arrays don’t matter. You have $n$ tests — the i-th test is an array of size $m_i$ $(1≤m_i≤k)$.
Your coordinator asks you to distribute all of your arrays into multiple testcases. Each testcase can include multiple arrays. However, each testcase should include no more than $c_1$ arrays of size greater than or equal to $1 (≥1)$, no more than $c_2$ arrays of size greater than or equal to $2$, …, no more than $c_k$ arrays of size greater than or equal to $k$. Also, $c_1≥c_2≥⋯≥c_k$.
So now your goal is to create the new testcases in such a way that:

• each of the initial arrays appears in exactly one testcase;
• for each testcase the given conditions hold;
• the number of testcases is minimum possible.
  Print the minimum possible number of testcases you can achieve and the sizes of arrays included in each testcase.

Input

The first line contains two integers $n$ and $k$ $(1≤n,k≤2⋅10^5)$ — the number of initial tests and the limit for the size of each array.
The second line contains $n$ integers $m_1,m_2,…,m_n$ $(1≤m_i≤k)$ — the sizes of the arrays in the original tests.
The third line contains $k$ integers $c_1,c_2,\dots,c_k(n\ge c_1\ge c_2\cdots\ge c_k\ge 1)$; $c_i$ is the maximum number of arrays of size greater than or equal to $i$ you can have in a single testcase.

Output

In the first line print a single integer $ans$ $(1≤ans≤n)$ — the minimum number of testcases you can achieve.
Each of the next ans lines should contain the description of a testcase in the following format:
$t$ $a_1, a_2, …, a_t$ $(1≤t≤n)$ — the testcase includes $t$ arrays, $a_i$ is the size of the $i$-th array in that testcase.
Each of the initial arrays should appear in exactly one testcase. In particular, it implies that the sum of t over all ans testcases should be equal to $n$.
Note that the answer always exists due to $c_k≥1$ (and therefore $c_1≥1$).
If there are multiple answers, you can output any one of them.

Examples

input

4 3
1 2 2 3
4 1 1

output

3
1 2
2 1 3
1 2

input

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

output

2
3 8 5 7
3 10 8 1

input

5 1
1 1 1 1 1
5

output

1
5 1 1 1 1 1

input

5 1
1 1 1 1 1
1

output

5
1 1
1 1
1 1
1 1
1 1

Note

In the first example there is no way to distribute the tests into less than $3$ testcases. The given answer satisfies the conditions: each of the testcases includes no more than $4$ arrays of size greater than or equal to $1$ and no more than $1$ array of sizes greater than or equal to $2$ and $3$.
Note that there are multiple valid answers for this test. For example, testcases with sizes $[[2],[1,2],[3]]$ would also be correct.
However, testcases with sizes $[[1,2],[2,3]]$ would be incorrect because there are $2$ arrays of size greater than or equal to $2$ in the second testcase.
Note the difference between the third and the fourth examples. You can include up to $5$ arrays of size greater than or equal to $1$ in the third example, so you can put all arrays into a single testcase. And you can have only up to $1$ array in the fourth example. Thus, every array should be included in a separate testcase.

Translation

数列 $\{m_n\}$ 中的最大元素为 $k$ 。将数列 $\{m_n\}$ 分组，要求每组中大于等于 $i$ 的数字个数不超过 $c_i$。
要求分的组的数量尽可能小，并输出分组情况。

Idea

设数列 $\{m_n\}$ 中大于等于 $i$ 的数字个数为 $cnt_i$。
于是，大于等于 $i$ 的数字有 $cnt_i$ 个，每组不能超过 $c_i$ 个，需要分成 $\left\lceil \frac{cnt_i}{c_i}\right\rceil$ 组。所以，当我们考察整个数列中的所有数字，至少需要分成 $ans=\max\limits_{1\le i\le k}\left\{\left\lceil \frac{cnt_i}{c_i}\right\rceil\right\}$ 组。
因此我们只需要将 $m_i$ 从大到小依次循环填入第 $1,2,\cdots,ans,1,2,\cdots$ 组即可，这样的分布是最优的，一定可以满足条件。

Code

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<vector>
#define N 200003
using namespace std;
int n,k;
int m[N],c[N];
int cnt[N];
vector<int>group[N];
int main()
{
	cin>>n>>k;
	int i;
	for(i=1;i<=n;i++) scanf("%d",m+i);
	for(i=1;i<=k;i++) scanf("%d",c+i);
	sort(m+1,m+1+n,greater<int>());//降序排列
	int j=1;
	i=1;
	//双指针计算大于等于i的数字个数cnt[i]
	while(i<=n&&j<=n)
	{
		while(m[i]==m[j]&&j<=n) j++;
		cnt[m[i]]=j-1;
		i=j;
	}
	int ans=0;
	for(i=1;i<=k;i++) ans=max(ans,(int)ceil(1.0*cnt[i]/c[i]));//得到分组数量
	cout<<ans<<endl;
	for(i=1,j=1;i<=n;i++,j=j+1>ans?1:j+1) group[j].push_back(m[i]);//依次填入
	for(i=1;i<=ans;i++)//输出
	{
		printf("%d ",group[i].size());
		for(int j:group[i]) printf("%d ",j);
		putchar('\n');
	}
	return 0;
}

E. Placing Rooks

Calculate the number of ways to place n rooks on n×n chessboard so that both following conditions are met:
- each empty cell is under attack;
- exactly $k$ pairs of rooks attack each other.
An empty cell is under attack if there is at least one rook in the same row or at least one rook in the same column. Two rooks attack each other if they share the same row or column, and there are no other rooks between them. For example, there are only two pairs of rooks that attack each other in the following picture:

One of the ways to place the rooks for $n=3$ and $k=2$
Two ways to place the rooks are considered different if there exists at least one cell which is empty in one of the ways but contains a rook in another way.
The answer might be large, so print it modulo $998244353$.

Input

The only line of the input contains two integers $n$ and $k$ $(1≤n≤200000; 0≤k≤\frac{n(n−1)}{2})$.

Output

Print one integer — the number of ways to place the rooks, taken modulo 998244353.

Examples

input

3 2

output

6

input

3 3

output

0

input

4 0

output

24

input

1337 42

output

807905441

Translation

在一个 $n\times n$ 的国际象棋棋盘上放置 $n$ 个车，满足以下两个条件：①棋盘上的每一个空格子都能被攻击到，②恰好存在 $k$ 对车可以相互攻击。

Idea

要在 $n\times n$ 的棋盘上放 $n$ 个车，使得所有空格都能被攻击到，那么每行/列都需要有一个车。我们先假设每行都有一个车，由棋盘的对称性，列的情况与之相同。以下的讨论只都基于每行都有一个车的情况。
设想现在每行都有一个车，如果考察行，每一辆车是互不干扰的，要使有 $k$ 个车能互相攻击，需要在列上做文章。初始情况是所有车都在棋盘的对角线上，这时没有车能互相攻击。我们选出 $k$ 列置为空，将 $k$ 个车放入其他 $n-k$ 列中；设想如果一列上有 $x(x>0)$ 个车，那么这列上能互相攻击的车的数目为 $x-1$；对于这 $n-k$ 列，能互相攻击的车的数目为 $\sum\limits_{i=1}^{n-k} (x_i-1)$$=$$\sum\limits_{i=1}^{n-k}x_i$$-$$\sum\limits_{i=1}^{n-k}1$$=n-(n-k)=k$。所以该问题等价于将 $n$ 个车放入 $n-k$ 列中。
立刻联想到了第二类斯特林数（$\text{Stirling Number of the Second Kind }$）。把 $n$ 个不同的球放到 $m$个相同的盒子里，假设没有空盒，则放球方案数记做 $S(n,m)$，称为第二类斯特林数。

$$S(n,m)={\frac 1 {m!}}\sum_{i=0}^m (-1)^i C(m,i)(m-i)^n$$

由于棋盘上每一列是不同的，所以系数 $\frac 1 {m!}$ 是多余的；此外，要从 $n$ 列中选出 $n-k$ 列放置 $n$ 个车，需要乘上系数 $C_{n}^{n-k}$。

$$ans=C_n^{n-k}\sum_{i=0}^{n-k} (-1)^i C_{n-k}^i(n-k-i)^n$$

当 $k\ge n$ 时组合数无意义，答案为 $0$。否则， 当 $k=0$ 时行和列的情况重复，只有在 $k\ne 0$ 时，答案需要乘 $2$ 来加上每一列上都有车的情况。

Code

#include<iostream>
#define ll long long
using namespace std;
const ll mod=998244353; 
ll ans;
int n,k;
ll fac[200002];
ll quick_pow(ll a,ll b)//快速幂
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
ll C(int n,int m)//组合数、逆元
{
	return fac[n]*quick_pow(fac[m],mod-2)%mod*quick_pow(fac[n-m],mod-2)%mod;
}
void init()
{
	fac[0]=1;
	ll i;
	for(i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
}
int main()
{
	cin>>n>>k;
	if(k>=n) puts("0");
	else
	{
		init();//初始化阶乘
		int i;
		int m=n-k;
		for(i=0;i<=m;i++)//迭代累加
		{
			int sign=i&1?-1:1;
			ll temp=sign*(C(m,i)*quick_pow(m-i,n));
			ans=(ans+temp+mod)%mod;
		}
		ans=ans*C(n,m)%mod;
		printf("%lld\n",k==0?ans%mod:ans*2%mod);//输出
	}
	return 0;
}

后记

乘 $2$ 之后记得取余。