← 返回题目列表

AtCoder · ahc057_a

A. 分子

中文机器翻译题面 查看原题

故事

AtCoder实验室从事新分子的开发。 高桥是一位天才化学家,他可以自由地结合在他选择的任何时间移动的原子形成分子。 然而,键合原子消耗的能量取决于它们之间的距离,因此他希望使用尽可能少的能量来创建所需数量的分子。

问题陈述

考虑由下式定义的二维平面 0 \leq x < L = 10^5 和 0 \leq y < L = 10^5。这架飞机有一个 环形 结构,意思是左右边缘(x = 0 和 x = L),以及顶部和底部边缘(y = 0 和 y = L),已连接。任何在此范围之外的坐标都将归一化为在该范围内 0 \leq x, y < L 除以后取余数 L 两者 x 和 y。例如,移动到达的位置 (-20000, 30000) 来自 (10000, 90000) is (90000, 20000).

有 N 点在此平面上。时 t = 0,初始位置 (x_i, y_i) (0 \leq x_i, y_i < L)和初始速度 (vx_i, vy_i) (-100 \leq vx_i, vy_i \leq 100)的 i第一点 (0 \leq i < N)作为输入给出。在初始状态下,每个点形成一个独立的连通分量。

每次 t = 0, 1, \ldots, T - 1,按顺序处理以下两个阶段: 1. 粘合阶段 和 2. 运动阶段.

1. 粘合阶段

时间 t,可以 债券 属于不同连通分量的两个点。多个键合可以在同一时间步骤中进行。

让 (x_i, y_i) 是点的位置 i 时间 t,和 (x_j, y_j) 是点的位置 j 时间 t。的 粘合成本 D 用于粘合点 i 和点 j 使用以下距离公式计算:

\[ D = \mathrm{round}\left( \sqrt{ \bigl(\min(L - \Delta x,\ \Delta x)\bigr)^2 + \bigl(\min(L - \Delta y,\ \Delta y)\bigr)^2 } \右) \]

\[ \Delta x = |x_i - x_j|,\quad \Delta y = |y_i - y_j| \]

当两个点粘合时,所得连接分量的速度根据动量守恒定律进行更新。假设在键之前,点 i 属于连通分量 A 以速度移动 (vx_A, vy_A),并点 j 属于连通分量 B 以速度移动 (vx_B, vy_B)。然后,对于属于连通分量的所有点 A 和 B,速度 绑定后的 (vx_{\text{new}}, vy_{\text{new}}) 更新如下:

\[ (vx_{\text{新}}, vy_{\text{新}}) = \左( \压裂{|A| \times vx_A + |B| \times vx_B}{|A| + |B|}, \压裂{|A| \times vy_A + |B| \times vy_B}{|A| + |B|} \右) \]

在这里, |A| 和 |B| 表示连通分量中的点数 分别是 A 和 B。粘合后,所得连接组件中的所有点都会随着移动 相同的速度。点的位置不会因粘合而改变。此外,同一时间步长内执行键合的顺序不会影响连接组件的最终位置、键合成本或速度。

坐标和速度可能会变成小数,但所有计算都是使用双精度浮点运算执行的。

2. 运动阶段

每个连接分量中所有点的位置同时更新。让 (x_i, y_i) 是点的位置 i 时间 t,让 (vx_i, vy_i) 是连接分量到该点的速度 i 属于。然后,位置 (x_i', y_i') 点 i 时间 t + 1 更新如下:

\[ (x_i', y_i') = ((x_i + vx_i) \bmod L, (y_i + vy_i) \bmod L) \]

规划债券,以便在适当的时候 T,连接组件的数量为 正是 M,每个连通分量的大小为 正是 K,同时最小化 总粘合成本 D.

粘合和移动示例

Example

上图展示了将三个点粘合到单个连接组件中的示例。 首先,左下和右下两点粘合,其运动方向向上改变。 接下来,它们与顶部向右移动的点粘合,移动方向变为右上。

评分

令所有债券的总债券成本为 D_{\text{sum}}。单个测试用例的分数计算如下。分数越高越好。

\[ \mathrm{分数} = \mathrm{round}\!\left(10^{6} \times \log_{2}\!\left( \frac{L \times (N - M)}{D_{\text{sum}} + 1} \right)\right) \]

结果将是 WA 在以下情况下:

  • 如果输出无效
  • 如果在时间 T,连接组件的数量不是 正是 M,或者每个连接组件的大小不是 正是 K
  • 如果在已经属于同一连通分量的两点之间指定键

有 150 测试用例,提交的分数是每个测试用例的总分。 如果您的提交产生非法输出或超出某些测试用例的时间限制,则提交本身将被判断为 WA or TLE ,提交的分数将为零。 比赛期间获得的最高分将决定最终排名,比赛结束后不进行系统测试。 如果超过一名参赛者获得相同分数,则无论提交时间如何,他们都将排名在同一位置。


