故事
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.
粘合和移动示例
上图展示了将三个点粘合到单个连接组件中的示例。 首先,左下和右下两点粘合,其运动方向向上改变。 接下来,它们与顶部向右移动的点粘合,移动方向变为右上。
评分
令所有债券的总债券成本为 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).
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
示例输入 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
