「Educational Codeforces Round #51」题解

A. Vasya And Password

题目描述

Vasya came up with a password to register for EatForces — a string ss . The password in EatForces should be a string, consisting of lowercase and uppercase Latin letters and digits.

But since EatForces takes care of the security of its users, user passwords must contain at least one digit, at least one uppercase Latin letter and at least one lowercase Latin letter. For example, the passwords abaCABA12, Z7q and 3R24m are valid, and the passwords qwerty, qwerty12345 and Password are not.

A substring of string ss is a string x=slsl+1sl+len1(1ls,0lensl+1)x = s_l s_{l + 1} \cdots s_{l + len - 1} (1 \le l \le |s|, 0 \le len \le |s| - l + 1) . lenlen is the length of the substring. Note that the empty string is also considered a substring of ss , it has the length 00.

Vasya's password, however, may come too weak for the security settings of EatForces. He likes his password, so he wants to replace some its substring with another string of the same length in order to satisfy the above conditions. This operation should be performed exactly once, and the chosen string should have the minimal possible length.

Note that the length of ss should not change after the replacement of the substring, and the string itself should contain only lowercase and uppercase Latin letters and digits.

输入输出格式

输入格式

The first line contains a single integer TT ( 1T1001 \le T \le 100 ) — the number of testcases.

Each of the next TT lines contains the initial password s ( 3s1003 \le |s| \le 100 ) , consisting of lowercase and uppercase Latin letters and digits.

Only T=1T = 1 is allowed for hacks.

输出格式

For each testcase print a renewed password, which corresponds to given conditions.

The length of the replaced substring is calculated as following: write down all the changed positions. If there are none, then the length is 00 . Otherwise the length is the difference between the first and the last changed position plus one. For example, the length of the changed substring between the passwords abcdef \rightarrow a7cdEf is 44 , because the changed positions are 22 and 55 , thus (52)+1=4(5 - 2) + 1 = 4.

It is guaranteed that such a password always exists.

If there are several suitable passwords — output any of them.

输入输出样例

输入样例#1

1
2
3
2
abcDCE
htQw27

输出样例#1

1
2
abcD4E
htQw27

说明

In the first example Vasya's password lacks a digit, he replaces substring C with 44 and gets password abcD4E. That means, he changed the substring of length 11.

In the second example Vasya's password is ok from the beginning, and nothing has to be changed. That is the same as replacing the empty substring with another empty substring (length 00).

题解

直接模拟.

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

const double eps = 1e-8;
const double pi = acos(-1.0);

typedef long long ll;
typedef long double lb;
typedef std::pair <int, int> pii;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n", __FUNCTION__, __LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n", __FUNCTION__, __LINE__)

#define All(x) x.begin(), x.end()

#define is ==
#define endl '\n'

#define up(a,b,c) for (register int a = b; a <= c; a++)
#define down(a,b,c) for (register int a = c; a >= b; a--)
#define lup(a,b,c) for (register ll a = b; a <= c; a++)
#define ldown(a,b,c) for (register ll a = c; a >= b; a--)

inline int SlowRead () {
register char ch = 0;
register int data = 0, f = 1;
while (ch != '-' and (ch < '0' || ch > '9')) ch = getchar();
if (ch is '-') f = -1, ch = getchar();
while (ch >= '0' and ch <= '9') {
data = data * 10 + ch - '0';
ch = getchar();
}
return data * f;
}

bool is_number (char c) {
if(c >= '0' and c <= '9') return true;
return false;
}

bool is_big (char c) {
if(c >= 'A' and c <= 'Z') return true;
return false;
}

bool is_small (char c) {
if(c >= 'a' and c <= 'z') return true;
return false;
}

int t;
std::string s;

int main(int argc, char const *argv[]) {
t = SlowRead();

int len;

int f1, f2, f3;
int ff1, ff2, ff3;

while (t --> 0 and std::cin >> s) {
len = s.size();
f1 = 0, f2 = 0, f3 = 0;

for (register int i = 0; i < len; i++) {
if (is_number( s[i] )) f1++, ff1 = i;
else if (is_big( s[i] )) f2++, ff2 = i;
else if (is_small( s[i] )) f3++, ff3 = i;
}

if (f1 and f2 and f3) s = s;
else if (f3 == len) s[0] = '1', s[1] = 'A';
else if (f2 == len) s[0] = '1', s[1] = 'a';
else if (f1 == len) s[0] = 'a', s[1] = 'A';
else if (f1 == 0) s[f2 == 1 ? ff3 : ff2] = '1';
else if (f2 == 0) s[f1 == 1 ? ff3 : ff1] = 'A';
else if (f3 == 0) s[f2 == 1 ? ff1 : ff2] = 'A';

for (register int i = 0; i < len; i++) putchar(s[i]);

printf("\n");
}

return 0;
}

B. Relatively Prime Pairs

题目描述

You are given a set of all integers from ll to rr inclusive, l<rl < r , (rl+1)3105(r - l + 1) \le 3 \cdot 10^5 and (rl)(r - l) is always odd.

You want to split these numbers into exactly rl+12\frac{r - l + 1}{2} pairs in such a way that for each pair (i,j)(i, j) the greatest common divisor of ii and jj is equal to 11 . Each number should appear in exactly one of the pairs.

Print the resulting pairs or output that no solution exists. If there are multiple solutions, print any of them.

输入输出格式

输入格式

The only line contains two integers ll and rr ( 1l<r10181 \le l < r \le 10^{18} rl+13105r - l + 1 \le 3 \cdot 10^5, (rl)(r - l) is odd).

输出格式

If any solution exists, print "YES" in the first line. Each of the next rl+12\frac{r - l + 1}{2} lines should contain some pair of integers. GCD of numbers in each pair should be equal to 11. All (rl+1)(r - l + 1) numbers should be pairwise distinct and should have values from ll to rr inclusive.

If there are multiple solutions, print any of them.

If there exists no solution, print NO.

输入输出样例

输入样例 #1

1
1 8

输出样例 #1

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

题解

氵题

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

const double eps = 1e-8;
const double pi = acos(-1.0);

typedef long long ll;
typedef long double lb;
typedef std::pair <int, int> pii;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n", __FUNCTION__, __LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n", __FUNCTION__, __LINE__)

#define All(x) x.begin(), x.end()

#define is ==
#define endl '\n'

#define up(a,b,c) for (register int a = b; a <= c; a++)
#define down(a,b,c) for (register int a = c; a >= b; a--)
#define lup(a,b,c) for (register ll a = b; a <= c; a++)
#define ldown(a,b,c) for (register ll a = c; a >= b; a--)

inline int SlowRead () {
register char ch = 0;
register int data = 0, f = 1;
while (ch != '-' and (ch < '0' || ch > '9')) ch = getchar();
if (ch is '-') f = -1, ch = getchar();
while (ch >= '0' and ch <= '9') {
data = data * 10 + ch - '0';
ch = getchar();
}
return data * f;
}

ll l, r;

int main(int argc, char const *argv[]) {
scanf("%lld%lld", &l, &r);
printf("YES\n");
for (register ll i = l; i <= r; i += 2) {
printf("%lld %lld\n", i, i + 1);
}
return 0;
}

先写到这里辣QAQ

坚持原创技术分享,您的支持将鼓励我继续创作!