Codeforces Round #723 (Div. 2)

Codeforces Round #723 (Div. 2)

A. Mean Inequality

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa of 2n2n distinct integers. You want to arrange the elements of the array in a circle such that no element is equal to the the arithmetic mean of its 22 neighbours.

More formally, find an array bb, such that:

  • bb is a permutation of aa.

  • For every ii from 11 to 2n2n, bi≠bi−1+bi+12bi≠bi−1+bi+12, where b0=b2nb0=b2n and b2n+1=b1b2n+1=b1.

It can be proved that under the constraints of this problem, such array bb always exists.

Input

The first line of input contains a single integer tt (1≤t≤1000)(1≤t≤1000) — the number of testcases. The description of testcases follows.

The first line of each testcase contains a single integer nn (1≤n≤25)(1≤n≤25).

The second line of each testcase contains 2n2n integers a1,a2,…,a2na1,a2,…,a2n (1≤ai≤109)(1≤ai≤109) — elements of the array.

Note that there is no limit to the sum of nn over all testcases.

Output

For each testcase, you should output 2n2n integers, b1,b2,…b2nb1,b2,…b2n, for which the conditions from the statement are satisfied.

Example

input

Copy

3
3
1 2 3 4 5 6
2
123 456 789 10
1
6 9

output

Copy

3 1 4 2 5 6
123 10 456 789
9 6

Note

In the first testcase, array [3,1,4,2,5,6][3,1,4,2,5,6] works, as it's a permutation of [1,2,3,4,5,6][1,2,3,4,5,6], and 3+4/2≠1 3+4/2≠1, 1+2/2≠4 1+2/2≠4, 4+5/2≠2 4+5/2≠2, 2+6/2≠5 2+6/2≠5, 5+3/2≠6 5+3/2≠6, 6+1/2≠3 6+1/2≠3.

题意

前一个加后一个不等于中间一个

所以可以先排序

然后再输出小大小大交替输出

上代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int a[50];
		for(int i=0;i<n*2;i++)
		cin>>a[i];
		sort(a,a+n*2);
		for(int i=0;i<n;i++)
		{
			cout<<a[i]<<" "<<a[2*n-i-1]<<" ";
		}
		cout<<endl;
	}
}

 

B. I Hate 1111

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an integer xx. Can you make xx by summing up some number of 11,111,1111,11111,…11,111,1111,11111,…? (You can use any number among them any number of times).

For instance,

  • 33=11+11+1133=11+11+11
  • 144=111+11+11+11144=111+11+11+11

Input

The first line of input contains a single integer tt (1≤t≤10000)(1≤t≤10000) — the number of testcases.

The first and only line of each testcase contains a single integer xx (1≤x≤109)(1≤x≤109) — the number you have to make.

Output

For each testcase, you should output a single string. If you can make xx, output "YES" (without quotes). Otherwise, output "NO".

You can print each letter of "YES" and "NO" in any case (upper or lower).

Example

input

Copy

3
33
144
69

output

Copy

YES
YES
NO

Note

Ways to make 3333 and 144144 were presented in the statement. It can be proved that we can't present 6969 this way.

这题只要11和111就可以组成所有的由1组成的数

所以只要算多少个11和111就行,

例如1111=11*100+11

11111=111*100+11

能组成就是Yes不能就是No

代码

#include<iostream>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int k=n%11;
		n=n-k*111;
		if(n>=0)
		cout<<"YES"<<endl;
		else
		cout<<"NO"<<endl;
	}
}

C1. Potions (Easy Version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

This is the easy version of the problem. The only difference is that in this version n≤2000n≤2000. You can make hacks only if both versions of the problem are solved.

There are nn potions in a line, with potion 11 on the far left and potion nn on the far right. Each potion will increase your health by aiai when drunk. aiai can be negative, meaning that potion will decrease will health.

You start with 00 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?

Input

The first line contains a single integer nn (1≤n≤20001≤n≤2000) — the number of potions.

The next line contains nn integers a1a1, a2a2, ... ,anan (−109≤ai≤109−109≤ai≤109) which represent the change in health after drinking that potion.

Output

Output a single integer, the maximum number of potions you can drink without your health becoming negative.

Example

input

Copy

6
4 -4 1 -3 1 -3

output

Copy

5

Note

For the sample, you can drink 55 potions by taking potions 11, 33, 44, 55 and 66. It is not possible to drink all 66 potions because your health will go negative at some point

 

这题没想出来

dalao告诉我是反贪心

用先序序列就可以做

看完代码后觉得dalao太厉害了

佩服

我来说一下主要思想实现

一瓶瓶药嗑下去,当身体吃不消的时候就吐出来对身体伤害最大的药,

吐完后接着嗑药

直到最后一瓶药为止

上代码

#include<bits/stdc++.h>
using namespace std;
long long c=0;
long long ans=0;
long long n;
priority_queue<long long,vector<long long>,greater<long long> >pq;
int main(){
	cin>>n;
	while(n--){
		long long x;cin>>x;
		pq.push(x),c+=x,ans++;
		if(c<0)c-=pq.top(),pq.pop(),ans--;
	}
	cout<<ans;
}

 

 

C2. Potions (Hard Version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

This is the easy version of the problem. The only difference is that in this version n≤2000n≤2000. You can make hacks only if both versions of the problem are solved.

There are nn potions in a line, with potion 11 on the far left and potion nn on the far right. Each potion will increase your health by aiai when drunk. aiai can be negative, meaning that potion will decrease will health.

You start with 00 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.

What is the largest number of potions you can drink?

Input

The first line contains a single integer nn (1≤n≤200000 1≤n≤200000) — the number of potions.

The next line contains nn integers a1a1, a2a2, ... ,anan (−109≤ai≤109−109≤ai≤109) which represent the change in health after drinking that potion.

Output

Output a single integer, the maximum number of potions you can drink without your health becoming negative.

Example

input

Copy

6
4 -4 1 -3 1 -3

output

Copy

5

Note

For the sample, you can drink 55 potions by taking potions 11, 33, 44, 55 and 66. It is not possible to drink all 66 potions because your health will go negative at some point

 

进阶版就是数据范围变大了

用先序序列完全可以过

代码都不用改 

上一篇:elk的一些零碎知识


下一篇:python数据分析入门