Codeforces Edu. Round #102 (Div. 2) [Personal Summary]

这场前 4 题难度不高,后 3 题抽时间看一下。

My Status

A B C D E F G
O O O O Ø Ø Ø

A. Replacing Elements

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

You have an array a1,a2,,ana_1, a_2, \dots, a_n. All aia_i are positive integers.

In one step you can choose three distinct indices ii, jj, and kk (iji \neq j; iki \neq k; jkj \neq k) and assign the sum of aja_j and aka_k to aia_i, i. e. make ai=aj+aka_i = a_j + a_k.

Can you make all aia_i lower or equal to dd using the operation above any number of times (possibly, zero)?

Input

The first line contains a single integer tt (1t20001 \le t \le 2000) — the number of test cases.

The first line of each test case contains two integers nn and dd (3n1003 \le n \le 100; 1d1001 \le d \le 100) — the number of elements in the array aa and the value dd.

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1001 \le a_i \le 100) — the array aa.

Output

For each test case, print YES\texttt{YES}, if it’s possible to make all elements aia_i less or equal than dd using the operation above. Otherwise, print NO\texttt{NO}.

You may print each letter in any case (for example, YES\texttt{YES}, Yes\texttt{Yes}, yes\texttt{yes}, yEs\texttt{yEs} will all be recognized as positive answer).

Example

Input
1
2
3
4
5
6
7
3
5 3
2 3 2 5 4
3 4
2 4 4
5 4
2 1 5 3 6
Output
1
2
3
NO
YES
YES

Note

In the first test case, we can prove that we can’t make all ai3a_i \le 3.

In the second test case, all aia_i are already less or equal than d=4d = 4.

In the third test case, we can, for example, choose i=5i = 5, j=1j = 1, k=2k = 2 and make a5=a1+a2=2+1=3a_5 = a_1 + a_2 = 2 + 1 = 3. Array aa will become [2,1,5,3,3][2, 1, 5, 3, 3].

After that we can make a3=a5+a2=3+1=4a_3 = a_5 + a_2 = 3 + 1 = 4. Array will become [2,1,4,3,3][2, 1, 4, 3, 3] and all elements are less or equal than d=4d = 4.

Solution

先检查是否有所有 aida_i \leq d 成立。

若不成立,则将 aa 按升序排序,检查是否有 a1+a2da_1 + a_2 \leq d。若成立,则可用 a1+a2a_1 + a_2 替换每个大于 dd 的值,存在可行方案;否则不存在可行方案。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*************************************************************/
#if __cplusplus < 201103L
// For jury which unsupports C++11

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <queue>
using namespace std;

#define ffor(_var, _begin, _end, ...) \
for(__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__)
#define rfor(_var, _rbegin, _rend, ...) \
for(__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__)
#define cfor(_var, _cbegin, _cend, ...) \
for(__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__)

#else

#include <bits/stdc++.h>
using namespace std;

#define ffor(_var, _begin, _end, ...) \
for(decay<decltype(_end)>::type _var = _begin; _var < _end; __VA_ARGS__)
#define rfor(_var, _rbegin, _rend, ...) \
for(decay<decltype(_rbegin)>::type _var = _rbegin; _var > _rend; __VA_ARGS__)

#endif

typedef long long ll;
typedef long double ld;
#define ABS(x) ((x) > 0 ? (x) : -(x))

const int INF = 0x3f3f3f3f;

// #define __DEBUG__

#ifdef __DEBUG__
#if defined _WIN32
#define _WINDEBUG
#include <windows.h>
inline std::ostream& __YELLOW__(std::ostream &s) {
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY);
return s;
}
inline std::ostream& __WHITE__(std::ostream &s) {
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
return s;
}
inline std::ostream& __RED__(std::ostream &s)
{
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_RED|FOREGROUND_INTENSITY);
return s;
}
#elif defined __linux__
#define _LINUXDEBUG
#define __YELLOW__ "\033[33;1m"
#define __WHITE__ "\033[0m"
#endif
#endif

#if defined _WINDEBUG || defined _LINUXDEBUG
#define ar2vec(_begin, _end) \
vector<decay<iterator_traits<decltype(_begin)>::value_type>::type>(_begin, _end)
#define debug(x...) \
do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0)
void err() { cout << __WHITE__ << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' '; err(x...); }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for(auto& v : a) cout << __RED__ << v << __YELLOW__ << ' '; err(x...); }
#else
#define ar2vec(...)
#define debug(...)
#endif
/*************************************************************/

const int MAXN = 100;
int a[MAXN + 10];

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);