输入

输入由标准输入按以下格式给出:

N T M K L
x_0 y_0 vx_0 vy_0
x_1 y_1 vx_1 vy_1
\vdots
x_{N-1} y_{N-1} vx_{N-1} vy_{N-1}
  • 总点数为 N = 300.
  • 总步数为 T = 1000.
  • 连接组件的目标数量为 M = 10.
  • 每个连接组件的目标大小是 K = 30.
  • 空间的边长是 L = 10^5.
  • (x_i, y_i) 表示点的初始位置 i,其中 0 \leq x_i, y_i < L 和值是整数。
  • (vx_i, vy_i) 表示点的初速度 i,其中 -100 \leq vx_i, vy_i \leq 100 和值是整数。

输出

准确输出 N - M 行连接到标准输出。每行由以下三个整数组成,代表该点 i 和点 j 已绑定时间 t。 输出的顺序是任意的,但处理是按照时间升序进行的 t.

t i j

输出必须满足以下条件:

  • 0 \leq t < T
  • 0 \leq i, j < N,和 i \neq j

显示示例

输入生成

\mathrm{rand}(L,U):随机生成一个介于 L 和 U,包含在内,具有统一概率。

生成初始位置

对于每个点 i,独立生成 x_i = \mathrm{rand}(0, L - 1) 和 y_i = \mathrm{rand}(0, L - 1).

生成初始速度

对于每个点 i,独立生成 vx_i = \mathrm{rand}(-100, 100) 和 vy_i = \mathrm{rand}(-100, 100).

工具(输入生成器和可视化工具)

请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。


示例输入 1

