C20 - Mayor's Challenge Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 100000000

問題文

KYOPRO 市は N \times N のマス目で表されます。上から i 番目、左から j 番目のマスを (i, j) とします。この市には K 個の地区があり、それぞれに 1 から K までの番号が付けられています。地区 k の人口は A_k 人、役所職員数は B_k 人です。また、マス (i, j) は地区 C_{i, j} に属しています(C_{i, j} = 0 のときは市の領域外です)。ここで、KYOPRO 市の各地区および市全体は連結になっています。ただし連結であるとは、どのマスからどのマスへも、上下左右に隣接するマスへの移動を繰り返して到達できることを指します。

KYOPRO 市の市長である三郎氏は、いくつかの地区を合併することで、市全体を L 個の「特別区」に分けようと考えています(下図は K = 24, L = 4 の例)。ここで、各特別区は連結である方が好ましいです。

三郎氏は特別区どうしの格差を減らしたいので、人口の差と役所職員数の差をできるだけ小さくする(評価基準については 得点 の項を参照)ような特別区の分け方を求めるプログラムを作成してください。

なお、この問題はヒューリスティック型課題であるため、必ずしも最適な答えを出力する必要はありません。また、採点方法やテストケースの生成方法などの情報は、以降の文章をご覧ください。

制約

  • N = 50
  • K = 400
  • L = 20
  • 50000 \leq A_k \leq 100000
  • 1000 \leq B_k \leq 2000
  • 0 \leq C_{i, j} \leq K
  • KYOPRO 市全体(C_{i, j} \neq 0 の部分)は連結
  • 地区 1, 2, \dots, K はすべて連結

入力

入力は以下の形式で標準入力から与えられます。

N K L
A_1 B_1
A_2 B_2
 \vdots
A_K B_K
C_{1, 1} C_{1, 2} \cdots C_{1, N}
C_{2, 1} C_{2, 2} \cdots C_{2, N}
 \vdots
C_{N, 1} C_{N, 2} \cdots C_{N, N}

出力

K 行にわたって出力してください。i 行目には、地区 i を何番目の特別区に割り当てるか(1 以上 L 以下の整数)を出力してください。

得点

この問題では、特別区どうしの格差が小さいほど高得点が得られるようになっています。

まず、以下の条件をひとつでも満たした場合は不正解 (WA) となり、0 点となります。

  • 出力形式が指定されたフォーマットに沿っていない
  • どの地区にも割り当てられていない特別区が存在する

それ以外の場合は正解 (AC) と判定されます。特別区の人口の最大値と最小値をそれぞれ p_{max}, p_{min}、特別区の役所職員数の最大値と最小値をそれぞれ q_{max}, q_{min} とするとき、テストケースの得点は以下の値を四捨五入して整数にした値となります。

  • すべての特別区が連結な場合:10^6 \times \min\left(\frac{p_{min}}{p_{max}}, \frac{q_{min}}{q_{max}}\right)
  • 一部の特別区が連結でない場合:10^3 \times \min\left(\frac{p_{min}}{p_{max}}, \frac{q_{min}}{q_{max}}\right)

採点に使われるテストケースは全部で 100 個あり、最終的な得点はそれらの合計となります。

マイルストーン

以下の図は、得点を 10 段階のレベルで表したものです。
より高いレベルに挑戦してみましょう!

入力データ生成方法

すべての採点用入力データは、以下の手順で生成されています。ただし、実数 x に対して、\lfloor x \rfloorx を超えない最大の整数とします。

ステップ 1. 地区に分割

まず、J = \lfloor 1.2 \times K \rfloor として、N \times N のマス目を以下のようにして J 個の地区に分割します。

  1. 最初、各マスが異なる地区に属するとして、合計 N^2 個の地区があるとする。
  2. 以下の処理を N^2 - J 回繰り返す。
    • 隣り合っている 2 つの地区のペアのなかで、合計マス数が最小になるものを選ぶ。このようなペアが複数ある場合は、その中から無作為に 1 つ選ぶ。
    • 選んだ 2 つの地区を合併し、1 つの地区にする。

ステップ 2. KYOPRO 市の地区の割り当て

ステップ 1 で生成した J 個の地区のうち J - K 個を除去した後、残った K 個の地区に番号を割り振ります。具体的な手順は以下のようになります。

  1. 以下の処理を J - K 回繰り返す。
    • 市の境界に面する地区をランダムに 1 つ選ぶ。
    • 選んだ地区を除去しても市が連結になるなら、その地区を除去する。そうでないなら、前述の処理をもう一度行う。
  2. 残った K 個の地区に、1 から K までの番号を無作為に割り振る。

