Educational Codeforces Round 114 (Rated for Div. 2) ABC
2021-9-21
·
hexer

A. Regular Bracket Sequences

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

A bracket sequence is a string containing only characters ”(” and ”)”. A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters “1” and ”+” between the original characters of the sequence. For example, bracket sequences ”()()” and ”(())” are regular (the resulting expressions are: “(1)+(1)” and “((1+1)+1)”), and ”)(”, ”(” and ”)” are not.

You are given an integer nn. Your goal is to construct and print exactly nn different regular bracket sequences of length 2n2n.

Input

The first line contains one integer tt (1≤t≤501≤t≤50) — the number of test cases.

Each test case consists of one line containing one integer nn (1≤n≤501≤n≤50).

Output

For each test case, print nn lines, each containing a regular bracket sequence of length exactly 2n2n. All bracket sequences you output for a testcase should be different (though they may repeat in different test cases). If there are multiple answers, print any of them. It can be shown that it’s always possible.

Example

input

Copy

3
3
1
3

output

Copy

()()()
((()))
(()())
()
((()))
(())()
()(())

解释与代码

简单构造,我的想法是,先存到数组里,

每次打印完,

把()()()中相邻的)(进行互换

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <stack>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <limits.h>
#include <assert.h>
#include <functional>
#include <numeric>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb          push_back
#define ppb         pop_back
#define lbnd        lower_bound
#define ubnd        upper_bound
#define endl        '\n'
#define mll         map<ll,ll>
#define msl         map<string,ll>
#define mls         map<ll, string>
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x)  for(auto& a : x)
#define pll         pair<ll,ll>
#define vl          vector<ll>
#define vll         vector<pair<ll, ll>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define DEBUG       cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x)  trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x)  cerr << #x << " is " << x << endl;
#define ini(a)      memset(a,0,sizeof(a))
#define ini2(a,b)   memset(a,b,sizeof(a))
//#define rep(i,a,b)  for(int i=a;i<=b;i++)
#define case        ll T;read(T);for(ll Q=1;Q<=T;Q++)
#define lowbit(x)   x&(-x)
#define pr          printf
#define sc          scanf
//#define _           0
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(x) \
    (void)(cout << "L" << __LINE__ \
    << ": " << #x << " = " << (x) << '\n')
#define TIE \
    cin.tie(0);cout.tie(0);\
    ios::sync_with_stdio(false);
//#define long long int

//using namespace __gnu_pbds;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI    = acos(-1.0);
const double eps   = 1e-6;
const int    INF   = 0x3f3f3f3f;
const ll     LLINF = 0x3f3f3f3f3f3f3f3f;

template <typename T>
void read(T &x) {
    x = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
    return;
}

inline void write(ll x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const ll     LN    = 5;
const int    maxn  = 205;
const int    N     = 31;

char ch[2] = {'(',')'};
char cb[10009];

void solve() {
	int n;
	cin>>n;
	for (int i=0; i<n*2; i++) {
		cb[i] = ch[i%2];
	}
	cb[n*2] = '\0';
	for (int i=0; i<n; i++) {
		
		if (i!=0) {
			swap(cb[2*i], cb[2*i-1]);
		}
		cout<<cb<<endl;
	}
}

int main()
{
//	TIE;
//    #ifndef ONLINE_JUDGE
//    freopen ("input.txt","r",stdin);
//    #else
//    #endif
//	solve();
    case{solve();}
//    case{cout<<"Case "<<Q<<":"<<endl;solve();}
//	return ~~(0^_^0);
}

B. Combinatorics Homework

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given four integer values aa, bb, cc and mm.

Check if there exists a string that contains:

  • aa letters ‘A’;
  • bb letters ‘B’;
  • cc letters ‘C’;
  • no other letters;
  • exactly mm pairs of adjacent equal letters (exactly mm such positions ii that the ii-th letter is equal to the (i+1)(i+1)-th one).

Input

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

Each of the next tt lines contains the description of the testcase — four integers aa, bb, cc and mm (1≤a,b,c≤1081≤a,b,c≤108; 0≤m≤1080≤m≤108).

Output

For each testcase print “YES” if there exists a string that satisfies all the requirements. Print “NO” if there are no such strings.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).

Example

input

Copy

3
2 2 1 0
1 1 1 1
1 2 3 2

output

Copy

YES
NO
YES

Note

In the first testcase strings “ABCAB” or “BCABA” satisfy the requirements. There exist other possible strings.

In the second testcase there’s no way to put adjacent equal letters if there’s no letter that appears at least twice.

In the third testcase string “CABBCC” satisfies the requirements. There exist other possible strings.

解释与代码

其实就是几种情况,if else全部写出就行

有两个边界值

例如

6 0 0 3

这样是不行的,不够也不行,超出也不行

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <stack>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <limits.h>
#include <assert.h>
#include <functional>
#include <numeric>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb          push_back
#define ppb         pop_back
#define lbnd        lower_bound
#define ubnd        upper_bound
#define endl        '\n'
#define mll         map<ll,ll>
#define msl         map<string,ll>
#define mls         map<ll, string>
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x)  for(auto& a : x)
#define pll         pair<ll,ll>
#define vl          vector<ll>
#define vll         vector<pair<ll, ll>>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define DEBUG       cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x)  trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x)  cerr << #x << " is " << x << endl;
#define ini(a)      memset(a,0,sizeof(a))
#define ini2(a,b)   memset(a,b,sizeof(a))
//#define rep(i,a,b)  for(int i=a;i<=b;i++)
#define case        ll T;read(T);for(ll Q=1;Q<=T;Q++)
#define lowbit(x)   x&(-x)
#define pr          printf
#define sc          scanf
//#define _           0
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(x) \
    (void)(cout << "L" << __LINE__ \
    << ": " << #x << " = " << (x) << '\n')
#define TIE \
    cin.tie(0);cout.tie(0);\
    ios::sync_with_stdio(false);
//#define long long int

//using namespace __gnu_pbds;

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI    = acos(-1.0);
const double eps   = 1e-6;
const int    INF   = 0x3f3f3f3f;
const ll     LLINF = 0x3f3f3f3f3f3f3f3f;

template <typename T>
void read(T &x) {
    x = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
    return;
}

inline void write(ll x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

const ll     LN    = 5;
const int    maxn  = 205;
const int    N     = 31;

void solve() {
	int a, b, c, m;
	cin>>a>>b>>c>>m;
	int ans = 0;
	if (a!=0)
	ans += a-1;
	if (b!=0)
	ans += b-1;
	if (c!=0)
	ans += c-1;
	if (ans >= m) {
		int d = max(a,max(b,c));
		if (d == a) {
			d -= (b+c);
		} else if (d == b) {
			d -= (a+c);
		} else if (d == c) {
			d -= (b+a);
		}
		if (d-1 <= m) {
			cout<<"YES"<<endl;
		} else {
			cout<<"NO"<<endl;
		}
	} else {
		cout<<"NO"<<endl;
	}
}

int main()
{
//	TIE;
//    #ifndef ONLINE_JUDGE
//    freopen ("input.txt","r",stdin);
//    #else
//    #endif
//	solve();
    case{solve();}
//    case{cout<<"Case "<<Q<<":"<<endl;solve();}
//	return ~~(0^_^0);
}

C. Slay the Dragon

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently, Petya learned about a new game “Slay the Dragon”. As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of nn heroes, the strength of the ii-th hero is equal to aiai.

According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon’s defense is equal to xx, then you have to send a hero with a strength of at least xx to kill it. If the dragon’s attack power is yy, then the total strength of the heroes defending the castle should be at least yy.

The player can increase the strength of any hero by 11 for one gold coin. This operation can be done any number of times.

There are mm dragons in the game, the ii-th of them has defense equal to xixi and attack power equal to yiyi. Petya was wondering what is the minimum number of coins he needs to spend to defeat the ii-th dragon.

Note that the task is solved independently for each dragon (improvements are not saved).

Input

The first line contains a single integer nn (2≤n≤2⋅1052≤n≤2⋅105) — number of heroes.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10121≤ai≤1012), where aiai is the strength of the ii-th hero.

The third line contains a single integer mm (1≤m≤2⋅1051≤m≤2⋅105) — the number of dragons.

The next mm lines contain two integers each, xixi and yiyi (1≤xi≤1012;1≤yi≤10181≤xi≤1012;1≤yi≤1018) — defense and attack power of the ii-th dragon.

Output

Print mm lines, ii-th of which contains a single integer — the minimum number of coins that should be spent to defeat the ii-th dragon.

Example

input

Copy

4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7

output

Copy

1
2
4
0
2

Note

To defeat the first dragon, you can increase the strength of the third hero by 11, then the strength of the heroes will be equal to [3,6,3,3][3,6,3,3]. To kill the dragon, you can choose the first hero.

To defeat the second dragon, you can increase the forces of the second and third heroes by 11, then the strength of the heroes will be equal to [3,7,3,3][3,7,3,3]. To kill the dragon, you can choose a second hero.

To defeat the third dragon, you can increase the strength of all the heroes by 11, then the strength of the heroes will be equal to [4,7,3,4][4,7,3,4]. To kill the dragon, you can choose a fourth hero.

To defeat the fourth dragon, you don’t need to improve the heroes and choose a third hero to kill the dragon.

To defeat the fifth dragon, you can increase the strength of the second hero by 22, then the strength of the heroes will be equal to [3,8,2,3][3,8,2,3]. To kill the dragon, you can choose a second hero.

解释与代码

贪心加二分

不二分会超时

贪心情况:找到第一个大于等于龙攻击力的人,然后判断金额,然后找这个人的前一个人(因为贪心),再次判断即可

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <limits.h>
#include <assert.h>
#include <functional>
#include <numeric>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb          push_back
#define ppb         pop_back
#define lbnd        lower_bound
#define ubnd        upper_bound
#define endl        '\n'
#define trav(a, x)  for(auto& a : x)
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define DEBUG       cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x)  trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x)  cerr << #x << " is " << x << endl;
#define ini(a)      memset(a,0,sizeof(a))
#define case        ll T;read(T);for(ll Q=1;Q<=T;Q++)
#define lowbit(x)   x&(-x)
#define pr          printf
#define sc          scanf
#define _           0
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(x) \
    (void)(cout << "L" << __LINE__ \
    << ": " << #x << " = " << (x) << '\n')
#define TIE \
    cin.tie(0);cout.tie(0);\
    ios::sync_with_stdio(false);
//#define long long int

//using namespace __gnu_pbds;

template <typename T>
void read(T &x) {
    x = 0;
    int f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    x *= f;
    return;
}

inline void write(long long x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    putchar('\n');
}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI    = acos(-1.0);
const double eps   = 1e-6;
const int    INF   = 0x3f3f3f3f;
const ll     LLINF = 0x3f3f3f3f3f3f3f3f;
const int    maxn  = 200009;
const ll     N     = 5;

ll arr[maxn];

void solve(){
	ll n, m, x, y, sum = 0, ans = LLINF;
	cin>>n;
	for (int i=0; i<n; i++) cin>>arr[i], sum += arr[i];
	sort(arr, arr+n);
	cin>>m;
	while (m--) {
		ans = LLINF;
		cin>>x>>y;
		ll p = lbnd(arr, arr+n, x) - arr;
		if (p < n) {
			ll sw = sum - arr[p];
			if (y - sw > 0) {
				ans = min(ans, y - sw);
			} else {
				ans = min(ans, 0LL);
			}
		}
		if (p != 0) {
			ll sw = sum - arr[p-1];
			ll ww = x - arr[p-1];
			if (ww < 0) {
				ww = 0;
			}
			if (y - sw > 0) {
				ans = min(ans, y - sw + ww);
			} else {
				ans = min(ans, (ll)ww);
			}
		}
		cout<<ans<<endl;
	}
}

int main()
{
	TIE;
    #ifndef ONLINE_JUDGE
//    freopen ("in.txt" , "r", stdin );
//    freopen ("out.txt", "w", stdout);
    #else
    #endif
	solve();
//    case{solve();}
//    case{cout<<"Case "<<Q<<":"<<endl;solve();}
	return ~~(0^_^0);
}