int t = 0;
cin >> t;
while(t--) {
int n = 0, d = 0;
cin >> n >> d;

for(int i = 1; i <= n; i++)
cin >> a[i];

bool flag = true;
for(int i = 1; i <= n; i++)
if(a[i] > d) {
flag = false;
break;
}

if(flag) {
cout << "YES" << endl;
continue;
}

sort(a + 1, a + n + 1);
if(a[1] + a[2] > d) cout << "NO" << endl;
else cout << "YES" << endl;
}

return 0;
}

B. String LCM

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

Let’s define a multiplication operation between a string aa and a positive integer xx: axa \cdot x is the string that is a result of writing xx copies of aa one after another. For example, “abc\texttt{abc} 2 =\cdot~2~=abcabc\texttt{abcabc}”, “a\texttt{a} 5 =\cdot~5~=aaaaa\texttt{aaaaa}”.

A string aa is divisible by another string bb if there exists an integer xx such that bx=ab \cdot x = a. For example, “abababab\texttt{abababab}” is divisible by “ab\texttt{ab}”, but is not divisible by “ababab\texttt{ababab}” or “aa\texttt{aa}”.

LCM of two strings ss and tt (defined as LCM(s,t)LCM(s, t)) is the shortest non-empty string that is divisible by both ss and tt.

You are given two strings ss and tt. Find LCM(s,t)LCM(s, t) or report that it does not exist. It can be shown that if LCM(s,t)LCM(s, t) exists, it is unique.

Input

The first line contains one integer qq (1q20001 \le q \le 2000) — the number of test cases.

Each test case consists of two lines, containing strings ss and tt (1s,t201 \le |s|, |t| \le 20). Each character in each of these strings is either ‘a\texttt{a}’ or ‘b\texttt{b}’.

Output

For each test case, print LCM(s,t)LCM(s, t) if it exists; otherwise, print -1\texttt{-1} . It can be shown that if LCM(s,t)LCM(s, t) exists, it is unique.

Example

Input
1
2
3
4
5
6
7
3
baba
ba
aa
aaa
aba
ab
Output
1
2
3
baba
aaaaaa
-1

Note

In the first test case, “baba\texttt{baba}” = “baba\texttt{baba} 1 =\cdot~1~=ba\texttt{ba} 2\cdot~2.

In the second test case, “aaaaaa\texttt{aaaaaa}” = “aa\texttt{aa} 3 =\cdot~3~=aaa\texttt{aaa} 2\cdot~2.

Solution

注意到 sstt 的长度均不超过 2020,因此直接模拟即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/*************************************************************/
#if __cplusplus < 201103L
// For jury which unsupports C++11

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <queue>
using namespace std;

#define ffor(_var, _begin, _end, ...) \
for(__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__)
#define rfor(_var, _rbegin, _rend, ...) \
for(__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__)
#define cfor(_var, _cbegin, _cend, ...) \
for(__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__)

#else

#include <bits/stdc++.h>
using namespace std;

#define ffor(_var, _begin, _end, ...) \
for(decay<decltype(_end)>::type _var = _begin; _var < _end; __VA_ARGS__)
#define rfor(_var, _rbegin, _rend, ...) \
for(decay<decltype(_rbegin)>::type _var = _rbegin; _var > _rend; __VA_ARGS__)

#endif

typedef long long ll;
typedef long double ld;
#define ABS(x) ((x) > 0 ? (x) : -(x))

const int INF = 0x3f3f3f3f;

// #define __DEBUG__

#ifdef __DEBUG__
#if defined _WIN32
#define _WINDEBUG
#include <windows.h>
inline std::ostream& __YELLOW__(std::ostream &s) {
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY);
return s;
}
inline std::ostream& __WHITE__(std::ostream &s) {
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
return s;
}
inline std::ostream& __RED__(std::ostream &s)
{
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_RED|FOREGROUND_INTENSITY);
return s;
}
#elif defined __linux__
#define _LINUXDEBUG
#define __YELLOW__ "\033[33;1m"
#define __WHITE__ "\033[0m"
#endif
#endif

#if defined _WINDEBUG || defined _LINUXDEBUG
#define ar2vec(_begin, _end) \
vector<decay<iterator_traits<decltype(_begin)>::value_type>::type>(_begin, _end)
#define debug(x...) \
do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0)
void err() { cout << __WHITE__ << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' '; err(x...); }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for(auto& v : a) cout << __RED__ << v << __YELLOW__ << ' '; err(x...); }
#else
#define ar2vec(...)
#define debug(...)
#endif
/*************************************************************/

string getsub(string &s) {
int n = s.length();
for(int i = 1; i <= n; i++) {
if(n % i) continue;

string sub = s.substr(0, i);
bool flag = true;
for(int j = i; j < n; j += i) {
if(sub != s.substr(j, i)) {
flag = false;
break;
}
}
if(flag)
return sub;
}
return string("");
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);