ステップ 3. 人口・役所職員数の設定

地区 k の人口 A_k および B_k は、以下のように生成します。

  • A_k50000 以上 100000 以下の整数の中から無作為に選ばれる
  • B_k1000 以上 2000 以下の整数の中から無作為に選ばれる

入力データのサンプル

入力データのサンプルは、ここをクリック するとダウンロードすることができます。ダウンロードで得られる ZIP ファイルの中には 100 個の入力ケースが入っており、手元でのテストなどに利用できます。そのうち in000.txt が入力例に対応しています。なお、これらの入力データのサンプルは、実際の採点に使われる入力データとは異なります。

ビジュアライザ(2022/10/9 追記)

ikd さんのご協力によりビジュアライザが作られました(リンク)。入出力を画像上に表示できるツールとなっています。デバッグ等にご活用ください。


入力例 1

50 400 20
88693 1799
76752 1355
97712 1846
70684 1141
55236 1861
85874 1843
73687 1551
50878 1033
92129 1207
75284 1795
92687 1323
84374 1306
73047 1460
85013 1272
64574 1753
81364 1084
71249 1908
88895 1551
59297 1708
87655 1553
71481 1149
67716 1979
80160 1921
78145 1609
98542 1801
56480 1674
74497 1425
52281 1209
96057 1606
82457 1590
71796 1634
86369 1694
62952 1868
67210 1946
83266 1149
86268 1140
50062 1259
96867 1641
73101 1065
52990 2000
94882 1658
63770 1027
87958 1834
54498 1384
53732 1434
63482 1894
56957 1074
98805 1584
53201 1657
96175 1707
90532 1889
57349 1943
72347 1257
73535 1927
92986 1940
85034 1284
64922 1330
75695 1423
79448 1460
57880 1050
96912 1747
98826 1198
74857 1720
54893 1134
94592 1752
59118 1390
81705 1359
61909 1499
54752 1251
86563 1280
94992 1401
76451 1126
87839 1177
98731 1832
64034 1565
88459 1148
99114 1549
58688 1771
57191 1611
61927 1862
85569 1010
70164 1726
57552 1125
71398 1057
88017 1367
85453 1396
71142 1434
71239 1262
89953 1203
86776 1559
95700 1344
94389 1450
52155 1733
50231 1288
56618 1211
96704 1352
87133 1702
65956 1383
84315 1804
99492 1243
85839 1054
63447 1506
65983 1844
76328 1540
59450 1289
84784 1457
99142 1651
55733 1097
57534 1387
95537 1197
95624 1140
84856 1172
61110 1513
75875 1273
65174 1261
87225 1293
94030 1356
77742 1939
81080 1529
85622 1458
91790 1347
84224 1910
61377 1476
95385 1869
69625 1066
50191 1439
70446 1453
82596 1631
60200 1404
57047 1961
65764 1912
81602 1898
77479 1283
61187 1395
77822 1611
53982 1848
55120 1953
81149 1387
81073 1476
53001 1307
77733 1161
66742 1479
55933 1683
64860 1072
90679 1043
99060 1682
96415 1960
80195 1499
71820 1554
64974 1476
83457 1034
85491 1311
72217 1045
58730 1574
60131 1170
80550 1874
77866 1564
64268 1952
96515 1546
79013 1149
79259 1932
85523 1789
64544 1373
61542 1398
52506 1301
91418 1486
74370 1254
91232 1272
63460 1656
57576 1867
79700 1636
54883 1710
76853 1204
63723 1439
88128 1458
84666 1222
61797 1455
55950 1368
76391 1790
56052 1835
61568 1907
85798 1831
83613 1311
87976 1674
68735 1665
90801 1360
64586 1526
75766 1508
71242 1000
94316 1104
55170 1746
70634 1143
73859 1153
67631 1446
62574 1281
61644 1337
94606 1894
50411 1200
54253 1677
93582 1457
66649 1199
63614 1767
59093 1661
94390 1127
61784 1028
89213 1871
66341 1250
50519 1088
55770 1302
80281 1258
65393 1010
97540 1652
94575 1879
77963 1256
74517 1362
73235 1333
64773 1461
94207 1924
70784 1833
95335 1191
94330 1141
98765 1676
56009 1168
77836 1430
93280 1215
86754 1669
80692 1550
57644 1505
82106 1636
94724 1113
54673 1732
60098 1295
61673 1180
66186 1024
51943 1233
70738 1267
82712 1428
88292 1989
84997 1403
83935 1350
99904 1794
92433 1094
58355 1810
83851 1619
66380 1163
66746 1279
95196 1658
72767 1131
94814 1250
72101 1173
65642 1244
94782 1468
71879 1157
56107 1700
67791 1698
85564 1284
58588 1596
75147 1053
89163 1339
87299 1490
55271 1943
85867 1103
59029 1660
69875 1920
65427 1451
80333 1007
71524 1993
67978 1291
63645 1998
96580 1004
93632 1630
83360 1359
87493 1731
94513 1586
87353 1587
70916 1045
91837 1034
65444 1819
69503 1625
55506 1011
99854 1643
65694 1033
59667 1844
79840 1197
96907 1273
65119 1445
55313 1624
70066 1256
71472 1207
99497 1658
85129 1433
86751 1665
69314 1518
84512 1648
87989 1332
63478 1837
57027 1721
92446 1019
51310 1371
73462 1244
98214 1223
96654 1494
75329 1362
87021 1568
64515 1250
73807 1374
73575 1982
99401 1980
51542 1896
60046 1814
58927 1488
71230 1112
73741 1372
57187 1883
61097 1108
75247 1289
78624 1588
87709 1151
50280 1397
64016 1923
71644 1928
91198 1430
81278 1260
77443 1235
56476 1873
93020 1985
81397 1922
74870 1287
61788 1006
63081 1458
96159 1588
74904 1302
95627 1002
80587 1480
79684 1526
89412 1412
72415 1511
94620 1448
77865 1932
69070 1108
67986 1183
74304 1276
96437 1630
97770 1496
93097 1363
73233 1761
71266 1304
71942 1712
52077 1566
83784 1361
84341 1762
99764 1366
54525 1061
67943 1625
85433 1852
69265 1113
87501 1853
71730 1404
50460 1722
91218 1910
64912 1896
78734 1682
92271 1124
52575 1207
81435 1305
67040 1494
62378 1480
89866 1385
82297 1429
83433 1141
81755 1745
85057 1598
86884 1043
60307 1326
65230 1562
93307 1663
74117 1515
80081 1867
85321 1835
86707 1321
81159 1705
54801 1391
88115 1354
63325 1307
55802 1247
89458 1011
72180 1493
71436 1789
64185 1857
70933 1964
96435 1350
97773 1863
51584 1157
93204 1747
50258 1242
93614 1395
96850 1858
54754 1591
91059 1339
72536 1956
379 379 379 0 226 226 226 382 382 355 355 355 0 0 0 0 0 0 0 63 63 63 63 0 0 0 0 0 0 327 0 0 0 0 194 194 0 0 0 0 72 358 358 358 358 0 0 0 0 0
379 379 379 0 0 226 226 382 382 0 0 355 0 0 0 337 337 0 0 0 0 163 356 356 0 0 0 0 0 327 300 300 0 0 194 194 0 0 0 0 72 72 358 358 0 0 0 0 0 0
379 379 0 0 275 226 226 382 382 0 0 0 0 0 0 337 69 69 69 0 163 163 356 356 0 0 378 378 327 327 300 300 0 0 194 194 174 174 297 297 297 72 358 0 0 0 0 0 0 0
347 347 128 128 275 275 275 382 382 87 354 354 354 0 0 337 69 69 0 0 163 163 151 151 151 151 378 327 327 327 327 338 338 0 0 320 320 174 174 297 297 297 358 0 0 0 0 0 0 0
347 347 128 128 275 244 182 87 87 87 354 354 354 354 0 0 238 238 0 0 0 342 151 151 188 188 378 284 284 95 95 338 338 307 307 320 320 174 210 210 210 210 210 0 0 0 348 348 0 0
128 128 128 244 244 244 182 159 149 149 149 149 205 205 205 90 238 238 0 0 0 342 342 342 188 188 284 284 284 95 95 397 338 307 14 14 67 224 224 224 210 210 210 0 0 0 348 375 375 0
0 0 244 244 244 244 182 159 149 149 149 202 202 202 205 90 90 90 173 0 0 0 342 342 188 188 97 34 34 95 95 397 397 307 14 14 67 224 184 184 184 184 0 0 0 348 348 375 375 227
0 0 0 41 41 41 182 159 88 88 267 202 309 12 119 119 90 90 173 0 0 0 344 188 188 133 97 34 34 95 137 137 397 36 14 14 67 67 67 76 76 76 269 269 227 227 227 227 227 227
0 0 0 41 41 41 159 159 88 88 267 309 309 12 119 119 90 90 173 0 0 0 344 133 133 133 97 272 272 137 137 137 137 36 36 260 260 80 80 76 76 76 269 269 178 178 178 178 156 156
0 0 0 380 380 380 88 88 88 88 267 309 309 12 12 334 334 216 173 0 0 344 344 133 74 74 97 272 272 371 371 137 137 36 36 260 260 80 80 80 269 269 269 269 3 3 3 178 156 156
0 0 0 380 333 333 333 98 98 98 267 374 374 374 109 334 334 216 216 216 0 207 207 74 74 74 97 299 299 371 371 371 308 308 36 260 351 103 103 324 324 324 324 209 3 323 323 225 225 265
0 0 0 0 0 333 136 136 98 98 374 374 374 374 109 109 334 334 58 58 58 58 207 74 40 40 299 299 299 371 371 39 39 308 155 336 351 103 103 324 324 324 47 209 209 323 323 225 265 265
0 0 0 0 0 333 136 206 287 287 127 127 374 369 369 109 334 394 394 58 58 58 207 74 40 40 25 25 299 299 39 39 39 308 155 336 351 351 118 118 47 47 47 240 209 209 142 225 265 0
177 306 306 0 38 333 136 206 287 287 127 127 127 369 369 161 161 394 394 55 92 92 92 150 150 150 25 25 264 264 212 148 148 132 155 336 135 135 118 118 296 296 131 240 142 142 142 225 153 0
177 306 306 306 38 38 38 206 206 104 104 104 383 383 266 266 161 55 55 55 322 322 92 150 150 357 357 357 357 264 212 148 148 132 155 336 135 321 321 321 296 296 131 240 142 142 142 153 153 0
177 177 262 262 302 302 302 206 206 104 230 104 383 383 266 266 161 346 253 322 322 322 73 73 73 220 220 220 220 264 212 148 132 132 155 336 135 321 232 232 232 232 131 240 349 349 295 153 0 0
262 262 262 302 302 82 82 206 206 230 230 104 383 383 266 266 346 346 253 253 322 31 31 180 73 285 220 220 220 264 212 193 193 193 252 252 252 321 304 368 368 368 131 349 349 349 295 23 0 0
42 42 42 11 11 82 82 203 203 230 230 222 222 279 279 266 346 24 24 253 331 31 31 180 285 285 44 44 220 145 145 193 193 193 252 252 252 33 304 304 304 368 171 59 59 295 295 23 23 0
158 158 42 11 305 305 203 203 203 316 316 222 222 222 279 279 18 18 24 253 331 331 180 180 285 285 44 44 317 145 145 187 193 319 319 195 195 33 33 304 171 171 171 171 59 59 59 23 0 0
158 158 292 11 305 305 203 203 289 316 316 222 71 71 71 279 18 18 24 24 24 331 331 331 285 117 117 317 317 145 145 187 187 319 319 319 195 33 33 33 170 170 45 45 59 59 59 23 0 114
0 0 292 305 305 144 144 144 289 289 222 222 71 71 231 231 231 204 126 126 261 261 9 331 117 117 317 317 179 179 179 187 187 21 319 319 195 49 49 33 147 170 45 377 377 377 377 0 0 114
0 0 292 305 305 75 274 144 289 289 17 17 71 71 231 276 276 204 126 126 261 261 9 9 9 6 6 6 179 179 21 21 21 21 360 360 195 195 49 147 147 170 45 26 26 26 110 140 114 114
0 292 292 75 75 75 274 200 122 122 17 17 350 234 276 276 276 204 204 37 218 301 9 9 290 290 290 6 112 112 21 21 21 278 360 107 195 195 49 147 28 28 45 26 110 110 110 140 123 123
0 0 0 115 115 115 274 200 122 122 17 17 350 234 234 214 214 204 37 37 218 301 86 86 290 242 242 6 112 112 268 278 278 278 360 107 107 107 107 28 28 28 28 28 110 0 140 140 123 123
0 0 0 115 274 274 274 200 286 286 256 256 350 234 214 214 204 204 37 218 218 301 301 86 86 86 242 242 242 246 268 268 278 278 387 387 387 387 107 52 52 52 152 168 168 0 0 0 0 123
291 291 291 239 239 120 120 200 286 286 256 256 350 234 366 366 318 318 78 218 218 389 389 270 270 398 398 242 242 246 329 268 278 278 35 387 399 399 373 373 52 52 152 168 168 0 0 0 0 123
291 291 239 239 258 258 120 120 120 22 22 93 93 366 366 366 318 318 78 78 389 389 389 270 270 270 398 398 384 246 329 329 329 329 35 399 399 373 373 373 52 152 152 113 0 0 0 0 0 0
0 0 0 258 258 16 29 29 29 22 22 93 93 93 93 50 50 50 78 48 48 48 389 172 172 43 43 43 384 246 329 329 35 35 35 35 56 56 364 364 364 152 113 113 0 0 0 0 0 0
0 0 0 258 16 16 29 65 65 65 22 22 93 217 217 50 50 100 78 78 78 48 339 172 172 43 43 384 384 246 246 248 248 248 365 365 56 83 233 233 364 364 113 395 395 186 186 186 0 0
0 0 0 16 16 199 199 199 65 65 361 22 22 217 217 157 157 100 100 359 339 339 339 339 339 43 213 213 213 259 259 259 259 248 365 365 56 83 233 233 364 364 113 395 395 236 236 186 0 0
0 0 0 0 0 0 199 199 361 361 361 343 217 217 217 157 157 100 100 359 359 353 353 353 353 43 213 213 213 213 213 345 345 345 365 365 56 83 233 60 60 255 255 395 395 236 236 0 0 0
0 0 0 392 392 0 10 199 199 241 46 343 217 393 393 393 393 393 100 100 359 141 141 353 353 257 257 66 27 27 27 325 345 345 15 365 81 83 60 60 255 255 255 0 0 0 0 0 0 0
0 0 0 392 392 392 10 10 241 241 46 343 343 343 280 280 57 57 57 183 183 183 141 141 257 257 102 66 27 325 325 325 15 15 15 15 81 81 60 60 255 255 255 341 0 0 0 0 0 0
0 0 0 0 392 10 10 10 241 46 46 166 166 343 280 280 162 57 183 183 183 381 257 257 257 257 102 66 372 325 340 5 5 169 169 81 81 81 249 249 249 165 165 341 0 0 0 0 0 0
0 0 0 0 0 0 0 0 241 64 64 166 166 400 400 400 162 57 330 330 381 381 381 381 125 125 102 66 372 340 340 367 5 5 169 169 169 81 249 229 165 165 165 341 341 215 201 0 0 0
0 0 0 0 0 0 0 0 64 64 13 13 13 400 400 400 162 162 330 330 381 381 381 125 125 102 102 372 372 340 367 367 367 96 96 169 169 196 196 229 229 165 84 84 84 215 201 201 201 0
0 328 328 68 68 0 0 0 160 13 13 89 89 400 400 2 2 2 386 330 111 111 111 176 176 102 102 243 243 243 243 208 367 96 245 196 196 196 229 229 229 165 84 84 215 215 263 263 0 0
0 328 328 68 68 68 0 0 160 160 13 89 89 198 2 2 2 386 386 330 4 4 111 176 176 298 298 101 101 101 243 208 208 96 245 30 30 62 62 62 190 190 190 108 108 143 263 263 0 0
0 0 0 99 99 370 121 160 160 160 13 235 235 198 198 198 386 386 386 386 4 4 111 124 124 298 298 314 314 101 303 208 208 245 245 30 30 62 62 385 385 385 190 108 108 143 143 0 0 0
0 0 99 99 99 370 121 121 121 294 294 294 235 235 235 271 271 271 271 106 106 106 111 124 124 154 154 314 314 303 303 61 208 146 146 30 62 62 62 385 385 385 192 192 192 143 143 0 0 0
0 0 0 0 370 370 121 282 293 294 294 390 390 181 181 181 181 271 271 271 271 106 53 53 124 154 154 352 352 303 303 61 61 61 146 146 146 146 385 385 288 288 192 192 192 192 192 134 0 0
0 0 211 211 211 121 121 282 293 293 390 390 390 197 221 221 0 0 19 19 53 53 53 53 54 54 154 352 352 352 352 312 1 1 388 146 139 164 164 288 288 273 273 85 85 85 85 134 134 134
0 0 211 211 211 211 282 282 293 293 390 197 197 197 221 221 221 0 0 19 19 70 70 70 54 396 105 105 105 7 352 312 1 1 388 139 139 139 164 288 362 273 273 85 85 0 0 0 134 134
0 0 0 0 0 51 247 247 293 293 310 310 94 94 94 94 221 221 0 391 391 391 391 70 54 396 105 7 7 7 312 312 228 228 388 388 388 139 164 362 362 251 251 191 191 0 0 0 0 0
0 32 0 0 0 51 129 247 247 247 247 310 310 189 189 189 20 20 0 391 138 391 391 281 396 396 105 250 250 250 363 363 228 283 283 223 223 139 219 362 362 251 251 191 191 0 0 0 0 0
0 32 0 237 237 51 129 247 0 0 332 332 91 91 91 189 20 20 0 0 138 391 281 281 396 396 105 0 0 250 363 363 228 283 283 223 223 167 219 219 219 335 335 335 335 130 130 79 0 0
0 32 32 237 237 51 129 129 0 8 8 332 332 91 91 0 0 0 0 138 138 281 281 281 376 376 105 0 250 250 363 313 313 283 77 77 77 167 219 219 219 219 335 335 0 130 130 79 0 0
0 0 32 237 237 237 129 315 0 0 8 8 8 0 0 0 0 277 277 311 311 311 311 326 326 376 0 0 254 250 250 313 313 313 0 0 77 167 167 0 0 0 0 0 0 130 130 79 0 0
0 0 0 0 0 0 0 315 0 0 0 0 0 0 0 0 0 277 277 0 0 311 311 326 326 376 0 0 254 116 116 0 313 313 0 0 0 175 175 0 0 0 0 0 185 185 130 79 0 0
0 0 0 0 0 0 315 315 0 0 0 0 0 0 0 0 0 0 0 0 0 0 326 326 326 0 0 254 254 116 116 0 0 0 0 0 0 175 175 175 0 0 0 0 185 185 130 0 0 0

