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 \rfloor を x を超えない最大の整数とします。
ステップ 1. 地区に分割
まず、J = \lfloor 1.2 \times K \rfloor として、N \times N のマス目を以下のようにして J 個の地区に分割します。
- 最初、各マスが異なる地区に属するとして、合計 N^2 個の地区があるとする。
- 以下の処理を N^2 - J 回繰り返す。
- 隣り合っている 2 つの地区のペアのなかで、合計マス数が最小になるものを選ぶ。このようなペアが複数ある場合は、その中から無作為に 1 つ選ぶ。
- 選んだ 2 つの地区を合併し、1 つの地区にする。
ステップ 2. KYOPRO 市の地区の割り当て
ステップ 1 で生成した J 個の地区のうち J - K 個を除去した後、残った K 個の地区に番号を割り振ります。具体的な手順は以下のようになります。
- 以下の処理を J - K 回繰り返す。
- 市の境界に面する地区をランダムに 1 つ選ぶ。
- 選んだ地区を除去しても市が連結になるなら、その地区を除去する。そうでないなら、前述の処理をもう一度行う。
- 残った K 個の地区に、1 から K までの番号を無作為に割り振る。
ステップ 3. 人口・役所職員数の設定
地区 k の人口 A_k および B_k は、以下のように生成します。
- A_k は 50000 以上 100000 以下の整数の中から無作為に選ばれる
- B_k は 1000 以上 2000 以下の整数の中から無作為に選ばれる
入力データのサンプル
入力データのサンプルは、ここをクリック するとダウンロードすることができます。ダウンロードで得られる ZIP ファイルの中には 100 個の入力ケースが入っており、手元でのテストなどに利用できます。そのうち in000.txt
が入力例に対応しています。なお、これらの入力データのサンプルは、実際の採点に使われる入力データとは異なります。
入力例 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 点が得られます。