int q = 0;
cin >> q;
while(q--) {
string s, t;
cin >> s >> t;

string s_sub = getsub(s);
string t_sub = getsub(t);

debug(s_sub);
debug(t_sub);

if(s_sub != t_sub)
cout << -1 << endl;
else {
int s_num = s.length() / s_sub.length();
int t_sum = t.length() / t_sub.length();
int lcd = s_num * t_sum / __gcd(s_num, t_sum);
debug(s_num, t_sum, lcd);

for(int i = 1; i < lcd; i++)
s_sub += t_sub;
cout << s_sub << endl;
}
}

return 0;
}

C. No More Inversions

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

You have a sequence aa with nn elements 1,2,3,,k1,k,k1,k2,,k(nk)1, 2, 3, \dots, k - 1, k, k - 1, k - 2, \dots, k - (n - k) (kn<2kk \le n < 2k).

Let’s call as inversion in aa a pair of indices i<ji < j such that a[i]>a[j]a[i] > a[j].

Suppose, you have some permutation pp of size kk and you build a sequence bb of size nn in the following manner: b[i]=p[a[i]]b[i] = p[a[i]].

Your goal is to find such permutation pp that the total number of inversions in bb doesn’t exceed the total number of inversions in aa, and bb is lexicographically maximum .

Small reminder: the sequence of kk integers is called a permutation if it contains all integers from 11 to kk exactly once.

Another small reminder: a sequence ss is lexicographically smaller than another sequence tt, if either ss is a prefix of tt, or for the first ii such that sitis_i \ne t_i, si<tis_i < t_i holds (in the first position that these sequences are different, ss has smaller number than tt).

Input

The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of test cases.

The first and only line of each test case contains two integers nn and kk (kn<2kk \le n < 2k; 1k1051 \le k \le 10^5) — the length of the sequence aa and its maximum.

It’s guaranteed that the total sum of kk over test cases doesn’t exceed 10510^5.

Output

For each test case, print kk integers — the permutation pp which maximizes bb lexicographically without increasing the total number of inversions.

It can be proven that pp exists and is unique.

Example

Input
1
2
3
4
5
4
1 1
2 2
3 2
4 3
Output
1
2
3
4
1 
1 2
2 1
1 3 2

Note

In the first test case, the sequence a=[1]a = [1], there is only one permutation p=[1]p = [1].

In the second test case, the sequence a=[1,2]a = [1, 2]. There is no inversion in aa, so there is only one permutation p=[1,2]p = [1, 2] which doesn’t increase the number of inversions.

In the third test case, a=[1,2,1]a = [1, 2, 1] and has 11 inversion. If we use p=[2,1]p = [2, 1], then b=[p[a[1]],p[a[2]],p[a[3]]]=[2,1,2]b = [p[a[1]], p[a[2]], p[a[3]]] = [2, 1, 2] and also has 11 inversion.

In the fourth test case, a=[1,2,3,2]a = [1, 2, 3, 2], and since p=[1,3,2]p = [1, 3, 2] then b=[1,3,2,3]b = [1, 3, 2, 3]. Both aa and bb have 11 inversion and bb is the lexicographically maximum.

Solution

考虑到 aa 中的逆序列数目共有 i=1nk=(nk)(nk+1)2\sum\limits_{i=1}^{n-k} = \dfrac{(n-k)(n-k+1)}{2} 个,全部由序列的后半部分 k,(k1),,k(nk)k,(k-1),\cdots,k-(n-k) 所贡献,因此只需要保证 bb 中的逆序列构造方式和 aa 相同即可。

因此构造 p=[1,2,,(2kn1),k,(k1),,k(nk)]p = [1, 2, \cdots, (2k-n-1),k,(k-1),\cdots,k-(n-k)] 即可。容易发现 bb 序列中的逆序列部分和 pp 相同。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/*************************************************************/
#if __cplusplus < 201103L
// For jury which unsupports C++11

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <queue>
using namespace std;

#define ffor(_var, _begin, _end, ...) \
for(__typeof__(_end) _var = _begin; _var < _end; __VA_ARGS__)
#define rfor(_var, _rbegin, _rend, ...) \
for(__typeof__(_rbegin) _var = _rbegin; _var > _rend; __VA_ARGS__)
#define cfor(_var, _cbegin, _cend, ...) \
for(__typeof__(_cend) _var = _cbegin; _var != _cend; __VA_ARGS__)

#else

#include <bits/stdc++.h>
using namespace std;

#define ffor(_var, _begin, _end, ...) \
for(decay<decltype(_end)>::type _var = _begin; _var < _end; __VA_ARGS__)
#define rfor(_var, _rbegin, _rend, ...) \
for(decay<decltype(_rbegin)>::type _var = _rbegin; _var > _rend; __VA_ARGS__)

