3 easy problems, but the rest are hard.
3 cases:
The case that might got you is the case of rectangles touching on the y-axis. Try this case:
1
4 200 100
20 80 10 1
80 20 20 0
20 90 120 1
30 8 150 0
The answer is 60.198039.
1#include <bits/stdc++.h>
2
3using namespace std;
4
5#define N 111
6#define MAX 1e18
7
8typedef long long ll;
9
10struct Pt {
11 int x, y;
12};
13
14struct Rect {
15 Pt upperLeft, lowerRight;
16 int k;
17};
18
19double dist(int x1, int y1, int x2, int y2)
20{
21 ll dx = x2 - x1;
22 ll dy = y2 - y1;
23 return sqrt(dx * dx + dy * dy);
24}
25
26void solve()
27{
28 int n, l, u;
29 scanf("%d %d %d", &n, &l, &u);
30
31 // read
32 double m[N][N];
33 for (int i = 0; i < N; i++)
34 for (int j = 0; j < N; j++)
35 m[i][j] = (i == j ? 0 : MAX);
36
37 vector<Rect> rect;
38 rect.push_back({{0, 0}, {u, 0}, 0}); // bottom
39 rect.push_back({{0, l}, {u, l}, 0}); // top
40 m[0][1] = m[1][0] = l;
41
42 for (int i = 0; i < n; i++) {
43 int h, w, d, k;
44 scanf("%d %d %d %d", &h, &w, &d, &k);
45
46 if (k == 0) {
47 Pt upperLeft = {0, h + d};
48 Pt lowerRight = {w, d};
49 rect.push_back({upperLeft, lowerRight, k});
50 } else {
51 Pt upperLeft = {u - w, h + d};
52 Pt lowerRight = {u, d};
53 rect.push_back({upperLeft, lowerRight, k});
54 }
55
56 m[i + 2][1] = m[1][i + 2] = l - h - d;
57 m[i + 2][0] = m[0][i + 2] = d;
58 }
59
60 // build
61 int sz = rect.size();
62 for (int i = 2; i < sz; i++) {
63 for (int j = 2; j < sz; j++) {
64 if (i == j)
65 continue;
66
67 int &ax = rect[i].upperLeft.x;
68 int &ay = rect[i].upperLeft.y;
69 int &bx = rect[i].lowerRight.x;
70 int &by = rect[i].lowerRight.y;
71 int &ki = rect[i].k;
72
73 int &cx = rect[j].upperLeft.x;
74 int &cy = rect[j].upperLeft.y;
75 int &dx = rect[j].lowerRight.x;
76 int &dy = rect[j].lowerRight.y;
77 int &kj = rect[j].k;
78
79 double val;
80 if (ax <= cx && cx <= bx) { // case1 - 1
81 if (ki != kj && cx == bx && by <= cy && cy <= ay) // touching case
82 val = 0;
83 else
84 val = min(abs(ay - dy), abs(by - cy));
85 } else if (ax <= dx && dx <= bx) { // case1 - 2
86 if (ki != kj && dx == bx && by <= dy && dy <= ay) // touching case
87 val = 0;
88 else
89 val = min(abs(ay - dy), abs(by - cy));
90 } else if (by <= cy && cy <= ay) { // case2 - 1
91 val = abs(bx - cx);
92 } else if (by <= dy && dy <= ay) { // case2 - 2
93 val = abs(bx - cx);
94 } else { // case3
95 val = min(dist(bx, ay, cx, dy), dist(bx, by, cx, cy));
96 /*
97 if(ay < dy) {
98 val = dist(bx, ay, cx, dy);
99 } else {
100 val = dist(bx, by, cx, cy);
101 }
102 */
103 }
104
105 m[i][j] = min(m[i][j], val);
106 m[j][i] = min(m[j][i], val);
107 //printf("%d %d %.6f\n", i, j, m[i][j]);
108 //printf("%d %d, %d %d, %d %d, %d %d\n", ax, ay, bx, by, cx, cy, dx, dy);
109 }
110 }
111
112 // solve
113 for (int k = 0; k < sz; k++)
114 for (int i = 0; i < sz; i++)
115 for (int j = 0; j < sz; j++) {
116 if (m[i][j] > 1e9)
117 continue;
118 m[i][j] = min(m[i][j], m[i][k] + m[k][j]);
119 }
120
121 printf("%.6f\n", m[0][1]);
122}
123
124int main()
125{
126 freopen("street.in", "r", stdin);
127
128 int ncase;
129 scanf("%d", &ncase);
130
131 while (ncase--)
132 solve();
133
134 return 0;
135}$C(n, m)$
1lude<bits / stdc++.h>
2
3using namespace std;
4
5typedef long long ll;
6ll dp[30][30];
7ll C(ll a, ll b)
8{
9 if (dp[a][b] != -1)
10 return dp[a][b];
11 ll ans = 1;
12 for (int i = 1; i <= b; i++) {
13 ans = ans * (a - i + 1);
14 ans = ans / i;
15 }
16 return dp[a][b] = ans;
17}
18
19void solve()
20{
21 int n, m;
22 scanf("%d %d", &n, &m);
23
24 printf("%lld\n", C(n, m));
25}
26
27int main()
28{
29 freopen("popcorn.in", "r", stdin);
30 int ncase;
31 scanf("%d", &ncase);
32 memset(dp, -1, sizeof(dp));
33 while (ncase--)
34 solve();
35
36 return 0;
37}BFS. Add edges, but reverse them!
1#include <bits/stdc++.h>
2
3using namespace std;
4
5#define N 100010
6vector<int> g[N];
7
8void solve()
9{
10 int n;
11 scanf("%d", &n);
12
13 for (int i = 0; i < n; i++)
14 g[i].clear();
15
16 for (int i = 0; i < n; i++) {
17 int d;
18 scanf("%d", &d);
19
20 int nxt = i + d;
21 int pre = i - d;
22
23 if (nxt < n)
24 g[nxt].push_back(i);
25 if (pre >= 0)
26 g[pre].push_back(i);
27 }
28
29 queue<int> q;
30 int dist[N];
31 memset(dist, -1, sizeof(dist));
32 dist[n - 1] = 0;
33 q.push(n - 1);
34
35 while (q.empty() == false) {
36 int u = q.front();
37 q.pop();
38
39 for (auto v : g[u]) {
40 if (dist[v] == -1) {
41 dist[v] = dist[u] + 1;
42 q.push(v);
43 }
44 }
45 }
46
47 for (int i = 0; i < n; i++)
48 printf("%d\n", dist[i]);
49}
50
51int main()
52{
53 freopen("jumping.in", "r", stdin);
54
55 int ncase;
56 scanf("%d", &ncase);
57
58 while (ncase--) {
59 solve();
60 }
61
62 return 0;
63}