300 1000 10 30 100000
2436 18582 80 -53
11172 25071 -47 -71
56643 73929 46 -89
32441 4016 1 62
81600 85102 -62 83
46831 96411 -13 -88
85958 91609 -31 -51
47788 53885 -98 87
80068 86751 -32 23
73792 28207 -18 55
82502 35092 87 41
42677 29047 14 -3
20208 44400 80 4
81416 25817 -66 85
66324 4956 19 73
79260 68753 -99 97
60669 49104 -1 -68
11487 8219 96 82
10449 35974 97 -83
36934 26216 -57 12
31832 45833 7 -75
84066 42632 -42 -93
48899 22095 -20 4
499 17907 19 -59
58093 41209 -45 61
68394 86597 7 16
94459 57728 47 38
3355 90413 64 -42
86511 77344 -16 -73
61617 76222 69 84
36013 78203 -62 -7
66418 15805 -100 -12
62210 76124 -63 78
69486 84752 96 -4
62365 49587 -35 3
7036 85915 -25 -91
85117 52902 -6 -95
30509 85473 -47 -80
85969 88350 -86 42
75340 91696 -48 -99
4902 94732 -49 49
44596 90771 -37 48
44827 68181 80 -98
96068 81537 -61 -35
92964 85388 -61 29
30384 93176 19 23
16047 68444 -56 -61
72556 4749 11 -17
41093 18686 -9 -10
73474 10624 89 39
38347 89510 -90 57
63568 16873 51 75
87374 7602 70 69
50016 50344 46 -6
72135 90944 -60 20
79124 34278 -14 85
57903 91370 -82 -86
65699 24840 -90 71
61416 42823 -4 -27
5881 13273 -75 35
90608 55227 44 26
4228 84079 -51 23
63053 6894 -83 20
54427 32840 -98 0
35069 866 60 84
56338 3161 -1 -67
87839 68526 -17 87
51927 22524 62 -88
18360 76668 -49 -19
41330 38632 -43 85
8423 85430 27 -72
31151 30949 -35 -68
35425 98667 -34 -40
64216 29899 -17 40
6406 50469 75 81
55655 37416 -9 35
1516 30683 82 35
91220 8358 -5 43
17134 28374 68 41
33754 62967 -80 79
49343 85380 -81 91
42151 35142 65 -92
66104 39335 71 9
14111 50565 -100 51
89806 40162 32 -37
64785 72129 20 31
32720 22985 29 53
72911 9918 46 -92
49311 20410 -27 -28
67923 29578 26 -75
35876 65903 32 -37
56965 81112 92 -12
69550 59002 36 35
63834 92908 -88 -19
75066 80665 47 -88
53110 24554 -90 54
59597 4126 20 -11
63411 98916 -27 -16
78646 71220 -6 18
53418 70370 -79 -22
91062 85140 -67 -83
86010 32629 2 45
75168 84052 24 48
85615 38954 18 19
13168 93699 30 -42
77158 13596 -79 -73
99380 68100 8 70
42694 41699 -32 96
57174 23983 44 -64
88856 48119 71 -2
57945 26398 -96 16
34332 3616 61 -76
20394 35156 22 -58
68780 41704 50 -73
5379 44220 55 21
90510 66235 28 -92
69428 77407 51 5
10696 78430 -45 -40
24277 96652 39 90
81795 3062 99 -31
80424 39645 -26 -51
62404 61793 1 42
18353 74523 -48 46
28270 6207 47 56
15533 8441 36 -4
83297 59770 17 -87
85877 26141 49 5
77103 62145 -32 -29
90325 58414 94 -90
26573 75460 31 -73
4974 24976 97 -93
28525 86194 20 74
83856 264 18 21
74580 51154 15 48
50869 29907 -6 78
948 12466 -82 -46
7689 60224 -42 -21
44985 60022 11 10
45567 21013 -71 40
41314 93936 92 -63
95718 29800 -8 -53
60008 67095 78 29
55013 36137 87 -66
503 3718 36 64
43856 81799 -81 19
91386 79466 -62 15
8026 98878 97 -6
96002 46215 -50 -42
54713 50659 9 -42
89363 21620 -56 19
49962 67038 55 -15
943 41697 7 53
40087 42225 16 -47
57254 77442 98 -82
36337 29590 74 91
26938 3423 54 51
39779 32823 -77 -84
32847 17135 100 -5
79055 40811 92 -15
21868 98831 -91 -38
10449 6999 -82 35
49418 87285 -42 37
97197 74822 -17 10
47348 63144 -90 68
64915 22253 74 90
42086 35915 -53 23
18935 26845 77 -20
2238 2244 41 32
72456 93027 -41 0
28617 20552 -62 -80
94701 39336 12 -49
62123 63790 58 -46
99993 60564 -69 2
3426 80446 52 -73
30321 10476 -70 -21
23253 950 28 -100
44526 84781 -56 57
51852 64272 -72 -78
84201 88938 -26 63
86769 34382 22 -32
22189 86673 62 9
58373 8944 -9 46
53079 90631 -48 29
23413 91072 45 66
88867 741 -23 16
1384 41908 95 76
35135 90166 -26 -95
74179 9930 -48 -51
50994 17019 27 -91
5797 76408 -10 4
96854 40045 64 34
92623 24149 -16 -69
83586 30280 -10 -26
61804 51797 31 -94
46036 49587 -32 -55
37530 39036 -59 69
8874 85829 -22 90
7485 2200 50 30
67407 98154 94 -30
70157 77324 48 34
81873 76890 39 58
52818 91109 22 -17
54658 95263 37 -59
9119 34477 25 -93
7129 74354 -18 25
60889 27731 -21 48
24786 2060 45 -46
38075 19541 38 -66
98098 20038 -52 10
35468 98666 34 -11
41880 19402 82 64
87283 93233 83 27
82643 48079 -82 85
36106 27889 49 -31
70284 84426 80 -34
48079 65974 -33 31
38620 22820 82 -33
12105 891 -35 3
39572 8070 -6 -100
88044 22119 28 -49
15634 33732 -100 -15
28278 92300 19 67
31771 58716 -81 49
3779 44317 -96 52
42251 33963 67 -2
2716 85833 -9 -22
94473 45427 -11 27
57546 98190 -38 33
93488 69325 88 -86
16834 84421 68 -24
16776 36469 87 -8
30469 55819 9 91
66676 94952 -51 100
74225 42292 -64 27
95178 98882 16 72
41586 53226 72 -25
54425 28395 40 86
63295 44650 35 -8
8918 89927 -84 -58
43617 54136 84 29
19114 90718 -88 -81
11772 48502 58 50
16769 18178 -52 10
30990 46183 53 87
77588 15246 75 73
22840 26416 74 -49
83985 39929 53 -81
47630 92407 -85 97
47626 93543 79 -6
66366 61019 98 -12
78834 90305 15 27
68799 66940 -16 45
84458 86826 83 1
96854 48119 -12 -81
28842 45332 -3 -85
99589 87666 68 28
10768 6116 4 13
77087 97715 93 60
19218 20594 73 -99
43766 43938 -29 69
36059 6277 30 -42
61262 71995 -14 54
53727 87806 -50 95
68498 24075 68 66
65701 58821 -43 -33
26807 3006 -99 78
96611 40954 -32 -61
74332 68414 61 -41
93886 14955 42 77
65492 15419 57 -3
92243 49163 -85 44
51731 74047 62 -54
98816 47865 4 -27
97740 87273 91 -72
67507 30632 34 -35
4098 14515 -92 93
99437 70562 11 -78
84641 87942 -56 -81
58040 49980 -94 8
66894 70330 57 89
49916 43921 -1 31
46384 60472 -58 17
76985 7656 -92 54
76463 7654 -42 74
67955 20110 74 -3
86395 65532 45 -52
80133 44506 -16 -19
3979 57651 65 -65
67184 14011 -99 48
26965 3647 -19 -29
97237 34716 16 -20
44259 87431 62 21
2929 5456 69 -8
82897 12715 12 5
46414 16319 54 43
20952 55289 -73 21
32306 80650 -36 -37
32354 54519 81 -4
22913 77540 -61 -66
21963 14649 67 -28

