# # Codeforces Round 660 (CF1388) 题解

## # Problem A - Captain Flint and Crew Recruitment

### # 题解

#include <cstdio>
#include <iostream>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
if (n <= 30) {
printf("NO\n");
return;
}
printf("YES\n");
if (n == 36 || n == 40 || n == 44)
printf("6 10 15 %d\n", n - 31);
else
printf("6 10 14 %d\n", n - 30);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem B - Captain Flint and a Long Voyage

### # 题解

#include <cstdio>
#include <iostream>
#define MOD 1000000007

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
int m = (n - 1) / 4 + 1;
string a(n - m, '9');
string b(m, '8');
string ans = a + b;
printf("%s\n", ans.c_str());
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem C - Uncle Bogdan and Country Happiness

### # 题解

$happy[i] - (cnt[i] - happy[i]) = h_i$

$happy[i]=\frac{h_i+cnt[i]}{2}$

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
bool ok = true;
int n, m;
vector<int> p, h, cnt, happy;
void check(int u, int pre) {
int lo = 0;
cnt[u] = p[u];
for (int v : adj[u]) {
if (v != pre) {
check(v, u);
cnt[u] += cnt[v];
lo += happy[v];
}
}
if ((h[u] + cnt[u]) % 2 != 0)
ok = false;
happy[u] = (h[u] + cnt[u]) / 2;
if (happy[u] < lo || happy[u] > cnt[u])
ok = false;
}

public:
void solve() {
adj = vector<vector<int>>(n + 1);
p = vector<int>(n + 1);
h = vector<int>(n + 1);
cnt = vector<int>(n + 1);
happy = vector<int>(n + 1);
for (int i = 1; i <= n; ++i)
for (int i = 1; i <= n; ++i)
for (int i = 1; i < n; ++i) {
int u, v;
}
check(1, 0);
printf(ok ? "YES\n" : "NO\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
while (t--) {
Solution solution = Solution();
solution.solve();
}
}

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

## # Problem D - Captain Flint and Treasure

### # 题目描述

$n$个数$a_1\cdots a_n$，以及对应的$n$个序号$b_1\cdots b_n$。要求对$n$个数按照某一顺序依次操作一次，使得得到的总和最大，求出这个总和并给出这一顺序。

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
int n;
vector<ll> a;
vector<int> b, in, left, right;

public:
void solve() {
a = vector<ll>(n + 1);
b = vector<int>(n + 1);
in = vector<int>(n + 1);
for (int i = 1; i <= n; ++i)
for (int i = 1; i <= n; ++i) {
if (b[i] != -1)
in[b[i]]++;
}
queue<int> q;
ll result = 0;
for (int i = 1; i <= n; ++i) {
if (in[i] == 0)
q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
if (a[u] < 0)
right.emplace_back(u);
else {
left.emplace_back(u);
if (b[u] != -1)
a[b[u]] += a[u];
}
result += a[u];
if (b[u] != -1) {
in[b[u]]--;
if (in[b[u]] == 0)
q.push(b[u]);
}
}
printf("%lld\n", result);
reverse(right.begin(), right.end());
for (int i : left)
printf("%d ", i);
for (int i : right)
printf("%d ", i);
printf("\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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

## # Problem E - Uncle Bogdan and Projections

### # 题目描述

X轴上方有$n$条互不相交且平行于X轴的线段。现在要求将这些线段互不相交地沿同一方向投影到$X$轴上，问最后得到的投影在X轴上的左端点和右端点间的距离最短为多少。

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

struct Line {
int l, r, y;
};

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }

struct Fraction {
int a, b;
Fraction(int a, int b) {
if (b < 0) {
a = -a;
b = -b;
}
int g = gcd(abs(a), abs(b));
this->a = a / g;
this->b = b / g;
};
bool operator<(const Fraction &other) const {
return (ll)a * other.b < (ll)b * other.a;
}
bool operator<=(const Fraction &other) const {
return (ll)a * other.b <= (ll)b * other.a;
}
bool operator>(const Fraction &other) const {
return (ll)a * other.b > (ll)b * other.a;
}
bool operator>=(const Fraction &other) const {
return (ll)a * other.b >= (ll)b * other.a;
}
bool operator!=(const Fraction &other) const {
return (ll)a * other.b != (ll)b * other.a;
}
bool operator==(const Fraction &other) const {
return (ll)a * other.b == (ll)b * other.a;
}
};

class Solution {
vector<pair<Fraction, Fraction>> seg;

Fraction theta(int x1, int x2, int dy) { return Fraction(x1 - x2, dy); }

void calc(Line a, Line b) {
if (a.y == b.y)
return;
if (a.y < b.y)
swap(a, b);
Fraction t1 = theta(a.l, b.r, a.y - b.y);
Fraction t2 = theta(a.r, b.l, a.y - b.y);
if (t1 > t2)
swap(t1, t2);
seg.emplace_back(t1, t2);
}

public:
void solve() {
int n;
vector<Line> a(n);
for (int i = 0; i < n; ++i)
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
calc(a[i], a[j]);
double ans = 1e18;
sort(seg.begin(), seg.end());
vector<pair<Fraction, Fraction>> t;
const Fraction magic(1, MOD);
Fraction l0 = magic, r0 = magic;
for (auto &[l, r] : seg) {
if (l >= r0) {
if (r0 != magic)
t.emplace_back(l0, r0);
l0 = l;
r0 = r;
} else {
if (l0 == magic) {
l0 = l;
r0 = r;
} else
r0 = max(r0, r);
}
}
if (l0 != magic)
t.emplace_back(l0, r0);
vector<Fraction> vt;
for (auto &[l, r] : t)
vt.emplace_back(l), vt.emplace_back(r);
if (vt.empty())
vt.emplace_back(0, 1);
for (Fraction d : vt) {
double l = 1e18, r = -1e18;
for (auto &e : a) {
l = min(l, (double)-d.a / d.b * e.y + e.l);
r = max(r, (double)-d.a / d.b * e.y + e.r);
}
ans = min(ans, r - l);
}
printf("%.9f", ans);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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