出力例 1

10
15
1
15
20
19
10
18
19
2
7
14
18
12
9
2
8
5
10
15
16
2
3
5
16
3
9
3
2
4
5
18
1
6
20
12
19
7
17
16
14
2
9
5
3
8
1
9
1
19
18
20
10
10
11
20
15
11
3
20
10
4
6
8
8
9
12
18
11
10
19
12
5
16
2
12
4
19
13
12
20
7
20
4
13
9
14
14
18
11
18
5
8
15
6
4
6
7
18
19
15
9
1
5
10
15
3
4
11
3
15
16
3
3
2
10
5
1
11
2
18
8
3
15
9
19
5
14
18
13
1
17
6
13
1
7
17
10
13
3
9
3
4
7
16
4
3
17
14
16
6
3
3
10
17
1
19
2
14
18
11
15
6
13
4
8
4
3
20
1
1
9
11
12
4
15
2
1
16
5
15
14
15
12
13
3
16
6
15
4
13
4
17
12
17
20
15
15
2
2
4
14
7
19
11
7
16
4
1
12
18
16
9
19
4
11
8
19
13
16
15
19
13
12
1
14
1
4
4
19
19
17
20
8
15
3
18
11
2
1
8
9
15
14
4
9
18
20
20
10
13
17
5
10
20
8
9
2
9
12
5
2
4
16
1
11
14
16
12
19
10
16
13
2
14
19
10
9
5
15
10
18
4
6
5
2
7
13
8
19
2
2
18
18
3
17
12
15
16
6
19
7
10
1
7
7
12
17
14
18
10
10
4
15
18
19
16
19
17
12
17
5
1
1
9
10
6
18
9
15
5
18
14
11
13
1
11
6
9
20
4
6
8
16
9
11
14
1
3
8
1
10
9
14
14
6
16
12
15
3
8
13
4
3
20
19
15
17
11
18
17
20
20
11
1
10
3
6
14
14
9
14
5
9
13
15
3
4
19
15
10
2
15
11
3
10
12
9
3
8

この出力例では p_{min} = 883111, p_{max} = 2041166, q_{min} = 18267, q_{max} = 39399 となっているため、このテストケースに対して 432650 点が得られます。