#2263. 季风
季风
季风
题目描述
NOI2024 联合省选 第一试季风(wind) 季风(wind) 【题目背景】 生活在二维平面的小X 准备拜访小Y,但由于气候的变化,平面上刮起了季风。小 X 想知道季风的影响下,TA 至少要多少天能够到达小Y 的家,但小X 也是第一次遇 见这种怪事,所以请精通算法的你来帮忙。 【题目描述】 给定n, k, x, y 和2n 个整数x0, y0, x1, y1, · · · , xn−1, yn−1。 找到最小的.非.负.整.数m,使得存在2m 个.实.数x′ 0, y′ 0, x′ 1, y′ 1, · · · , x′ m−1, y′ m−1 满足以 下条件,或报告不存在这样的m: • !m−1 i=0 (x′ i + xi mod n) = x; • !m−1 i=0 (y′ i + yi mod n) = y; • ∀0 ≤i ≤m −1,|x′ i| + |y′ i| ≤k。 特别地,m = 0 时,认为 "!m−1 i=0 (x′ i + xi mod n)
和 "!m−1 i=0 (y′ i + yi mod n)
均为0。 【输入格式】 从文件wind.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行一个整数T 表示测试数据组数。 对于每组测试数据, • 第一行四个整数n, k, x, y, • 接下来n 行,第i 行两个整数xi−1, yi−1。 【输出格式】 输出到文件wind.out 中。 对于每组测试数据输出一行一个整数,如果存在满足题意的m,输出其最小可能值, 否则输出‐1。 【样例1 输入】 1 4 2 1 2 2 2 3 1 1 4 1 2 ‐2 ‐2 5 1 1 6 1 2 0 0 第2 页 共12 页
NOI2024 联合省选 第一试季风(wind) 7 1 1 8 2 100000000 100000000 100000000 9 ‐99999999 0 10 ‐100000000 0 【样例1 输出】 1 1 2 ‐1 3 0 4 399999999 【样例1 解释】 该组样例共有四组测试数据。 • 对于第一组测试数据,取m = 1,(x′ 0, y′ 0) = (1, 1) 满足条件,可以证明不存在更 小的m 满足条件; • 对于第二组测试数据,可以证明不存在任何非负整数m 满足条件; • 对于第三组测试数据,取m = 0 满足条件,可以证明不存在更小的m 满足条件。 【样例2】 见选手目录下的wind/wind2.in 与wind/wind2.ans。 该组样例共有八十组测试数据,所有测试数据均满足n = 1。其中测试数据1 ∼20 满足特殊性质A,21 ∼40 满足特殊性质B,41 ∼60 满足特殊性质C。 【样例3】 见选手目录下的wind/wind3.in 与wind/wind3.ans。 该组样例共有六十组测试数据,所有测试数据均满足n = 200。其中测试数据1 ∼20 满足特殊性质A,21 ∼40 满足特殊性质B。 【子任务】 设! n 为单个测试点内所有测试数据的n 的和。对于所有测试数据, • 1 ≤T ≤5 × 104; • 1 ≤n ≤105,1 ≤! n ≤106; • 0 ≤|x|, |y|, |xi|, |yi|, k ≤108。 第3 页 共12 页
NOI2024 联合省选 第一试季风(wind) 测试点编号 n ≤ ! n ≤ 特殊性质 1 1 300 A 2 B 3 C 4 无 5 200 5, 000 A 6 B 7 无 8 104 105 A 9 B 10 105 106 无 特殊性质A:∀0 ≤i ≤n −1,|xi| + |yi| ≤k。 特殊性质B:k = 0。 特殊性质C:x0 = y0 = 0。 【提示】 本题输入文件较大,请使用较为快速的输入方式。 第4 页 共12 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4
1 2 2 2
1 1
1 2 -2 -2
1 1
1 2 0 0
1 1
2 100000000 100000000 100000000
-99999999 0
-100000000 0
1
-1
0
399999999
样例 2
80
1 3879 -38153167 -71867746
2583 0
1 348280 -12775625 -68560864
96198 187933
1 823 47730561 -33483074
-173 -18
1 1052 -2583 74869396
208 -844
1 26320 79869642 17518241
-23006 -3313
1 20 -63819161 -20275499
-4 -13
1 17975 18272332 6586849
-10829 5243
1 2739 32999091 -88525496
-1619 1119
1 2 -41171064 26775275
2 0
1 3396 -3066117 -78701232
1891 1504
1 1175859 -7358 66342643
396234 -779625
1 833 50263152 21371231
-546 -286
1 1113846 46564780 23943140
-13807 -93917
1 1 17244088 -58625353
0 0
1 63 733 32532666
59 4
1 2482633 23831768 87243936
0 43875
1 16233 42752958 80404220
-4905 1584
1 74 -47319541 77415559
6 -67
1 3582528 -53706366 -49792130
1008682 -635801
1 1 -19359946 45661461
0 0
1 0 -15784782 -40708122
19 49
1 0 54836473 -5507751
151 -8070
1 0 -25801865 -7740331
-50 -15
1 0 -12279435 73159674
-12279435 73159674
1 0 70105860 -67018895
5500843 16428624
1 0 -80178589 -30186079
-80178589 -30186079
1 0 -5851716 1950572
6 -2
1 0 22316310 9967974
11158155 4983987
1 0 -92573223 -2458899
-92573223 -2458899
1 0 44109212 -93388971
44109212 -93388971
1 0 -9794848 -8083648
-4897424 -4041824
1 0 4923133 -70962510
4923133 -70962510
1 0 -35469168 -844504
42 1
1 0 -64993799 -64413616
-32496653 -32206957
1 0 -10950588 4301828
-28 11
1 0 78962494 39431848
-12443 -1232
1 0 -75528207 96418697
-37763906 48209144
1 0 -892941 -11905880
3 40
1 0 10314501 15677758
25 38
1 0 -8119118 -57557618
-5091989 -5352713
1 0 55199413 15696468
0 0
1 10863 -57969777 5546602
0 0
1 0 -68311922 -89039202
0 0
1 0 74356210 0
0 0
1 234 0 -18631445
0 0
1 4694 0 2725302
0 0
1 4 3282987 77024495
0 0
1 52780367 -87998863 -90852752
0 0
1 95 -88011885 -58568648
0 0
1 54241757 0 0
0 0
1 30869 -54967329 -95591650
0 0
1 142257 -90069473 11517898
0 0
1 2595 0 0
0 0
1 24068286 -42546516 16196960
0 0
1 0 0 -21611532
0 0
1 9 64479986 -86768051
0 0
1 0 0 -10394408
0 0
1 1 -97292960 27820762
0 0
1 0 0 0
0 0
1 0 0 0
0 0
1 2265 32823931 -79928370
1 1
1 8360636 -37588197 1677525
-1623665 4972132
1 444339 68495825 19062399
-118406 -325929
1 68208769 68455914 3573397
4 -19
1 41785 -82946964 -39352116
3491 38290
1 15 -46840279 23149501
17 90
1 0 -8861148 -5212440
-17 -10
1 6949083 27637290 25698862
21 81
1 4 56180502 -25647702
28090251 -12823851
1 1 2702188 21420856
1351094 10710428
1 5252 -93536009 -43689939
-81545 87988
1 11565 72680075 18116895
-2 -14
1 14023 49885302 43182522
-94114 -24825
1 3011918 64252891 -47246631
-1918693 1093224
1 947167 -25732498 4352
0 670845
1 29058 -32922495 43498200
18288 -10766
1 234 -23889492 -66821364
33 196
1 5449 -27210368 22216383
-112801 -5784
1 1091 -87096973 -53971827
73295 138235
1 70051 -31917111 55181816
31552 -38498
84893
1268
121578
-1
97387883
3958515
6141
121524587
-1
81767349
-1
71634383
71
75869441
4066492
44
9539
124735100
33
65021407
-1
-1
-1
1
-1
1
-1
2
1
1
2
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
5848
-1
-1
79622
581
20076871
4
1542953
0
4878
715
0
3
-1
16805338
-1
125113722
0
0
49781
8
21889556
2
30574770
-1
521244
8
2
2
-1
7862
-1
111499522
94
19105174
18142172
-1
-1
87098927