示例输出 1

510 192 66
226 174 276
569 16 98
958 56 36
744 30 149
936 81 236
289 260 269
289 276 222
69 146 210
81 107 230
842 25 199
746 82 230
103 68 143
986 39 60
159 58 241
908 247 80
512 274 216
167 154 138
881 220 241
392 59 54
841 235 190
625 206 246
267 69 138
290 177 163
708 116 55
424 52 66
156 291 14
476 130 213
122 189 155
457 226 136
866 34 163
767 29 292
496 74 22
772 172 237
28 139 1
591 88 20
219 140 47
626 191 68
180 209 150
626 279 265
4 73 20
319 156 136
775 97 231
358 141 154
488 85 254
39 164 180
30 83 21
150 197 163
162 217 222
780 152 71
67 282 88
642 133 254
617 248 95
134 86 128
291 4 116
44 178 206
554 79 66
319 117 92
202 254 253
56 3 153
801 168 231
933 122 65
990 180 54
485 26 294
703 251 123
438 44 77
821 222 262
188 232 160
661 112 258
697 277 83
596 228 244
682 91 221
976 281 20
772 160 0
732 236 143
173 57 282
7 144 16
343 183 244
691 294 194
61 241 163
463 280 5
157 27 247
555 105 65
105 55 119
206 41 125
770 124 199
318 297 181
357 250 269
220 110 197
373 76 151
449 9 164
507 287 92
436 171 35
552 285 102
862 63 36
553 244 163
576 292 194
308 106 107
546 138 229
15 163 87
297 128 173
959 23 39
284 123 154
720 126 68
687 5 117
757 272 134
966 270 259
926 216 149
407 120 199
907 198 262
764 157 54
744 227 181
423 121 73
650 0 12
44 230 229
926 245 59
11 239 228
317 37 207
932 268 118
55 252 138
33 99 16
504 62 36
303 296 206
623 28 55
726 293 80
284 72 19
924 153 246
928 267 131
752 181 54
833 150 214
541 115 194
418 237 236
418 113 153
673 78 73
254 185 233
81 71 267
403 46 12
317 67 184
130 103 28
827 93 46
327 210 276
731 199 119
647 223 116
525 255 131
903 19 44
207 208 78
406 40 245
102 205 271
544 188 230
202 65 261
145 213 131
509 14 131
374 215 252
751 145 77
658 95 287
711 243 12
180 196 79
840 108 79
74 109 296
869 94 125
73 179 20
328 96 161
444 155 18
413 170 73
930 38 271
197 169 236
927 290 132
869 45 68
656 90 197
739 75 216
173 7 214
671 283 83
143 53 117
687 125 93
667 89 124
246 286 56
168 36 93
29 187 137
256 263 187
196 231 137
478 15 63
848 167 44
482 211 199
864 92 225
795 289 128
293 278 285
422 161 163
571 257 160
359 242 241
172 299 1
377 35 157
204 47 256
979 80 28
950 288 28
598 114 20
636 166 73
175 275 47
306 84 183
850 162 220
816 238 182
947 225 194
420 259 262
827 219 213
665 66 137
785 240 241
105 151 150
972 118 246
857 104 78
59 8 272
903 295 36
251 265 150
202 284 256
223 201 114
3 158 229
290 135 0
157 48 84
809 102 4
411 224 156
461 193 28
342 262 269
882 149 50
530 49 269
458 271 92
125 253 137
97 195 260
536 261 153
153 218 163
714 176 20
251 159 225
729 17 182
121 132 51
882 18 119
201 6 229
232 143 246
715 64 120
781 173 218
118 186 241
443 207 92
163 142 146
236 1 151
176 42 53
883 264 113
387 148 20
871 33 14
751 32 49
569 22 236
938 249 93
11 98 213
707 10 105
285 134 146
27 50 114
56 204 247
117 61 296
388 258 20
471 147 112
129 221 210
403 234 73
863 131 273
490 54 137
337 175 192
748 256 222
283 190 6
99 11 141
528 212 128
748 203 197
330 233 184
189 2 139
66 31 159
162 77 225
581 21 229
89 51 0
44 165 134
782 101 277
275 100 73
189 298 258
921 24 191
518 70 86
149 43 265
913 13 82
471 127 121
199 184 229
132 136 12
51 182 36
240 214 273
314 200 159
923 202 138
997 266 222
28 60 28
267 111 273
460 129 140