#endif

typedef long long ll;
typedef long double ld;
#define ABS(x) ((x) > 0 ? (x) : -(x))

const int INF = 0x3f3f3f3f;

// #define __DEBUG__

#ifdef __DEBUG__
#if defined _WIN32
#define _WINDEBUG
#include <windows.h>
inline std::ostream& __YELLOW__(std::ostream &s) {
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_GREEN|FOREGROUND_RED|FOREGROUND_INTENSITY);
return s;
}
inline std::ostream& __WHITE__(std::ostream &s) {
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_RED|FOREGROUND_GREEN|FOREGROUND_BLUE);
return s;
}
inline std::ostream& __RED__(std::ostream &s)
{
HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hStdout,
FOREGROUND_RED|FOREGROUND_INTENSITY);
return s;
}
#elif defined __linux__
#define _LINUXDEBUG
#define __YELLOW__ "\033[33;1m"
#define __WHITE__ "\033[0m"
#endif
#endif

#if defined _WINDEBUG || defined _LINUXDEBUG
#define ar2vec(_begin, _end) \
vector<decay<iterator_traits<decltype(_begin)>::value_type>::type>(_begin, _end)
#define debug(x...) \
do { cout << __YELLOW__ << #x << " -> "; err(x); } while(0)
void err() { cout << __WHITE__ << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << __RED__ << a << __YELLOW__ << ' '; err(x...); }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for(auto& v : a) cout << __RED__ << v << __YELLOW__ << ' '; err(x...); }
#else
#define ar2vec(...)
#define debug(...)
#endif
/*************************************************************/

const int MAXN = 1e5;
int p[MAXN + 10];

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);

int t = 0;
cin >> t;
while(t--) {
int n = 0, k = 0;
cin >> n >> k;

for(int i = 1; i <= 2 * k - n - 1; i++)
p[i] = i;
for(int i = 2 * k - n, cnt = k; i <= k; i++)
p[i] = cnt--;
for(int i = 1; i <= k; i++)
if(i == k) cout << p[i] << endl;
else cout << p[i] << " ";
}

return 0;
}

D. Program

Description

Time Limit: 2 seconds
Memory Limit: 256 megabytes

You are given a program that consists of nn instructions. Initially a single variable xx is assigned to 00. Afterwards, the instructions are of two types:

  • increase xx by 11;
  • decrease xx by 11.

You are given mm queries of the following format:

  • query ll rr — how many distinct values is xx assigned to if all the instructions between the ll-th one and the rr-th one inclusive are ignored and the rest are executed without changing the order?

Input

The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of testcases.

Then the description of tt testcases follows.

The first line of each testcase contains two integers nn and mm (1n,m21051 \le n, m \le 2 \cdot 10^5) — the number of instructions in the program and the number of queries.

The second line of each testcase contains a program — a string of nn characters: each character is either ‘+\texttt{+}’ or ‘-\texttt{-}’ — increment and decrement instruction, respectively.

Each of the next mm lines contains two integers ll and rr (1lrn1 \le l \le r \le n) — the description of the query.

The sum of nn over all testcases doesn’t exceed 21052 \cdot 10^5. The sum of mm over all testcases doesn’t exceed 21052 \cdot 10^5.

Output

For each testcase print mm integers — for each query ll, rr print the number of distinct values variable xx is assigned to if all the instructions between the ll-th one and the rr-th one inclusive are ignored and the rest are executed without changing the order.

Example

Input
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
8 4
-+--+--+
1 8
2 8
2 5
1 1
4 10
+-++
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4
Output
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
2
4
4
3
3
4
2
3
2
1
2
2
2

Note

The instructions that remain for each query of the first testcase are:

  1. empty program — xx was only equal to 00;
  2. -\texttt{-}” — xx had values 00 and 1-1;
  3. ---+\texttt{---+}” — xx had values 00, 1-1, 2-2, 3-3, 2-2 — there are 44 distinct values among them;
  4. +--+--+\texttt{+--+--+}” — the distinct values are 11, 00, 1-1, 2-2.

Solution

首先考虑到在一段连续的指令序列中,xx 的赋值序列是连续的;这是因为每条指令只能为 xx11 或者减 11。因此,只需要维护该段指令序列中 xx 的最大值和最小值。

考虑维护一个如下的数据结构:

1
2
3
4
5
6
7
8
9
10
11
struct Data {
int maxx, minn, add;

Data(int _max = 0, int _min = 0, int _add = 0):
maxx(_max), minn(_min), add(_add) {}
Data operator + (const Data &d) {
return Data(max(maxx, add + d.maxx), min(minn, add + d.minn),
add + d.add);
}
};
#endif

其中 maxxminn 分别为在指令序列此处 xx 的最大值和最小值,add 代表

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.