← Back to Notebook

Typical90_All_Problems_ZH

2026-08-28Page Views

競程典型 90 問（Typical 90）全題目繁體中文題本

本題本收錄 AtCoder 經典題集 《競プロ典型 90 問》（Typical 90） 全部 90 道題目之完整繁體中文翻譯、限制條件、輸入輸出格式與範例測資詳解。 原題集由 E869120 企劃出題，涵蓋演算法競賽中最核心的思維模式與技巧（★2 至 ★7 難度）。

題目目錄（Table of Contents）

Table content rendering (requires nested block fetching)

001 - 羊羹派對 / Yokan Party（★4）

題目描述

有一條長度為 LL cm 的長條狀羊羹。上面標記了 NN 個切割點，從左數來第 ii 個切割點位於距離左端 AiA_i cm 的位置。

你想要從這 NN 個切割點中選出 KK 個進行切割，將羊羹切成 K+1K+1 塊。我們將此時的得分定義如下：

  • K+1K+1 塊羊羹中，最短那一塊的長度（以 cm 為單位）

請計算在最佳切割方式下所能獲得的最大得分。

數據範圍

  • 1≤K≤N≤1000001 \leq K \leq N \leq 100000
  • 0<A1<A2<⋯<AN<L≤1090 \lt A_1 \lt A_2 \lt \cdots \lt A_N \lt L \leq 10^9
  • 所有輸入皆為整數

輸入格式

N L
K
A_1 A_2 … A_N

輸出格式

請輸出所求的最大得分。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 34
1
8 13 26

輸出：

13

說明： 若選擇在從左數來第 22 個切割點切開，羊羹將被分為長度 1313 cm 與長度 2121 cm 的兩塊，可獲得得分 1313。

❌ Unsupported block (heading_4)

輸入：

7 45
2
7 11 16 20 28 34 38

輸出：

12

說明： 若選擇在從左數來第 33 個與第 55 個切割點切開，可獲得得分 1212。

❌ Unsupported block (heading_4)

輸入：

3 100
1
28 54 81

輸出：

46

說明： 若選擇在從左數來第 22 個切割點切開，可獲得得分 4646。

❌ Unsupported block (heading_4)

輸入：

3 100
2
28 54 81

輸出：

26

❌ Unsupported block (heading_4)

輸入：

20 1000
4
51 69 102 127 233 295 350 388 417 466 469 523 553 587 720 739 801 855 926 954

輸出：

170

002 - 括號百科全書 / Encyclopedia of Parentheses（★3）

題目描述

請按字典序輸出所有長度為 NN 的合法括號序列。

其中，合法括號序列的定義如下：

  • () 是合法括號序列。
  • 若 SS 是合法括號序列，則字串 ( +S++ S + ) 也是合法括號序列。
  • 若 S,TS, T 皆為合法括號序列，則字串 S+TS + T 也是合法括號序列。
  • 除此之外的字串皆不是合法括號序列。

例如：

  • ()()
  • (()())(())
  • ()()()()()()()()

是合法括號序列，而

  • )(
  • )))()(((
  • ((((a))))

則不是合法括號序列。

另外，在字典序中定義 ( 優先於 )（即 ( 小於 )）。

數據範圍

  • 1≤N≤201 \leq N \leq 20
  • NN 為整數

輸入格式

N

輸出格式

請將所有長度為 NN 的合法括號序列依字典序輸出，每行輸出一個。

範例測資

❌ Unsupported block (heading_4)

輸入：

2

輸出：

()

說明： 長度為 22 的合法括號序列僅有 ()。

❌ Unsupported block (heading_4)

輸入：

3

輸出：

說明： ※ 也可能存在完全沒有輸出的情況。

❌ Unsupported block (heading_4)

輸入：

4

輸出：

(())
()()

❌ Unsupported block (heading_4)

輸入：

10

輸出：

((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()

003 - 最長環狀道路 / Longest Circular Road（★4）

題目描述

有 NN 座城市，編號分別為 11 到 NN。 另外有 N−1N-1 條道路，第 ii 條道路 (1≤i≤N−1)(1 \leq i \leq N-1) 雙向連接城市 AiA_i 與城市 BiB_i。 保證任兩座城市之間都可以透過若干條道路互相連通。

現在，你可以自由選擇兩個整數 u,vu, v (1≤u<v≤N)(1 \leq u \lt v \leq N)，並新建一條雙向連接城市 uu 與城市 vv 的道路。我們將此時的得分定義如下：

  • 不重複經過同一條道路的前提下，從某座城市出發並回到同一座城市的路徑中所經過的道路數量（該值是唯一確定的）。

請輸出所有可能獲得的得分中的最大值。

數據範圍

  • 3≤N≤1000003 \leq N \leq 100000
  • 1≤Ai<Bi≤N1 \leq A_i \lt B_i \leq N (1≤i≤N−1)(1 \leq i \leq N-1)
  • 任兩座城市之間皆可透過若干條道路互相連通
  • 所有輸入皆為整數

輸入格式

N
A_1 B_1
⋮
A_{N-1} B_{N-1}

輸出格式

請輸出題目定義的得分之最大可能值。

範例測資

❌ Unsupported block (heading_4)

輸入：

3
1 2
2 3

輸出：

3

說明： 在城市 11 與城市 33 之間新建一條道路。如此一來，沿著「城市 11 → 城市 22 → 城市 33 → 城市 11」的路徑所經過的道路數量為 33 條，可獲得得分 33。

❌ Unsupported block (heading_4)

輸入：

5
1 2
2 3
3 4
3 5

輸出：

4

說明： 在城市 11 與城市 55 之間新建一條道路。如此一來，沿著「城市 11 → 城市 22 → 城市 33 → 城市 55 → 城市 11」的路徑所經過的道路數量為 44 條，可獲得得分 44。

❌ Unsupported block (heading_4)

輸入：

10
1 2
1 3
2 4
4 5
4 6
3 7
7 8
8 9
8 10

輸出：

8

❌ Unsupported block (heading_4)

輸入：

31
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8 16
8 17
9 18
9 19
10 20
10 21
11 22
11 23
12 24
12 25
13 26
13 27
14 28
14 29
15 30
15 31

輸出：

9

004 - 十字加總 / Cross Sum（★2）

題目描述

有一個 HH 列 WW 行的方格棋盤。由上數來第 ii 列 (1≤i≤H)(1 \leq i \leq H)、由左數來第 jj 行 (1≤j≤W)(1 \leq j \leq W) 的方格 (i,j)(i, j) 上寫有整數 Ai,jA_{i, j}。 對於所有方格 (i,j)(i, j) (1≤i≤H,1≤j≤W)(1 \leq i \leq H, 1 \leq j \leq W)，請計算以下數值：

  • 與方格 (i,j)(i, j) 位於同一列或同一行的所有方格（包含自身）上所寫整數的總和。

數據範圍

  • 2≤H,W≤20002 \leq H, W \leq 2000
  • 1≤Ai,j≤991 \leq A_{i, j} \leq 99
  • 所有輸入皆為整數

輸入格式

H W
A_{1, 1} A_{1, 2} … A_{1, W}
A_{2, 1} A_{2, 2} … A_{2, W}
⋮
A_{H, 1} A_{H, 2} … A_{H, W}

輸出格式

設與方格 (i,j)(i, j) 位於同一列或同一行的所有方格（包含自身）上整數的總和為 Bi,jB_{i, j}，請依以下格式輸出：

B_{1, 1} B_{1, 2} … B_{1, W}
B_{2, 1} B_{2, 2} … B_{2, W}
⋮
B_{H, 1} B_{H, 2} … B_{H, W}

範例測資

❌ Unsupported block (heading_4)

輸入：

3 3
1 1 1
1 1 1
1 1 1

輸出：

5 5 5
5 5 5
5 5 5

❌ Unsupported block (heading_4)

輸入：

4 4
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3

輸出：

28 28 25 26
39 33 40 34
38 38 36 31
41 41 39 43

說明： 與方格 (1,1)(1, 1) 位於同一列或同一行的方格上所寫整數的總和如下：

  • 3+1+4+1+5+5+9=283+1+4+1+5+5+9=28

❌ Unsupported block (heading_4)

輸入：

2 10
31 41 59 26 53 58 97 93 23 84
62 64 33 83 27 95 2 88 41 97

輸出：

627 629 598 648 592 660 567 653 606 662
623 633 651 618 645 650 689 685 615 676

❌ Unsupported block (heading_4)

輸入：

10 10
83 86 77 65 93 85 86 92 99 71
62 77 90 59 63 76 90 76 72 86
61 68 67 79 82 80 62 73 67 85
79 52 72 58 69 67 93 56 61 92
79 73 71 69 84 87 98 74 65 70
63 76 91 80 56 73 62 70 96 81
55 75 84 77 86 55 96 79 63 57
74 95 82 95 64 67 84 64 93 50
87 58 76 78 88 84 53 51 54 99
82 60 76 68 89 62 76 86 94 89

輸出：

1479 1471 1546 1500 1518 1488 1551 1466 1502 1546
1414 1394 1447 1420 1462 1411 1461 1396 1443 1445
1388 1376 1443 1373 1416 1380 1462 1372 1421 1419
1345 1367 1413 1369 1404 1368 1406 1364 1402 1387
1416 1417 1485 1429 1460 1419 1472 1417 1469 1480
1410 1392 1443 1396 1466 1411 1486 1399 1416 1447
1397 1372 1429 1378 1415 1408 1431 1369 1428 1450
1419 1393 1472 1401 1478 1437 1484 1425 1439 1498
1366 1390 1438 1378 1414 1380 1475 1398 1438 1409
1425 1442 1492 1442 1467 1456 1506 1417 1452 1473

005 - 受限的數字 / Restricted Digits（★7）

題目描述

僅使用數字 c1,c2,…,cKc_1, c_2, \dots, c_K 所能構成的 NN 位正整數中，有多少個是 BB 的倍數？請計算其數量除以 109+710^9 + 7 的餘數。

數據範圍

  • 1≤K≤91 \leq K \leq 9
  • 1≤c1<c2<⋯<cK≤91 \leq c_1 \lt c_2 \lt \cdots \lt c_K \leq 9
  • 1≤N≤10181 \leq N \leq 10^{18}
  • 2≤B≤10002 \leq B \leq 1000
  • 所有輸入皆為整數

輸入格式

N B K
c_1 c_2 … c_K

輸出格式

請輸出答案除以 109+710^9 + 7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 7 3
1 4 9

輸出：

3

說明： 由 1,4,91, 4, 9 所構成的 33 位數中，77 的倍數有 119,441,994119, 441, 994 共 33 個。

❌ Unsupported block (heading_4)

輸入：

5 2 3
1 4 9

輸出：

81

❌ Unsupported block (heading_4)

輸入：

10000 27 7
1 3 4 6 7 8 9

輸出：

989112238

❌ Unsupported block (heading_4)

輸入：

1000000000000000000 29 6
1 2 4 5 7 9

輸出：

853993813

說明： ※ 此範例測資僅滿足子任務 2,32, 3 的約束條件。

❌ Unsupported block (heading_4)

輸入：

1000000000000000000 957 7
1 2 3 5 6 7 9

輸出：

205384995

說明： ※ 此範例測資僅滿足子任務 33 的約束條件。

006 - 最小子序列 / Smallest Subsequence（★5）

題目描述

給定一個長度為 NN 且僅由小寫英文字母組成的字串 SS。

請在 SS 的所有長度為 KK 的子序列中，找出字典序最小的字串並輸出。

數據範圍

  • 1≤K≤N≤1000001 \leq K \leq N \leq 100000
  • SS 是長度為 NN 且僅由小寫英文字母組成的字串
  • N,KN, K 為整數

輸入格式

N K
S

輸出格式

請輸出符合條件的字典序最小字串。

範例測資

❌ Unsupported block (heading_4)

輸入：

7 3
atcoder

輸出：

acd

說明： 取第 1,3,51, 3, 5 個字元可得到字串 acd。 該字串是所有長度為 33 的子序列中字典序最小的。

❌ Unsupported block (heading_4)

輸入：

14 5
kittyonyourlap

輸出：

inlap

007 - 程式競賽分班 / CP Classes（★3）

題目描述

ABC 程式競賽補習班開設了 NN 個班級，編號為 ii (1≤i≤N)(1 \leq i \leq N) 的班級適合目標 Rating 為 AiA_i 的學生。

現在有 QQ 位學生準備進入該補習班。 編號為 jj (1≤j≤Q)(1 \leq j \leq Q) 的學生的 Rating 為 BjB_j。 每位學生如果進入不適合自己程度的班級都會感到不滿。 對每位學生而言，其不滿度定義如下：

  • 班級目標 Rating aa 與自身 Rating bb 差值的絕對值，即 ∣a−b∣|a-b|

對於每個 j=1,2,3,…,Qj = 1, 2, 3, \ldots, Q，請分別計算編號為 jj 的學生在選擇班級時可能產生的最小不滿度。 注意：允許某些班級沒有任何學生加入，也允許一個班級有多名學生加入。

數據範圍

  • 1≤N≤3000001 \leq N \leq 300000
  • 1≤Q≤3000001 \leq Q \leq 300000
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • 0≤Bj≤1090 \leq B_j \leq 10^9
  • 所有輸入皆為整數

輸入格式

N
A_1 A_2 A_3 … A_N
Q
B_1
B_2
B_3
⋮
B_Q

輸出格式

對於每個 j=1,2,3,…,Qj = 1, 2, 3, \ldots, Q，請依序在標準輸出一行輸出答案，總共輸出 QQ 行。

範例測資

❌ Unsupported block (heading_4)

輸入：

4
4000 4400 5000 3200
3
3312
2992
4229

輸出：

112
208
171

❌ Unsupported block (heading_4)

輸入：

1
4000
10
3582
3538
3320
3312
3296
3257
3111
3040
3013
2994

輸出：

418
462
680
688
704
743
889
960
987
1006

❌ Unsupported block (heading_4)

輸入：

10
869120000 998244353 777777777 123456789 100100100 464646464 987654321 252525252 869120001 1000000000
10
4229
20210406
1
268435456
3582
536870912
1000000000
869120
99999999
869120001

輸出：

100095871
79889694
100100099
15910204
100096518
72224448
0
99230980
100101
0

❌ Unsupported block (heading_4)

輸入：

100
298750376 229032640 602876667 944779015 909539868 533609371 231368330 445484152 408704870 850216874 349286798 30417810 807260002 554049450 40706045 380488344 749325840 801881841 459457853 66691229 5235900 8100458 46697277 997429858 827651689 790051948 981897272 271364774 536232393 997361572 449659237 602191750 294800444 346669663 792837293 277667068 997282249 468293808 444906878 702693341 894286137 845317003 27053625 926547765 739689211 447395911 902031510 326127348 582956343 842918193 235655766 844300842 438389323 406413067 862896425 464876303 68833418 76340212 911399808 745744264 551223563 854507876 196296968 52144186 431165823 275217640 424495332 847375861 337078801 83054466 648322745 694789156 301518763 319851750 432518459 772897937 630628124 581390864 313132255 350770227 642944345 677742851 448945480 688009163 160941957 290297295 5532462 823543277 19634445 15791361 193309093 66202596 72364149 743270896 297240520 264035189 898589962 59916738 307942952 403411309
30
930579110
22697034
44652533
280533771
753567118
684927419
923477579
557613803
779616458
389130756
323671659
3117850
408004003
224808850
18421958
359047808
364572866
334631363
854759331
647435074
826055423
668443532
620408208
32237184
67299071
251185742
217292659
16181227
850865411
218577687

輸出：

4031345
3062589
2044744
2866703
4241278
3081744
3070186
3564353
6718521
8642412
2455689
2118050
700867
4223790
1212487
8277581
13802639
2447438
251455
887671
1596266
9299319
10219916
1819374
607842
12849447
11739981
389866
648537
10454953

008 - AtCoder 計數 / AtCounter（★4）

題目描述

給定一個長度為 NN 且僅由小寫英文字母組成的字串 SS。令 SS 的第 ii 個字元為 sis_i。

從 SS 中取出 00 個以上字元的方法共有 2N2^{N} 種，其中滿足以下條件的選取方式共有多少種？由於答案可能非常大，請輸出答案除以 109+710^9 + 7 的餘數。

  • 將取出的字元按照原本的先後順序連接後，構成的字串為 "atcoder"。

注意：若存在至少一個字元 sis_i (1≤i≤N)(1 \leq i \leq N) 在兩種選取方式中僅其中一種被取出，則這兩種「取出字元的方法」被視為不同。

數據範圍

  • 1≤N≤100,0001 \leq N \leq 100{,}000
  • ∣S∣=N|S| = N
  • 字串 SS 僅由小寫英文字母組成

輸入格式

N
S

輸出格式

請輸出答案除以 109+710^9 + 7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

10
attcordeer

輸出：

4

說明： 能夠構成子序列 "atcoder" 的例子之一是選取 SS 的第 (1,2,4,5,7,8,10)(1, 2, 4, 5, 7, 8, 10) 個字元。除此之外還有另外 33 種滿足條件的子序列選取方式，因此答案共有 44 種。

❌ Unsupported block (heading_4)

輸入：

41
btwogablwetwoiehocghiewobadegwhoihegnldir

輸出：

2

❌ Unsupported block (heading_4)

輸入：

140
aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr

輸出：

279999993

說明： 請輸出答案除以 109+710^9 + 7 的餘數。

009 - 三點夾角 / Three Point Angle（★6）

題目描述

座標平面上有相異的 NN 個點 P1,…,PNP_1, \dots, P_N，其中點 PiP_i 的座標為 (Xi,Yi)(X_i, Y_i)。

從這 NN 個點中選出相異的 3 個點 Pi,Pj,PkP_i, P_j, P_k，我們希望最大化 ∠PiPjPk\angle P_i P_j P_k。請以度數法（度）為單位輸出此最大值。

這裡規定 0∘≤∠PiPjPk≤180∘0^\circ \leq \angle P_i P_j P_k \leq 180^{\circ}。

關於 ∠PiPjPk\angle P_i P_j P_k： 指由折線「點 Pi→P_i \to 點 Pj→P_j \to 點 PkP_k」所構成的角度大小（即以 PjP_j 為頂點的夾角）。

數據範圍

  • 3≤N≤20003 \leq N \leq 2000
  • 0≤Xi,Yi≤1090 \leq X_i, Y_i \leq 10^9 (1≤i≤N)(1 \leq i \leq N)
  • (Xi,Yi)≠(Xj,Yj)(X_i, Y_i) \neq (X_j, Y_j) (1≤i<j≤N)(1 \leq i < j \leq N)
  • 所有輸入數值皆為整數

輸入格式

N
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N

輸出格式

請以度數法輸出 ∠PiPjPk\angle P_i P_j P_k 的最大值。 若輸出的相對誤差或絕對誤差在 10−710^{-7} 以下，則視為正確答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

3
0 0
0 10
10 10

輸出：

90

說明：P1,P2,P3P_1, P_2, P_3 的座標分別為 (0,0),(0,10),(10,10)(0, 0), (0, 10), (10, 10)。

  • ∠P1P2P3=90∘\angle P_1 P_2 P_3 = 90^\circ
  • ∠P2P3P1=45∘\angle P_2 P_3 P_1 = 45^\circ
  • ∠P3P1P2=45∘\angle P_3 P_1 P_2 = 45^\circ

其中最大值為 ∠P1P2P3=90∘\angle P_1 P_2 P_3 = 90^\circ，因此輸出 90 即可。

❌ Unsupported block (heading_4)

輸入：

5
8 6
9 1
2 0
1 0
0 1

輸出：

171.869897645844

說明：∠P2P3P4=171.869⋯∘\angle P_2 P_3 P_4 = 171.869\cdots^\circ 為最大值。

❌ Unsupported block (heading_4)

輸入：

10
0 0
1 7
2 6
2 8
3 5
5 5
6 7
7 1
7 9
8 8

輸出：

180

說明：∠P1P6P10=180∘\angle P_1 P_6 P_{10}=180^\circ 為最大值。

❌ Unsupported block (heading_4)

輸入：

40
298750376 229032640
602876667 944779015
909539868 533609371
231368330 445484152
408704870 850216874
349286798 30417810
807260002 554049450
40706045 380488344
749325840 801881841
459457853 66691229
5235900 8100458
46697277 997429858
827651689 790051948
981897272 271364774
536232393 997361572
449659237 602191750
294800444 346669663
792837293 277667068
997282249 468293808
444906878 702693341
894286137 845317003
27053625 926547765
739689211 447395911
902031510 326127348
582956343 842918193
235655766 844300842
438389323 406413067
862896425 464876303
68833418 76340212
911399808 745744264
551223563 854507876
196296968 52144186
431165823 275217640
424495332 847375861
337078801 83054466
648322745 694789156
301518763 319851750
432518459 772897937
630628124 581390864
313132255 350770227

輸出：

179.9834340684232

010 - 區間得分總和查詢 / Score Sum Queries（★2）

題目描述

ABC 大學有 NN 名一年級學生。一年級共有 22 個班級，學號為 ii 的學生屬於第 CiC_i 班。今天是期末考成績公布的日子，學號為 ii 的學生期末考成績為 PiP_i 分。

現在給定 QQ 個以下格式的詢問，請分別對每個 j=1,2,…,Qj = 1, 2, \dots, Q 進行回答：

  • 學號在 Lj∼RjL_j \sim R_j 之間的第 11 班學生期末考成績總和。
  • 學號在 Lj∼RjL_j \sim R_j 之間的第 22 班學生期末考成績總和。
  • 分別求出這兩個數值。

數據範圍

  • 1≤N≤1000001 \leq N \leq 100000
  • 1≤Ci≤21 \leq C_i \leq 2
  • 0≤Pi≤1000 \leq P_i \leq 100
  • 1≤Q≤1000001 \leq Q \leq 100000
  • 1≤Lj≤Rj≤N1 \leq L_j \leq R_j \leq N
  • 所有輸入皆為整數

輸入格式

N
C_1 P_1
C_2 P_2
⋮
C_N P_N
Q
L_1 R_1
L_2 R_2
⋮
L_Q R_Q

輸出格式

設學號在 Lj∼RjL_j \sim R_j 之間的第 11 班學生期末考成績總和為 AjA_j、第 22 班學生期末考成績總和為 BjB_j，請依以下格式輸出：

A_1 B_1
A_2 B_2
⋮
A_Q B_Q

範例測資

❌ Unsupported block (heading_4)

輸入：

7
1 72
2 78
2 94
1 23
2 89
1 40
1 75
1
2 6

輸出：

63 261

說明： 學號在 2∼62 \sim 6 之間的第 11 班學生，期末考成績總和為 23+40=6323+40=63 分。 學號在 2∼62 \sim 6 之間的第 22 班學生，期末考成績總和為 78+94+89=26178+94+89=261 分。

❌ Unsupported block (heading_4)

輸入：

7
1 72
2 78
2 94
1 23
2 89
1 40
1 75
10
1 3
2 4
3 5
4 6
5 7
1 5
2 6
3 7
1 6
2 7

輸出：

72 172
23 172
23 183
63 89
115 89
95 261
63 261
138 183
135 261
138 261

❌ Unsupported block (heading_4)

輸入：

1
1 100
3
1 1
1 1
1 1

輸出：

100 0
100 0
100 0

說明： ※ 也可能存在某一個班級完全沒有學生的情況。

❌ Unsupported block (heading_4)

輸入：

20
2 90
1 67
2 9
2 17
2 85
2 43
2 11
1 32
2 16
1 19
2 65
1 14
1 51
2 94
1 4
1 55
2 90
1 89
1 35
2 81
20
3 17
5 5
11 11
8 10
3 13
2 6
3 7
3 5
12 18
4 8
3 16
6 8
3 20
1 12
1 6
5 16
3 10
17 19
4 4
7 15

輸出：

175 430
0 85
0 65
51 16
116 246
67 154
0 165
0 111
213 184
32 156
175 340
32 54
299 511
132 336
67 244
175 314
51 181
124 90
0 17
120 186

011 - 肥缺工作 / Gravy Jobs（★6）

題目描述

ABC 君收到了 NN 件工作委託。每件工作依序編號為 1,2,…,N1, 2, \dots, N。

工作 ii 的截止期限為第 DiD_i 天結束時，且需要花費連續 CiC_i 天才能完成。無法透過其他方式完成該工作。

更精確地說，要在截止期限前完成工作 ii，對於某個滿足 Ci≤k≤DiC_i \leq k \leq D_i 的整數 kk，必須從第 k−Ci+1k - C_i + 1 天開始到第 kk 天結束為止，連續進行第 ii 件工作。

在截止期限前完成工作 ii 可獲得 SiS_i 元的報酬。每天最多只能進行 11 種工作。

現在是第 11 天的開始。若 ABC 君妥善選擇要承接的工作並安排排程，請求出他所能獲得的報酬金額的最大可能值。

數據範圍

  • 1≤N≤50001 \leq N \leq 5000
  • 1≤Di≤5000 (1≤i≤N)1 \leq D_i \leq 5000\ (1 \leq i \leq N)
  • 1≤Ci≤5000 (1≤i≤N)1 \leq C_i \leq 5000\ (1 \leq i \leq N)
  • 1≤Si≤109 (1≤i≤N)1 \leq S_i \leq 10^9\ (1 \leq i \leq N)
  • 所有輸入皆為整數

輸入格式

N
D_1 C_1 S_1
D_2 C_2 S_2
⋮
D_N C_N S_N

輸出格式

請在一行中輸出 ABC 君能獲得的報酬金額的最大可能值。

範例測資

❌ Unsupported block (heading_4)

輸入：

1
12 3 69853

輸出：

69853

說明： 從第 11 天到第 33 天花費 33 天完成第 11 件工作，可以獲得 6985369853 元。

由於無法獲得超過 6985369853 元的報酬，因此答案為 6985369853 元。

❌ Unsupported block (heading_4)

輸入：

3
7 3 200000
3 2 100000
5 3 150000

輸出：

350000

說明： 從第 22 天到第 44 天花費 33 天完成第 33 件工作，從第 55 天到第 77 天花費 33 天完成第 11 件工作，可以獲得 350000350000 元。

由於無法獲得超過 350000350000 元的報酬，因此答案為 350000350000 元。

❌ Unsupported block (heading_4)

輸入：

8
376 640 602876667
4015 1868 533609371
3330 152 408704870
1874 798 30417810
2 1450 40706045
3344 1840 801881841
2853 1229 5235900
458 1277 997429858

輸出：

1744196082

❌ Unsupported block (heading_4)

輸入：

20
376 640 602876667
4015 868 533609371
3330 152 408704870
1874 798 30417810
2 450 40706045
3344 840 801881841
2853 229 5235900
458 277 997429858
1689 948 981897272
4774 393 997361572
4237 750 294800444
4663 293 277667068
2249 808 444906878
3341 137 845317003
3625 765 739689211
911 510 326127348
1343 193 235655766
842 323 406413067
1425 303 68833418
212 808 745744264

輸出：

6583558066

說明： 此範例輸入不符合子任務 11 的限制，但符合子任務 2,32, 3 的限制。

❌ Unsupported block (heading_4)

輸入：

30
376 140 602876667
4015 368 533609371
3330 152 408704870
1874 298 30417810
2 450 40706045
3344 340 801881841
2853 229 5235900
458 277 997429858
1689 448 981897272
4774 393 997361572
4237 250 294800444
4663 293 277667068
2249 308 444906878
3341 137 845317003
3625 265 739689211
911 10 326127348
1343 193 235655766
842 323 406413067
1425 303 68833418
212 308 745744264
3563 376 196296968
4186 323 275217640
332 361 337078801
4466 245 694789156
3763 250 432518459
2937 124 581390864
2255 227 642944345
2851 480 688009163
1957 295 5532462
3277 445 15791361

輸出：

11420667389

說明： 此範例輸入不符合子任務 1,21, 2 的限制，但符合子任務 33 的限制。

012 - 塗成紅色 / Red Painting（★4）

題目描述

有一個 HH 行 WW 列的網格，從上數來第 ii 行 (1≤i≤H)(1 \leq i \leq H)、從左數來第 jj 列 (1≤j≤W)(1 \leq j \leq W) 的方格表示為 (i,j)(i, j)。

一開始所有方格都是白色的。接著會依序給出 QQ 個以下形式的查詢。

對於第 ii 個 (1≤i≤Q)(1 \leq i \leq Q) 查詢：

  • 當 ti=1t_i = 1 時： 給定整數 ri,cir_i, c_i。 白色方格 (ri,ci)(r_i, c_i) 被塗成紅色。
  • 當 ti=2t_i = 2 時： 給定整數 rai,cai,rbi,cbi{ra}_i, {ca}_i, {rb}_i, {cb}_i。 若同時滿足以下兩個條件則輸出 Yes，否則輸出 No：

請依序處理這 QQ 個查詢。

數據範圍

  • 1≤H,W≤20001 \leq H, W \leq 2000
  • 1≤Q≤1000001 \leq Q \leq 100000
  • 1≤ti≤21 \leq t_i \leq 2
  • 當 ti=1t_i = 1 時，1≤ri≤H1 \leq r_i \leq H、1≤ci≤W1 \leq c_i \leq W
  • 當 ti=2t_i = 2 時，1≤rai,rbi≤H1 \leq {ra}_i, {rb}_i \leq H、1≤cai,cbi≤W1 \leq {ca}_i, {cb}_i \leq W
  • 當 ti=1t_i = 1 且 tj=1t_j = 1 (1≤i<j≤Q)(1 \leq i < j \leq Q) 時，(ri,ci)≠(rj,cj)(r_i, c_i) \neq (r_j, c_j)
  • 所有輸入皆為整數

輸入格式

H W
Q
q_1
⋮
q_Q

其中 qiq_i 代表第 ii 個查詢的資訊，符合以下兩種格式之一：

1 r_i c_i
2 {ra}_i {ca}_i {rb}_i {cb}_i

輸出格式

對於給定的 QQ 個查詢中所有 ti=2t_i = 2 的查詢，依序將處理結果以換行分隔，一行輸出一個結果。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 3
10
1 2 2
1 1 1
2 1 1 2 2
1 3 2
2 1 1 2 2
2 2 2 3 2
1 2 3
1 2 1
2 1 1 2 2
2 1 1 3 3

輸出：

No
No
Yes
Yes
No

說明： 依序處理給定的 1010 個查詢如下：

  • 方格 (2,2)(2, 2) 被塗成紅色。
  • 方格 (1,1)(1, 1) 被塗成紅色。
  • 從方格 (1,1)(1, 1) 無法透過在紅色方格上朝上下左右移動到達方格 (2,2)(2, 2)，因此輸出 No。
  • 方格 (3,2)(3, 2) 被塗成紅色。
  • 從方格 (1,1)(1, 1) 無法透過在紅色方格上朝上下左右移動到達方格 (2,2)(2, 2)，因此輸出 No。
  • 方格 (2,2)(2, 2) 與方格 (3,2)(3, 2) 皆被塗成紅色，且在上下方向相鄰，因此輸出 Yes。
  • 方格 (2,3)(2, 3) 被塗成紅色。
  • 方格 (2,1)(2, 1) 被塗成紅色。
  • 從方格 (1,1)(1, 1) 可以透過依序經過方格 (1,1)→(1, 1) \to 方格 (2,1)→(2, 1) \to 方格 (2,2)(2, 2) 在紅色方格上朝上下左右移動到達，因此輸出 Yes。
  • 從方格 (1,1)(1, 1) 無法透過在紅色方格上朝上下左右移動到達方格 (3,3)(3, 3)，因此輸出 No。

❌ Unsupported block (heading_4)

輸入：

1 1
3
2 1 1 1 1
1 1 1
2 1 1 1 1

輸出：

No
Yes

說明： 請注意沒有任何方格被塗成紅色的情況。

❌ Unsupported block (heading_4)

輸入：

5 5
42
2 3 4 3 4
2 3 2 3 2
1 4 1
2 4 1 2 2
1 1 2
1 4 5
1 3 3
2 4 2 1 3
1 3 5
2 2 4 2 3
2 2 4 2 5
2 3 4 5 1
2 3 1 2 2
2 3 1 1 2
2 2 4 5 2
2 3 2 5 3
1 4 3
2 3 3 3 5
2 3 1 3 2
1 1 5
2 4 4 5 3
1 1 4
2 1 3 2 5
2 4 3 1 4
2 2 3 3 3
1 2 1
1 2 5
2 1 4 5 3
2 4 4 2 5
2 4 2 2 4
1 2 2
2 4 1 5 2
1 2 4
2 3 1 4 1
1 4 4
2 3 2 2 1
2 1 1 5 2
1 4 2
2 4 2 3 5
1 3 2
1 3 4
1 2 3

輸出：

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes

013 - 途經 / Passing（★5）

題目描述

AGC 王國有 NN 座城鎮，編號分別為 1,2,…,N1, 2, \dots, N。此外，有 MM 條連接城鎮的道路。第 ii 條道路雙向連接城鎮 AiA_i 與 BiB_i，通過該道路需要花費 CiC_i 分鐘。

對於每個 k=1,2,…,Nk = 1, 2, \dots, N，求從城鎮 11 出發，途經城鎮 kk 移動到城鎮 NN 所需時間的最小值。

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • 1≤M≤min⁡(100000,N(N−1)2)1 \leq M \leq \min\left(100000, \frac{N(N-1)}{2}\right)
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • (Ai,Bi)≠(Aj,Bj)(A_i, B_i) \neq (A_j, B_j) (1≤i<j≤M)(1 \leq i < j \leq M)
  • 1≤Ci≤100001 \leq C_i \leq 10000
  • 任意兩座城鎮之間都可以透過若干條道路互相到達
  • 所有輸入皆為整數

輸入格式

N M
A_1 B_1 C_1
⋮
A_M B_M C_M

輸出格式

請輸出 NN 行。 第 kk 行 (1≤k≤N)(1 \leq k \leq N) 輸出從城鎮 11 出發，途經城鎮 kk 移動到城鎮 NN 所需時間的最小值（以分鐘為單位）。

範例測資

❌ Unsupported block (heading_4)

輸入：

7 9
1 2 2
1 3 3
2 5 2
3 4 1
3 5 4
4 7 5
5 6 1
5 7 6
6 7 3

輸出：

8
8
9
9
8
8
8

說明： 例如當 k=3k = 3 時，選擇以下路徑是最優的。此時花費的時間為 99 分鐘，因此第 33 行輸出 99。

❌ Unsupported block (heading_4)

輸入：

4 3
1 2 1
2 3 10
3 4 100

輸出：

111
111
111
111

❌ Unsupported block (heading_4)

輸入：

4 3
1 2 314
1 3 159
1 4 265

輸出：

265
893
583
265

014 - 我們曾一起唱歌 / We Used to Sing a Song Together（★3）

題目描述

AGC 街道上住著 NN 位小學生，小學生 ii (1≤i≤N)(1 \leq i \leq N) 的家位於位置 AiA_i。 此外，街道上建有 NN 所小學，小學 jj (1≤j≤N)(1 \leq j \leq N) 位於位置 BjB_j。 住在 AGC 街道上的小學生彼此性格不合、關係緊張，因此希望能讓每個人都就讀不同的小學。

此外，「不便程度」定義如下： - 若將小學生 ii 從家到學校的距離記為 EiE_i，則不便程度為所有距離的總和，即 E1+E2+⋯+ENE_1 + E_2 + \dots + E_N。 - 其中，從位置 uu 到位置 vv 的距離為 ∣u−v∣|u - v|。

在每位學生就讀不同學校的條件下，求不便程度的最小可能值。

數據範圍

  • 1≤N≤1000001 \leq N \leq 100000
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • 0≤Bj≤1090 \leq B_j \leq 10^9
  • A1,A2,…,ANA_1, A_2, \dots, A_N 互不相同
  • B1,B2,…,BNB_1, B_2, \dots, B_N 互不相同
  • 所有輸入皆為整數

輸入格式

N
A_1 A_2 … A_N
B_1 B_2 … B_N

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

1
869
120

輸出：

749

說明： 小學生 11 的家與小學 11 的距離為 ∣869−120∣=749|869 - 120| = 749。 在此輸入中，小學生 11 必定就讀小學 11，因此該值是不便程度唯一可能的值，也是最小值。

❌ Unsupported block (heading_4)

輸入：

6
8 6 9 1 2 0
1 5 7 2 3 9

輸出：

5

說明： 若讓小學生 1,2,3,4,5,61, 2, 3, 4, 5, 6 分別就讀小學 3,2,6,4,5,13, 2, 6, 4, 5, 1，不便程度為 ∣8−7∣+∣6−5∣+∣9−9∣+∣1−2∣+∣2−3∣+∣0−1∣=5|8-7| + |6-5| + |9-9| + |1-2| + |2-3| + |0-1| = 5。 無法使不便程度小於此值，因此答案為 55。

❌ Unsupported block (heading_4)

輸入：

10
31 41 59 26 53 58 97 93 23 84
17 32 5 8 7 56 88 77 29 35

輸出：

211

❌ Unsupported block (heading_4)

輸入：

20
804289382 846930886 681692776 714636914 957747792 424238335 719885386 649760491 596516649 189641420 25202361 350490026 783368690 102520058 44897761 967513925 365180539 540383425 304089172 303455735
35005211 521595368 294702567 726956428 336465782 861021530 278722862 233665123 145174065 468703135 101513928 801979801 315634021 635723058 369133068 125898166 59961392 89018454 628175011 656478041

輸出：

2736647674

015 - 保持距離 / Don’t be too close（★6）

題目描述

有 NN 顆球，上面分別寫著 11 到 NN 的整數。 對於每個 k=1,2,3,…,Nk = 1, 2, 3, \dots, N，請回答以下問題：

  • 從這 NN 顆球中選出 11 顆以上的球，共有 2N−12^N - 1 種選法。其中滿足以下條件的選法有多少種？
  • 由於答案可能非常大，請輸出對 109+710^9+7 取模的結果。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • NN 為整數

輸入格式

N

輸出格式

輸出共有 NN 行。

第 ii 行 (1≤i≤N)(1 \leq i \leq N) 請輸出當 k=ik = i 時的答案對 109+710^9+7 取模的結果。

範例測資

❌ Unsupported block (heading_4)

輸入：

1

輸出：

1

說明： 只有選擇球 11 這一種方法。

❌ Unsupported block (heading_4)

輸入：

2

輸出：

3
2

說明： 當 k=1k=1 時，所選球的集合有 {1}\{1\}、{2}\{2\}、{1,2}\{1,2\} 共 33 種。

當 k=2k=2 時，有 {1}\{1\}、{2}\{2\} 共 22 種。

❌ Unsupported block (heading_4)

輸入：

3

輸出：

7
4
3

❌ Unsupported block (heading_4)

輸入：

4

輸出：

15
7
5
4

❌ Unsupported block (heading_4)

輸入：

7

輸出：

127
33
18
13
10
8
7

❌ Unsupported block (heading_4)

輸入：

20

輸出：

1048575
17710
2744
906
430
250
167
118
90
75
65
56
48
41
35
30
26
23
21
20

❌ Unsupported block (heading_4)

輸入：

50

輸出：

898961330
951279874
262271567
14341526
1985602
466851
153365
63191
30623
16687
9987
6453
4354
3070
2290
1790
1427
1138
910
735
605
512
448
405
375
350
326
303
281
260
240
221
203
186
170
155
141
128
116
105
95
86
78
71
65
60
56
53
51
50

說明： 請輸出對 109+710^9+7 取模的結果。

016 - 最少硬幣 / Minimum Coins（★3）

題目描述

使用 AA 元硬幣、BB 元硬幣、CC 元硬幣各 00 枚以上恰好支付 NN 元時，求所使用硬幣枚數的最小可能值。

保證每種硬幣皆有無限多枚可供使用。

數據範圍

  • 1≤A,B,C,N≤1091 \leq A, B, C, N \leq 10^9
  • A,B,CA, B, C 互不相同
  • 能以合計最多 99999999 枚硬幣恰好支付 NN 元
  • 所有輸入皆為整數

輸入格式

N
A B C

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

227
21 47 56

輸出：

5

說明： 使用 11 枚 2121 元硬幣、22 枚 4747 元硬幣、22 枚 5656 元硬幣來支付是最優的。 合計為 55 枚。

❌ Unsupported block (heading_4)

輸入：

9999
1 5 10

輸出：

1004

說明： 使用 44 枚 11 元硬幣、11 枚 55 元硬幣、999999 枚 1010 元硬幣來支付是最優的。 合計為 10041004 枚。

❌ Unsupported block (heading_4)

輸入：

998244353
314159 265358 97932

輸出：

3333

❌ Unsupported block (heading_4)

輸入：

100000000
10001 10002 10003

輸出：

9998

017 - 相交線段 / Crossing Segments（★7）

題目描述

圓周上有 NN 個點，順時針依序編號為 1,2,…,N1, 2, \dots, N。 另外有 MM 條線段，線段 ii 連接點 LiL_i 與點 RiR_i。

求滿足線段 ss 與線段 tt 在端點以外的位置相交的數對 (s,t)(s, t) (1≤s<t≤M)(1 \leq s < t \leq M) 的數量。

數據範圍

  • 3≤N≤3000003 \leq N \leq 300000
  • 2≤M≤3000002 \leq M \leq 300000
  • 1≤Li<Ri≤N1 \leq L_i < R_i \leq N
  • (Li,Ri)≠(Lj,Rj)(L_i, R_i) \neq (L_j, R_j) (1≤i<j≤M)(1 \leq i < j \leq M)

輸入格式

N M
L_1 R_1
L_2 R_2
⋮
L_M R_M

輸出格式

請輸出滿足線段 s,ts, t 在端點以外的位置相交的數對 (s,t)(s, t) (1≤s<t≤M)(1 \leq s < t \leq M) 的數量。

範例測資

❌ Unsupported block (heading_4)

輸入：

6 3
2 5
1 4
1 3

輸出：

2

❌ Unsupported block (heading_4)

輸入：

250 10
13 218
17 99
24 180
53 115
96 97
111 158
124 164
135 227
158 177
204 224

輸出：

10

❌ Unsupported block (heading_4)

輸入：

100 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11

輸出：

0

❌ Unsupported block (heading_4)

輸入：

100 10
1 100
2 99
3 98
4 97
5 96
6 95
7 94
8 93
9 92
10 91

輸出：

0

❌ Unsupported block (heading_4)

輸入：

1000 40
12 43
23 59
32 118
44 751
68 136
70 168
85 328
88 809
92 981
95 540
98 772
98 903
125 896
173 737
199 325
212 369
227 587
230 374
287 442
306 926
314 858
316 371
318 493
337 506
384 887
387 493
394 457
404 652
414 527
422 920
441 730
445 620
468 602
482 676
568 857
587 966
653 757
710 928
764 927
778 916

輸出：

229

018 - 直大雕像 / Statue of Chokudai（★3）

題目描述

在平面 x=0x = 0 上，有一座高度為 LL、每 TT 分鐘旋轉一圈的摩天輪。 摩天輪呈圓形，並以恆定速度依以下方式運轉。 其中，xyxy 平面為水平方向，zz 軸為垂直方向。

  • 搭乘 00 分鐘後，位於座標 (0,0,0)(0, 0, 0)
  • 搭乘 T4\frac{T}{4} 分鐘後，位於座標 (0,−L2,L2)\left(0, -\frac{L}{2}, \frac{L}{2}\right)
  • 搭乘 T2\frac{T}{2} 分鐘後，位於座標 (0,0,L)(0, 0, L)
  • 搭乘 3T4\frac{3T}{4} 分鐘後，位於座標 (0,L2,L2)\left(0, \frac{L}{2}, \frac{L}{2}\right)

摩天輪的著名地標「高橋直大像」位於座標 (X,Y,0)(X, Y, 0)。 給定 QQ 個以下形式的詢問，請依序回答：

  • 在第 ii 個詢問中，求 E869120 君搭乘摩天輪 EiE_i 分鐘後，從 E869120 君的角度看高橋直大像的俯角。

數據範圍

  • 2≤T≤1092 \leq T \leq 10^9
  • 1≤L,X,Y≤1091 \leq L, X, Y \leq 10^9
  • 1≤Q≤10001 \leq Q \leq 1000
  • 0≤Ei<T0 \leq E_i < T
  • 所有輸入皆以整數給出

輸入格式

T
L X Y
Q
E_1
E_2
⋮
E_Q

輸出格式

請依序輸出各時刻看高橋直大像的俯角，共 QQ 行。 角度請以度數法（度）輸出，範圍為 00 到 9090 度。

當絕對誤差或相對誤差在 10−710^{-7} 以下時，將被視為正確。

範例測資

❌ Unsupported block (heading_4)

輸入：

4
2 1 1
4
0
1
2
3

輸出：

0.000000000000
24.094842552111
54.735610317245
45.000000000000

說明： 高橋直大像位於座標 (1,1,0)(1, 1, 0)。

在時刻 00，E869120 君位於座標 (0,0,0)(0, 0, 0)，從 E869120 君看高橋直大像的俯角為 00 度。

在時刻 33，E869120 君位於座標 (0,1,1)(0, 1, 1)，從 E869120 君看高橋直大像的俯角為 4545 度。

❌ Unsupported block (heading_4)

輸入：

5121
312000000 4123 3314
6
123
12
445
4114
42
1233

輸出：

4.322765775902
0.421184234768
15.640867693969
35.396039162484
1.475665637902
43.338582976959

019 - 取出兩個 / Pick Two（★6）

題目描述

給定一個長度為 2N2N 的正整數數列 A=(A1,A2,…,A2N)A = (A_1, A_2, \dots, A_{2N})。 考慮透過以下操作從數列 AA 中移除數字：

  • 設當前剩餘的數列為 (A1′,A2′,…,AM′)(A^{\prime}_1, A^{\prime}_2, \dots, A^{\prime}_M)。選擇一個滿足 1≤i<M1 \leq i < M 的整數 ii，並從數列中移除 Ai′A^{\prime}_i 與 Ai+1′A^{\prime}_{i+1}。在此操作後，剩餘的數列變為 (A1′,…,Ai−1′,Ai+2′,…,AM′)(A^{\prime}_1, \dots, A^{\prime}_{i-1}, A^{\prime}_{i+2}, \dots, A^{\prime}_M)。

進行此操作需要消耗成本。 若移除的數字為 Ai′,Ai+1′A^{\prime}_i, A^{\prime}_{i+1}，則單次操作所需的成本為 ∣Ai′−Ai+1′∣|A^{\prime}_i - A^{\prime}_{i+1}|。

重複進行此操作 NN 次以將數列 AA 中的所有數字全部移除，求這 NN 次操作的成本總和的最小可能值。

數據範圍

  • 1≤N≤2001 \leq N \leq 200
  • 1≤Ai≤106 (1≤i≤2N)1 \leq A_i \leq 10^6\ (1 \leq i \leq 2N)
  • 所有輸入皆為整數

輸入格式

N
A_1 A_2 … A_{2N}

輸出格式

請輸出進行 NN 次操作所需成本總和的最小可能值。

範例測資

❌ Unsupported block (heading_4)

輸入：

3
6 2 3 9 8 6

輸出：

2

說明： 成本總和最小的操作範例如下：

  • 選擇 i=2i = 2，花費 ∣2−3∣=1|2 - 3| = 1 的成本進行操作。數列變為 (6,9,8,6)(6, 9, 8, 6)。
  • 選擇 i=2i = 2，花費 ∣9−8∣=1|9 - 8| = 1 的成本進行操作。數列變為 (6,6)(6, 6)。
  • 選擇 i=1i = 1，花費 ∣6−6∣=0|6 - 6| = 0 的成本進行操作。數列變為 ()()。

這 33 次操作的成本總和為 22。

❌ Unsupported block (heading_4)

輸入：

3
1 3 5 5 3 1

輸出：

0

❌ Unsupported block (heading_4)

輸入：

4
1 2 4 8 16 32 64 128

輸出：

85

❌ Unsupported block (heading_4)

輸入：

15
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32

輸出：

207

020 - 對數不等式 / Log Inequality（★3）

題目描述

是否滿足 log⁡2a<blog⁡2c\log_2 a < b \log_2 c？

數據範圍

  • 1≤a≤9×10181 \leq a \leq 9 \times 10^{18}
  • 1≤b≤171 \leq b \leq 17
  • 1≤c≤131 \leq c \leq 13
  • 所有輸入皆為整數

輸入格式

a b c

輸出格式

若 log⁡2a<blog⁡2c\log_2 a < b \log_2 c 則輸出 Yes，否則輸出 No。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 3 2

輸出：

Yes

說明： 因為 log⁡24=2\log_2 4 = 2 且 3log⁡22=3×1=33 \log_2 2 = 3 \times 1 = 3，所以 log⁡24<3log⁡22\log_2 4 < 3 \log_2 2。

❌ Unsupported block (heading_4)

輸入：

16 3 2

輸出：

No

說明： 因為 log⁡216=4\log_2 16 = 4 且 3log⁡22=3×1=33 \log_2 2 = 3 \times 1 = 3，所以不滿足 log⁡216<3log⁡22\log_2 16 < 3 \log_2 2。

❌ Unsupported block (heading_4)

輸入：

8 3 2

輸出：

No

說明： 因為 log⁡28=3\log_2 8 = 3 且 3log⁡22=3×1=33 \log_2 2 = 3 \times 1 = 3，所以 log⁡28=3log⁡22\log_2 8 = 3 \log_2 2。 請注意兩邊的值相等時也要輸出 No。

021 - 平安歸來 / Come Back in One Piece（★5）

題目描述

有一個 NN 個頂點、MM 條邊的有向圖。邊被編號為 1,2,…,M1,2,\dots,M，第 ii 條邊從頂點 AiA_i 連向頂點 BiB_i。

請問滿足以下條件的頂點對 (x,y)(x, y)（1≤x<y≤N1 \leq x \lt y \leq N）共有多少組？

  • 頂點 xx 到頂點 yy 的路徑，以及頂點 yy 到頂點 xx 的路徑，兩者皆存在。

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • 1≤M≤2000001 \leq M \leq 200000
  • 1≤Ai,Bi≤N1 \leq A_i , B_i \leq N (1≤i≤M)(1 \leq i \leq M)
  • AieBiA_i e B_i (1≤i≤M)(1 \leq i \leq M)
  • 所有輸入皆為整數

輸入格式

N M
A_1 B_1
A_2 B_2
 dots
A_M B_M

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 7
1 2
2 1
2 3
4 3
4 1
1 4
2 3

輸出：

3

說明： 例如，(x,y)=(1,2)(x,y) = (1,2) 中，從頂點 11 到頂點 22 存在由邊 11 組成的路徑，從頂點 22 到頂點 11 存在由邊 22 組成的路徑，因此滿足條件。 除此之外，(x,y)=(1,4),(2,4)(x,y)=(1,4),(2,4) 也滿足條件；但 (x,y)=(2,3)(x,y)=(2,3) 由於不存在從頂點 33 到頂點 22 的路徑，因此不滿足條件。

另外請注意，如邊 33 與邊 77 所示，圖中可能包含重邊（多重邊）。

❌ Unsupported block (heading_4)

輸入：

100 1
1 2

輸出：

0

022 - 立方體蛋糕 / Cubic Cake（★2）

題目描述

有一個寬為 AA、深為 BB、高為 CC 的長方體形狀蛋糕。

你可以對蛋糕進行以下操作：

  • 沿著與某個面平行的方向進行切斷
  • 但是，不能移動蛋糕（當蛋糕被分割成多個部分時，不能將它們移動或分開單獨切割）

最少需要幾次操作，才能使所有蛋糕塊都變成正方體（立方體）？

數據範圍

  • 1≤A,B,C≤10181 \leq A, B, C \leq 10^{18}
  • 所有輸入皆為整數

輸入格式

A B C

輸出格式

請在一行中輸出最少的操作次數。

範例測資

❌ Unsupported block (heading_4)

輸入：

2 2 3

輸出：

4

說明： 切斷蛋糕 44 次後，可以得到 1212 個邊長為 11 的立方體。

❌ Unsupported block (heading_4)

輸入：

2 2 4

輸出：

1

說明： 切斷蛋糕 11 次後，可以得到 22 個邊長為 22 的立方體。

❌ Unsupported block (heading_4)

輸入：

1000000000000000000 999999999999999999 999999999999999998

輸出：

2999999999999999994

說明： 請注意整數溢位。

023 - 避免衝突 / Avoid War（★7）

題目描述

有一個高 HH 格、寬 WW 格的網格，從上數來第 ii 列、從左數來第 jj 行的格子記為 (i,j)(i,j)。 每個格子都有塗色，格子 (i,j)(i,j) 的顏色在 Ci,jC_{i,j} 為 # 時為黑色，在 Ci,jC_{i,j} 為 . 時為白色。

你可以選擇若干個白色格子（也可以一個都不選），在上面放置國王（King）棋子。 請問有多少種放置方法，使得國王之間互不互相攻擊（定義如下）？請輸出方法數除以 109+710^9+7 的餘數。

在此，兩種放置方法被視為不同，若且唯若： 「存在某個白色格子，在其中一種方法中放置了國王，而在另一種方法中沒有放置」。

「國王之間互不互相攻擊」是指： 對於任意兩個放置了國王的不同格子 (i,j)(i,j) 與 (k,l)(k,l)，均滿足 ∣i−k∣>1|i-k|>1 或 ∣j−l∣>1|j-l|>1。

數據範圍

  • 1≤H,W≤241 \leq H,W \leq 24
  • H,WH,W 為整數
  • Ci,jC_{i,j} 為 # 或 .
  • 至少存在一個白色格子

輸入格式

H W
C_{1,1}… C_{1,W}
dots
C_{H,1}… C_{H,W}

輸出格式

請輸出滿足條件的放置方法數除以 109+710^9+7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

1 3
...

輸出：

5

說明： 共有以下 55 種方式。（o 表示放置了國王的格子）

...     o..     .o.     ..o     o.o

這滿足子任務 1,2,3,41,2,3,4 的限制。

❌ Unsupported block (heading_4)

輸入：

3 3
.#.
#..
.##

輸出：

13

說明： 共有以下 1313 種方式。（o 表示放置了國王的格子）

.#.     o#.     .#o     .#.     .#.     .#.     o#o
#..     #..     #..     #o.     #.o     #..     #..
.##     .##     .##     .##     .##     o##     .##

o#.     o#.     .#o     .#.     o#o     o#.
#.o     #..     #..     #.o     #..     #.o
.##     o##     o##     o##     o##     o##

這滿足子任務 1,2,3,41,2,3,4 的限制。

❌ Unsupported block (heading_4)

輸入：

8 9
######.##
####..##.
..#...#..
###...###
#....##.#
.##......
#.####..#
#.#######

輸出：

273768

說明： 這滿足子任務 2,3,42,3,4 的限制。

❌ Unsupported block (heading_4)

輸入：

17 17
.####...#.....#.#
.#....#.#####...#
#...##.##...#..##
..#..####..#...##
.#..#..#.#.##...#
.#.#.#...#.##..#.
#...#..#..##..###
###.#..###..###..
...#.##.##.#....#
..####....#.#...#
.##...##.#.#...#.
..########...###.
#..##....#.......
##.##..###.#.##..
.##....#........#
....#####..##.#..
.###...##..##.#..

輸出：

314465173

說明： 請輸出除以 109+710^9+7 的餘數。

這滿足子任務 3,43,4 的限制。

❌ Unsupported block (heading_4)

輸入：

22 18
.##.##.#.#.#...##.
####.#..###.#.#..#
#####.##...##.###.
...#.#.#.##.##.###
..#.##.#.#....#...
#.###.##....###..#
....#####...#...#.
.#..##..#..###....
....#..##.#.#..#.#
###.#.....#..##.#.
#..#..#.#.##..###.
#...#....##..###..
..#...#..###..##..
.#....#.#.#..###.#
##.#.#..#..###..##
....###.##.##.##..
#...####.#.#..##..
..#.###.###.###.##
#...##.#.#.#...#.#
#..###..########..
#.##.#####.#..#.##
#..#........#...#.

輸出：

47296634

說明： 這滿足子任務 44 的限制。

024 - 加減一的選擇 / Select +／- One（★2）

題目描述

給定長度為 NN 的正整數數列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N) 及 B=(B1,B2,…,BN)B = (B_1, B_2, \ldots, B_N)。

請判斷是否能透過進行恰好 KK 次以下操作，使 AA 與 BB 完全一致。

操作：選擇一個滿足 1≤i≤N1 \leq i \leq N 的 ii，將 AiA_i 替換為 Ai−1A_i - 1 或 Ai+1A_i + 1。

數據範圍

  • 1≤N≤10001 \leq N \leq 1000
  • 1≤K≤1091 \leq K \leq 10^9
  • 1≤Ai,Bi≤106 (1≤i≤N)1 \leq A_i, B_i \leq 10^6 \ (1 \leq i \leq N)
  • 所有輸入皆為整數

輸入格式

N K
A_1 A_2 … A_N
B_1 B_2 … B_N

輸出格式

如果能透過恰好 KK 次操作使 AA 與 BB 一致，請輸出 Yes；否則輸出 No。

範例測資

❌ Unsupported block (heading_4)

輸入：

2 5
1 3
2 1

輸出：

Yes

說明： 例如，可以透過以下恰好 55 次操作使 AA 與 BB 一致：

  • 選擇 i=1i = 1，將 A1A_1 替換為 A1−1A_1 - 1。此時 AA 變為 (0,3)(0, 3)。
  • 選擇 i=2i = 2，將 A2A_2 替換為 A2−1A_2 - 1。此時 AA 變為 (0,2)(0, 2)。
  • 選擇 i=2i = 2，將 A2A_2 替換為 A2−1A_2 - 1。此時 AA 變為 (0,1)(0, 1)。
  • 選擇 i=1i = 1，將 A1A_1 替換為 A1+1A_1 + 1。此時 AA 變為 (1,1)(1, 1)。
  • 選擇 i=1i = 1，將 A1A_1 替換為 A1+1A_1 + 1。此時 AA 變為 (2,1)(2, 1)，與 BB 一致。

❌ Unsupported block (heading_4)

輸入：

3 1
7 8 9
7 8 9

輸出：

No

說明： 進行恰好 11 次操作後，AA 會變成以下其中之一：

  • (6,8,9)(6, 8, 9)
  • (8,8,9)(8, 8, 9)
  • (7,7,9)(7, 7, 9)
  • (7,9,9)(7, 9, 9)
  • (7,8,8)(7, 8, 8)
  • (7,8,10)(7, 8, 10)

這些都與 BB 不一致，因此請輸出 No。

❌ Unsupported block (heading_4)

輸入：

7 999999999
3 1 4 1 5 9 2
1 2 3 4 5 6 7

輸出：

Yes

025 - 數位乘積方程式 / Digit Product Equation（★7）

題目描述

函數 f(x)f(x) 定義如下：

  • f(x)=(xext的各個數位數字之乘積)f(x) = (x ext{ 的各個數位數字之乘積})

例如 f(777)=343f(777)=343、f(8691)=432f(8691)=432、f(869120)=0f(869120)=0。

給定整數 NN 與 BB，求在 11 以上 NN 以下的整數 mm 中，滿足 m−f(m)=Bm-f(m) = B 的整數個數。

數據範圍

  • 1≤N<10111 \leq N \lt 10^{11}
  • 1≤B<10111 \leq B \lt 10^{11}
  • 所有輸入皆為整數

輸入格式

N B

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

999 434

輸出：

2

說明：m=574m=574 與 m=777m=777 這 22 個數滿足條件。

❌ Unsupported block (heading_4)

輸入：

255 15

輸出：

2

❌ Unsupported block (heading_4)

輸入：

9999999999 1

輸出：

0

026 - 樹上的獨立集 / Independent Set on a Tree（★4）

題目描述

給定一棵 NN 個頂點的樹。頂點編號為 11 到 NN，第 ii 條邊 (1≤i≤N−1)(1 \leq i \leq N-1) 連接頂點 AiA_i 與 BiB_i。

請從這棵樹中選出 $rac{N}{2}$ 個不重複的頂點，使得選出的任意兩個頂點均不相鄰。

數據範圍

  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • NN 為偶數
  • 所有輸入皆為整數
  • 給定的數據是一棵樹

輸入格式

N
A_1 B_1
A_2 B_2
dots
A_{N-1} B_{N-1}

輸出格式

請在一行中以空格分隔，輸出 $rac{N}{2}$ 個不重複的頂點編號。

範例測資

❌ Unsupported block (heading_4)

輸入：

4
1 2
2 3
2 4

輸出：

3 4

❌ Unsupported block (heading_4)

輸入：

6
1 3
2 4
3 5
2 5
3 6

輸出：

1 2 6

027 - 註冊申請 / Sign Up Requests （★2）

題目描述

低橋君建立了一個程式競賽網站「LowCoder」並開始營運服務。 截至今天為止，LowCoder 上沒有任何使用者。

從今天起算第 ii 天（1≤i≤N1 \leq i \leq N），會有一位希望使用使用者名稱 SiS_i 的使用者提出註冊申請。

在提出申請的當下，如果已經存在使用者名稱為 SiS_i 的使用者，則該註冊申請將被忽略。 如果不存在這樣的使用者，則該註冊申請會被受理，該使用者將被成功註冊到 LowCoder 中。

請計算出哪些天數（第幾天）送出的註冊申請會被受理。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • SiS_i（1≤i≤N1 \leq i \leq N）為由英文字母小寫及數字組成的長度介於 11 到 1515 之間的字串。 更精確地說，SiS_i 是可用正規表達式 [a-z0-9]{1,15} 表示的字串。

輸入格式

N
S_1
S_2
dots
S_N

輸出格式

請將從今天起算第幾天送出的註冊申請會被受理，依升冪（由小到大）順序輸出。

範例測資

❌ Unsupported block (heading_4)

輸入：

5
e869120
atcoder
e869120
square1001
square1001

輸出：

1
2
4

說明： 第 11 天申請了使用者名稱 e869120，由於此時沒有該名稱的使用者，因此成功註冊至 LowCoder。 第 22 天申請了使用者名稱 atcoder，由於此時沒有該名稱的使用者，因此成功註冊至 LowCoder。 第 33 天申請了使用者名稱 e869120，但由於該使用者名稱已經被註冊過，因此不予受理。 第 44 天申請了使用者名稱 square1001，由於此時沒有該名稱的使用者，因此成功註冊至 LowCoder。 第 55 天申請了使用者名稱 square1001，但由於該使用者名稱已經被註冊過，因此不予受理。

❌ Unsupported block (heading_4)

輸入：

4
taro
hanako
yuka
takashi

輸出：

1
2
3
4

說明： 也可能存在沒有任何註冊申請被拒絕的情況（所有申請均被受理）。

❌ Unsupported block (heading_4)

輸入：

10
square869120
square869120
square869120
square869120
square869120
square869120
square869120
square869120
square869120
square869120

輸出：

1

說明：SiS_i 有可能全部相同。

028 - 雜亂的紙張 / Cluttered Paper（★4）

題目描述

二維平面上有 NN 張長方形的紙。所有紙張的邊都與 xx 軸或 yy 軸平行放置，第 ii 張紙的左下角座標為 (lxi,lyi)(lx_i, ly_i)，右上角座標為 (rxi,ryi)(rx_i, ry_i)。 對於 k=1,2,3,…,Nk=1,2,3, \dots, N，請分別求出以下數值：

  • 恰好被 kk 張紙重疊覆蓋的區域面積

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 0≤lxi<rxi≤10000 \leq lx_i \lt rx_i \leq 1000
  • 0≤lyi<ryi≤10000 \leq ly_i \lt ry_i \leq 1000
  • 所有輸入皆為整數

輸入格式

N
lx_1 ly_1 rx_1 ry_1
lx_2 ly_2 rx_2 ry_2
dots
lx_N ly_N rx_N ry_N

輸出格式

令恰好被 kk 張紙重疊覆蓋的區域面積為 AkA_k，請依以下格式輸出：

A_1
A_2
dots
A_N

範例測資

❌ Unsupported block (heading_4)

輸入：

2
1 1 3 2
2 1 4 2

輸出：

2
1

說明： 恰好被 11 張紙覆蓋的區域面積為 22，恰好被 22 張紙覆蓋的區域面積為 11。

❌ Unsupported block (heading_4)

輸入：

2
1 1 3 4
3 4 6 5

輸出：

9
0

說明： 紙張之間可能完全不重疊。

❌ Unsupported block (heading_4)

輸入：

20
61 98 76 100
70 99 95 100
10 64 96 91
12 37 99 66
63 93 65 95
16 18 18 67
30 47 88 56
33 6 38 8
37 19 40 68
4 56 12 84
3 16 92 78
39 24 67 96
46 1 69 57
40 34 65 65
20 38 51 92
5 32 100 73
7 33 92 55
4 46 97 85
43 18 57 87
15 29 54 74

輸出：

1806
990
1013
1221
567
839
413
305
228
121
58
40
0
0
0
0
0
0
0
0

029 - 長磚塊 / Long Bricks（★5）

題目描述

有一個由 WW 個正方形格子左右排列而成的水平地面。最初，所有格子的地面高度均為 00。現在依序堆疊 NN 個高度為 11 的長方體磚塊。當磚塊接觸到高度為 hh 的表面時，該磚塊頂部的高度會變為 h+1h+1。

第 ii 個堆疊的磚塊放置在恰好覆蓋從左數來第 LiL_i 個到第 RiR_i 個格子的範圍。此時，磚塊會與覆蓋範圍內最高的水平面接觸。

請計算每個磚塊堆疊後，其頂部的高度。

數據範圍

  • 2≤W≤5imes1052 \leq W \leq 5 imes 10^5
  • 1≤N≤2.5imes1051 \leq N \leq 2.5 imes 10^5
  • 1≤Li≤Ri≤W1 \leq L_i \leq R_i \leq W (1≤i≤N)(1 \leq i \leq N)
  • 所有輸入皆為整數

輸入格式

W N
L_1 R_1
L_2 R_2
dots
L_N R_N

輸出格式

請在第 ii 行（1≤i≤N1 \leq i \leq N）以整數輸出第 ii 個堆疊磚塊頂部的高度。

範例測資

❌ Unsupported block (heading_4)

輸入：

100 4
27 100
8 39
83 97
24 75

輸出：

1
2
2
3

說明： 我們將第 ii 個堆疊的磚塊稱為磚塊 ii。 磚塊 11 接觸地面，因此頂部高度為 11。 磚塊 22 接觸磚塊 11 的頂部，因此頂部高度為 22。 磚塊 33 接觸磚塊 11 的頂部，因此頂部高度為 22。 磚塊 44 接觸磚塊 22 的頂部，因此頂部高度為 33。

❌ Unsupported block (heading_4)

輸入：

3 5
1 2
2 2
2 3
3 3
1 2

輸出：

1
2
3
4
4

說明： 我們將第 ii 個堆疊的磚塊稱為磚塊 ii。 磚塊 11 接觸地面，因此頂部高度為 11。 磚塊 22 接觸磚塊 11 的頂部，因此頂部高度為 22。 磚塊 33 接觸磚塊 22 的頂部，因此頂部高度為 33。 磚塊 44 接觸磚塊 33 的頂部，因此頂部高度為 44。 磚塊 55 接觸磚塊 33 的頂部，因此頂部高度為 44。

❌ Unsupported block (heading_4)

輸入：

10 10
1 3
3 5
5 7
7 9
2 4
4 6
6 8
3 5
5 7
4 6

輸出：

1
2
3
4
3
4
5
5
6
7

❌ Unsupported block (heading_4)

輸入：

500000 7
1 500000
500000 500000
1 500000
1 1
1 500000
500000 500000
1 500000

輸出：

1
2
3
4
5
6
7

說明： ※ 此範例測資僅滿足子任務 2,32, 3 的限制。

030 - K 個質因數 / K Factors（★5）

題目描述

請計算在 22 以上 NN 以下的整數中，擁有 KK 種以上相異質因數的整數個數。

數據範圍

  • 2≤N≤1072 \leq N \leq 10^7
  • 1≤K≤81 \leq K \leq 8
  • 所有輸入皆為整數

輸入格式

N K

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

15 2

輸出：

5

說明： 例如，4=224=2^2 只有 11 種質因數，因此不滿足條件； 而 6=2imes36=2 imes 3 有 22 種質因數，因此滿足條件。

滿足條件的數共有 6,10,12,14,156,10,12,14,15 這 55 個。

❌ Unsupported block (heading_4)

輸入：

30 2

輸出：

13

說明： 滿足條件的數共有 6,10,12,14,15,18,20,21,22,24,26,28,306,10,12,14,15,18,20,21,22,24,26,28,30 這 1313 個。

❌ Unsupported block (heading_4)

輸入：

200 4

輸出：

0

❌ Unsupported block (heading_4)

輸入：

869120 1

輸出：

869119

❌ Unsupported block (heading_4)

輸入：

10000000 3

輸出：

6798027

031 - 對決 AtCoder / VS AtCoder（★6）

題目描述

你以「競技程式設計師隊」成員的身份參加了人氣節目「VS AtCoder」。

該節目的最終遊戲「拿石頭遊戲」的規則如下：

規則 1　有 NN 堆石頭橫向排成一列。從左數來第 ii 堆石頭中，有 WiW_i 顆白石和 BiB_i 顆青石。

規則 2　由先攻開始輪流執行以下操作：

  • 選擇一堆白石數量為 11 顆以上或青石數量為 22 顆以上的石頭堆，並執行以下操作中的其中一種。設所選石頭堆中現有的白石與青石數量分別為 w,bw, b：

規則 3　最先無法進行操作的人判為輸（失敗）。也就是說，輪到自己回合時，首次出現「對所有石頭堆而言，皆滿足白石為 00 顆且青石為 11 顆以下」這種情況的人輸掉遊戲。

你將與該節目的固定班底 E869120 進行一對一直接對決。作為嘉賓特權，你可以自由選擇先攻或後攻。由於這場遊戲的勝負直接決定了整個比賽的勝負，因此你必須在這場遊戲中贏得勝利。

在雙方均採取最佳策略的情況下，為了獲勝，你應該選擇先攻還是後攻？

關於 ⌊x⌋\lfloor x \rfloor⌊x⌋\lfloor x \rfloor 表示不超過 xx 的最大整數。 例如，⌊2.5⌋=2\lfloor 2.5 \rfloor = 2、⌊3⌋=3\lfloor 3 \rfloor = 3、⌊9.999999⌋=9\lfloor 9.999999 \rfloor = 9。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 0≤Wi,Bi≤500 \leq W_i, B_i \leq 50
  • (Wi,Bi)≠(0,0)(W_i, B_i) \neq (0,0)
  • 輸入的所有數值皆為整數

輸入格式

N
W_1 W_2 … W_N
B_1 B_2 … B_N

輸出格式

若你應該選擇先攻，請輸出 First；若應該選擇後攻，請輸出 Second。

範例測資

❌ Unsupported block (heading_4)

輸入：

1
0
2

輸出：

First

說明： 若你選擇先攻，在最初的操作中可以從唯一的石頭堆中移除 11 顆青石。 進行此操作後，該石頭堆的狀態變為「僅剩 11 顆青石」，此時 E869120 無法進行操作而落敗，你獲得勝利。 因此，你應該選擇先攻。

❌ Unsupported block (heading_4)

輸入：

2
10 10
10 10

輸出：

Second

說明： 若你選擇後攻，在每次輪到自己操作時，只要對另一堆石頭執行與 E869120 剛剛相同的操作，你就能獲勝。因此，你應該選擇後攻。

❌ Unsupported block (heading_4)

輸入：

1
1
1

輸出：

Second

說明： 你應該選擇後攻。因為遊戲只能按照以下流程進行：

  • E869120 最初只能加入 11 顆青石並移除 11 顆白石。
  • 石頭堆的狀態變為「僅剩 22 顆青石」。此時你只能進行移除 11 顆青石的操作。
  • 接著，石頭堆的狀態變為「僅剩 11 顆青石」，輪到 E869120 時無法進行操作。

❌ Unsupported block (heading_4)

輸入：

6
3 1 4 1 5 9
2 7 1 8 2 8

輸出：

Second

❌ Unsupported block (heading_4)

輸入：

6
1 2 3 4 5 6
1 2 3 4 5 6

輸出：

First

032 - AtCoder 接力賽 / AtCoder Ekiden（★3）

題目描述

ABC 田徑隊有 NN 名驛站接力賽選手。在接力賽中，每位選手負責跑 11 個區間（棒次）。不能有多名選手負責同一個區間，也不能有一名選手負責多個區間。接力賽路線共有第 11 區到第 NN 區，選手 ii 跑第 jj 區所需的時間為 Ai,jA_{i, j}。

接力賽將依第 11 區、第 22 區、……、第 NN 區的順序，由負責該區間的選手依序奔跑。跑完第 jj 區（1≤j≤N−11 \leq j \leq N - 1）的選手必須將接力帶（タスキ）傳遞給跑第 j+1j + 1 區的選手。此時交接接力帶所花費的時間極短，可忽略不計。最後接到接力帶的選手跑完第 NN 區即為抵達終點。

ABC 田徑隊中流傳著 MM 個傳聞，第 ii 個傳聞為「選手 XiX_i 與選手 YiY_i 關係不好」。被傳聞關係不好的兩位選手之間無法進行接力帶的交接。也就是說，選手 XiX_i 的下一棒不能是選手 YiY_i，選手 YiY_i 的下一棒也不能是選手 XiX_i。

請計算 ABC 田徑隊完成接力賽抵達終點所需時間的最小值。如果無論如何安排各選手負責的區間都無法順利完賽，請改為輸出 -1。

數據範圍

  • 1≤N≤101 \leq N \leq 10
  • 1≤Ai,j≤1000 (1≤i≤N,1≤j≤N)1 \leq A_{i, j} \leq 1000 \ (1 \leq i \leq N, 1 \leq j \leq N)
  • 0≤M≤N(N−1)/20 \leq M \leq N(N - 1)/2
  • 1≤Xi<Yi≤N (1≤i≤M)1 \leq X_i < Y_i \leq N \ (1 \leq i \leq M)
  • (Xi,Yi)≠(Xj,Yj) (i≠j)(X_i, Y_i) \neq (X_j, Y_j) \ (i \neq j)
  • 輸入的所有數值皆為整數

輸入格式

N
A_{1, 1} A_{1, 2} … A_{1, N}
A_{2, 1} A_{2, 2} … A_{2, N}
⋮
A_{N, 1} A_{N, 2} … A_{N, N}
M
X_1 Y_1
X_2 Y_2
⋮
X_M Y_M

輸出格式

輸出抵達終點所需時間的最小值。如果無論如何安排選手負責的區間都無法抵達終點，請輸出 -1。

範例測資

❌ Unsupported block (heading_4)

輸入：

3
1 10 100
10 1 100
100 10 1
1
1 2

輸出：

111

說明： 讓選手 11 跑第 11 區、選手 33 跑第 22 區、選手 22 跑第 33 區，總耗時為 1+10+100=1111 + 10 + 100 = 111，即可達成最小值 111111。

❌ Unsupported block (heading_4)

輸入：

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

輸出：

-1

❌ Unsupported block (heading_4)

輸入：

3
1 10 100
10 1 100
100 10 1
0

輸出：

3

033 - 不要太亮 / Not Too Bright（★2）

題目描述

E869120 打算製作一個在冬季展示的燈光造景。 E869120 所規劃的燈光造景由縱向 H×H \times 橫向 WW 共 HWHW 顆 LED 燈組成。 燈光造景上的每顆 LED 燈都可以自由切換為點亮或熄滅的狀態。

當該燈光造景滿足以下條件時，稱為不恰當的：

  • 存在一個完全包含在整個燈光造景內部、大小為縱向 2×2 \times 橫向 22（包含 44 顆 LED 燈）的區域，該區域內點亮的 LED 燈數量達到 22 顆以上。

在所有恰當（即非不恰當狀態）的燈光點亮配置中，求點亮的 LED 燈數量的最大可能值。

數據範圍

  • 1≤H,W≤1001 \leq H, W \leq 100
  • 輸入的所有數值皆為整數

輸入格式

H W

輸出格式

輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

2 3

輸出：

2

說明： 若以 '#' 表示點亮的 LED，'.' 表示熄滅的 LED，例如以下狀態為符合條件且點亮 LED 數量最多的一種配置：

#.#
...

另一方面，以下狀態是不恰當的，因此不滿足條件： 在由上數來第 1∼21 \sim 2 列、由左數來第 1∼21 \sim 2 行組成的區域中，存在 22 顆點亮的 LED。

#.#
.#.

❌ Unsupported block (heading_4)

輸入：

3 4

輸出：

4

說明： 例如以下狀態為符合條件且點亮 LED 數量最多的一種配置：

#..#
....
#..#

❌ Unsupported block (heading_4)

輸入：

3 6

輸出：

6

034 - 元素種類受限 / There are few types of elements（★4）

題目描述

給定一個長度為 NN 的數列 a=(a1,a2,…,aN)a = (a_1, a_2, \ldots, a_N) 與一個整數 KK。 請在滿足以下條件的所有連續子數列中，求出最長子數列的長度：

  • 該子數列所包含的元素的值最多只有 KK 種。

數據範圍

  • 1≤K≤N≤100,0001 \leq K \leq N \leq 100{,}000
  • 1≤ai≤1091 \leq a_i \leq 10^{9} (1≤i≤N1 \leq i \leq N)
  • 輸入的所有數值皆為整數

輸入格式

N K
a_1 a_2 … a_N

輸出格式

輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

5 1
1 2 3 4 5

輸出：

1

說明：K=1K = 1，且數列中的元素值全部互不相同，因此答案為 11。

❌ Unsupported block (heading_4)

輸入：

5 4
1 1 2 4 2

輸出：

5

說明：K=4K = 4，而數列中的元素值只有 33 種，因此包含所有元素的區間皆滿足條件，答案為 55。

❌ Unsupported block (heading_4)

輸入：

10 2
1 2 3 4 4 3 2 1 2 3

輸出：

4

說明： 在滿足條件的區間中，長度最大的是區間 [3,6][3, 6]。

035 - 保持連通性 / Preserve Connectivity（★7）

題目描述

給定一棵具有 NN 個頂點的樹，頂點編號為 1,2,⋯ ,N1, 2, \cdots, N。第 ii 條邊（1≤i≤N−11 \leq i \leq N-1）連接頂點 AiA_i 與 BiB_i。

給定 QQ 個以下形式的詢問，請依 j=1,2,⋯ ,Qj = 1, 2, \cdots, Q 的順序進行回答：

  • 從 N−1N-1 條邊中選擇若干條邊保留。
  • 刪除未被選中的邊之後，使得頂點 Vj,1,Vj,2,⋯ ,Vj,KjV_{j,1}, V_{j,2}, \cdots, V_{j,K_j} 全部彼此相互連通。
  • 最少需要選擇保留多少條邊？

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • 1≤Ai<Bi≤N1 \leq A_i \lt B_i \leq N
  • 1≤Q≤1000001 \leq Q \leq 100000
  • 2≤Kj≤N2 \leq K_j \leq N
  • 1≤Vj,1<Vj,2<⋯<Vj,Kj≤N1 \leq V_{j,1} \lt V_{j,2} \lt \cdots \lt V_{j,K_j} \leq N
  • K1+K2+⋯+KQ≤200000K_1 + K_2 + \cdots + K_Q \leq 200000
  • 給定的圖為一棵樹
  • 輸入的所有數值皆為整數

輸入格式

N
A_1 B_1
A_2 B_2
⋮
A_{N-1} B_{N-1}
Q
K_1 V_{1,1} V_{1,2} ... V_{1,K_1}
K_2 V_{2,1} V_{2,2} ... V_{2,K_2}
⋮
K_Q V_{Q,1} V_{Q,2} ... V_{Q,K_Q}

輸出格式

對於 j=1,2,…,Qj=1, 2, \dots, Q，請在第 jj 行輸出對應第 jj 個詢問的答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

6
1 2
2 3
3 4
1 5
3 6
5
2 1 2
3 1 3 5
4 2 3 4 5
5 1 2 3 5 6
6 1 2 3 4 5 6

輸出：

1
3
4
4
5

說明： 在第 11 個詢問中，頂點 11 與頂點 22 由第 11 條邊相鄰連接，因此只需選擇該邊即可。 其餘詢問亦可同理得出答案。

此外，本組測資滿足子任務 1、4 的限制條件。

❌ Unsupported block (heading_4)

輸入：

6
1 2
2 3
3 4
1 5
3 6
5
2 1 2
2 3 4
2 4 6
2 1 5
2 2 5

輸出：

1
1
2
1
2

說明： 本組測資滿足子任務 1、2、4 的限制條件。

❌ Unsupported block (heading_4)

輸入：

6
1 2
2 3
3 4
1 5
3 6
5
3 1 2 3
3 1 2 5
3 1 3 6
3 3 4 5
3 4 5 6

輸出：

2
2
3
4
5

說明： 本組測資滿足子任務 1、3、4 的限制條件。

036 - 最大曼哈頓距離 / Max Manhattan Distance（★5）

題目描述

在二維坐標平面上有 NN 個互不相同的點 P1,P2,…,PNP_1, P_2, \ldots, P_N，點 PiP_i 的坐標為 (xi,yi)(x_i, y_i)。

請依序處理以下 QQ 個詢問：

  • 第 ii 個詢問（1≤i≤Q1 \leq i \leq Q）中給定一個整數 qiq_i，請輸出點 PqiP_{q_i} 與這 NN 個點之間曼哈頓距離的最大值。
  • 也就是說，若將點 PsP_s 與點 PtP_t 的曼哈頓距離記為 dist\rm{dist}(Ps,Pt)(P_s, P_t)，請輸出 max\rm{max}((dist\rm{dist}$(P_{q_i}, P_1), , (P_{q_i}, P_N))$ 的值。

關於曼哈頓距離 坐標 (x1,y1)(x_1, y_1) 與坐標 (x2,y2)(x_2, y_2) 之間的曼哈頓距離定義為 ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|。

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • 1≤Q≤N1 \leq Q \leq N
  • −109≤xi,yi≤109-10^9 \leq x_i, y_i \leq 10^9
  • (xi,yi)≠(xj,yj)(x_i, y_i) \neq (x_j, y_j) (1≤i<j≤N)(1 \leq i < j \leq N)
  • 1≤qi≤N1 \leq q_i \leq N (1≤i≤Q)(1 \leq i \leq Q)
  • qi≠qjq_i \neq q_j (1≤i<j≤Q)(1 \leq i < j \leq Q)
  • 輸入的所有數值皆為整數

輸入格式

N Q
x_1 y_1
⋮
x_N y_N
q_1
⋮
q_Q

輸出格式

將給定的 QQ 個詢問的答案以換行分隔，依序輸出於每行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 3
-1 2
1 1
-2 -3
1
2
3

輸出：

6
7
7

說明： 第 11 個詢問中關注點 11：

  • 點 11 與點 11 的曼哈頓距離為 ∣−1−(−1)∣+∣2−2∣=0|-1 - (-1)| + |2 - 2| = 0
  • 點 11 與點 22 的曼哈頓距離為 ∣−1−1∣+∣2−1∣=3|-1 - 1| + |2 - 1| = 3
  • 點 11 與點 33 的曼哈頓距離為 ∣−1−(−2)∣+∣2−(−3)∣=6|-1 - (-2)| + |2 - (-3)| = 6

因此，第 11 個詢問輸出這些曼哈頓距離的最大值 66。

❌ Unsupported block (heading_4)

輸入：

5 3
-2 -2
-1 -1
0 0
1 1
2 2
5
3
1

輸出：

8
4
8

❌ Unsupported block (heading_4)

輸入：

2 1
-1000000000 -1000000000
1000000000 1000000000
1

輸出：

4000000000

說明： 請注意數值溢位（Overflow）。

037 - 不留香料 / Don’t Leave the Spice（★5）

題目描述

有 NN 種需要使用香料的料理，編號為 11 到 NN。

料理 ii（1≤i≤N1 \le i \le N）的價值為 ViV_i，製作時會消耗香料。消耗香料的量可以在 LiL_i [mg][\mathrm{mg}] 以上、RiR_i [mg][\mathrm{mg}] 以下的範圍內自由調節。

請判斷是否能達成以下目標；若可以達成，請輸出製作料理的價值總和之最大可能值：

  • 從 NN 種料理中挑選若干種並各製作 1 份，使得消耗的香料總量恰好為 WW [mg][\mathrm{mg}]。
  • 但是，無法透過上述以外的途徑消耗香料。

數據範圍

  • 1≤W≤1041 \leq W \leq 10^4
  • 1≤N≤5001 \leq N \leq 500
  • 1≤Li≤Ri≤W1 \leq L_i \leq R_i \leq W (1≤i≤N)(1 \leq i \leq N)
  • 1≤Vi≤1091 \leq V_i \leq 10^9 (1≤i≤N)(1 \leq i \leq N)
  • 輸入的所有數值皆為整數

輸入格式

W N
L_1 R_1 V_1
L_2 R_2 V_2
⋮
L_N R_N V_N

輸出格式

輸出所製作料理的價值總和之最大可能值。

若無法恰好消耗 WW [mg][\mathrm{mg}] 的香料，請輸出 -1。

範例測資

❌ Unsupported block (heading_4)

輸入：

100 4
30 40 120
30 40 30
30 40 1500
30 40 40

輸出：

1660

說明： 若製作料理 11、料理 33、料理 44，各消耗 1003\frac{100}{3} [mg][\mathrm{mg}] 的香料，則價值總和為 120+1500+40=1660120+1500+40=1660。

❌ Unsupported block (heading_4)

輸入：

100 4
13 15 31415
12 13 92653
29 33 58979
95 98 32384

輸出：

-1

說明： 無法恰好消耗 100100 [mg][\mathrm{mg}] 的香料。

❌ Unsupported block (heading_4)

輸入：

5000 5
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000

輸出：

5000000000

❌ Unsupported block (heading_4)

輸入：

10000 20
4539 6002 485976
1819 5162 457795
1854 2246 487643
1023 4733 393530
1052 6274 289577
1874 2436 167747
1457 4248 452660
2103 4189 174955
3057 5061 319316
4898 4953 394627
1313 2880 154687
1274 1364 259598
3866 5844 233027
1163 5036 386223
1234 4630 155972
2845 4978 442858
3168 5368 171601
3708 4407 394899
3924 4122 428313
2112 4169 441976

輸出：

2727026

038 - 龐大的最小公倍數 / Large LCM（★3）

題目描述

給定正整數 A,BA, B。請計算 AA 與 BB 的最小公倍數（LCM）。但是，若答案超過 101810^{18}，請改為輸出 Large。

數據範圍

  • 1≤A,B≤10181 \leq A, B \leq 10^{18}
  • 輸入的所有數值皆為整數

輸入格式

A B

輸出格式

輸出 AA 與 BB 的最小公倍數。若答案超過 101810^{18}，請改為輸出 Large。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 6

輸出：

12

說明：44 與 66 的最小公倍數為 1212。 由於答案未超過 101810^{18}，請輸出 1212。

❌ Unsupported block (heading_4)

輸入：

1000000000000000000 3

輸出：

Large

說明：101810^{18} 與 33 的最小公倍數為 3×10183 \times 10^{18}。 由於答案超過 101810^{18}，請輸出 Large。

❌ Unsupported block (heading_4)

輸入：

1000000000000000000 1

輸出：

1000000000000000000

說明： 請注意，若答案恰好為 101810^{18}，請直接輸出該數值。

039 - 樹上距離總和 / Tree Distance（★5）

題目描述

給定一棵具有 NN 個頂點的樹。樹上的頂點分別編號為 11 到 NN。 第 ii 條邊雙向連接頂點 aia_i 與頂點 bib_i，邊長皆為 11。

請計算以下式子的值：

  • ∑u=1N−1∑v=u+1Ndist⁡(u,v){\displaystyle\sum_{u = 1}^{N - 1} \sum_{v = u + 1}^{N} \operatorname{dist}(u, v)}

其中，dist⁡(u,v)\operatorname{dist}(u,v) 表示從頂點 uu 到頂點 vv 的最短距離。

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 給定的圖為一棵樹
  • 輸入的所有數值皆為整數

輸入格式

N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}

輸出格式

請將答案輸出於一行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

2
1 2

輸出：

1

說明：dist⁡(1,2)=1\operatorname{dist}(1, 2) = 1，因此答案為 11。

❌ Unsupported block (heading_4)

輸入：

4
1 2
1 3
1 4

輸出：

9

說明： - dist⁡(1,2)=1\operatorname{dist}(1, 2) = 1 - dist⁡(1,3)=1\operatorname{dist}(1, 3) = 1 - dist⁡(1,4)=1\operatorname{dist}(1, 4) = 1 - dist⁡(2,3)=2\operatorname{dist}(2, 3) = 2 - dist⁡(2,4)=2\operatorname{dist}(2, 4) = 2 - dist⁡(3,4)=2\operatorname{dist}(3, 4) = 2

將以上距離相加得到 99，即為答案。

❌ Unsupported block (heading_4)

輸入：

12
1 2
3 1
4 2
2 5
3 6
3 7
8 4
4 9
10 5
11 7
7 12

輸出：

211

040 - 獲取更多金錢 / Get More Money（★7）

題目描述

在 AtCoder 共和國中有 NN 間房屋，編號為 11 到 NN。

一開始，房屋 ii 內放有現金 AiA_i 圓以及 kik_i 把鑰匙（分別為房屋 ci,1,ci,2,…,ci,kic_{i,1}, c_{i,2}, \dots, c_{i,k_i} 的鑰匙），進入房屋即可回收這些物品。 保證對任意的 jj（1≤j≤ki1 \leq j \leq k_i）皆滿足 ci,j>ic_{i,j} \gt i。

此外，要進入房屋 ii，必須完成以下兩件事：

  • 若 AtCoder 共和國中存在房屋 ii 的鑰匙，必須處於已將它們全部回收的狀態
  • 支付費用 WW 圓

你打算透過收集 AtCoder 共和國各房屋內的現金，來賺取盡可能多的金額。若妥善安排進入房屋的順序與選擇，請計算最多能淨賺多少圓。 也就是說，設進入房屋回收的現金總額為 II 圓，為了進入房屋所支付的費用總額為 OO 圓，請計算 I−OI-O 的最大值。 假設若有需要支付進入房屋的費用，隨時皆有足夠的資金可以支付。

數據範圍

  • 2≤N≤1002 \leq N \leq 100
  • 0≤W≤1070 \leq W \leq 10^7
  • 0≤Ai≤1070 \leq A_i \leq 10^7
  • 0≤ki≤N−i0 \leq k_i \leq N-i
  • i<ci,j≤Ni \lt c_{i,j} \leq N
  • ci,j≠ci,kc_{i,j} \neq c_{i,k} (j≠k)(j \neq k)
  • 輸入的所有數值皆為整數

輸入格式

N W
A_1 A_2 … A_N
k_1 c_{1,1} c_{1,2} … c_{1,k_1}
k_2 c_{2,1} c_{2,2} … c_{2,k_2}
⋮
k_N c_{N,1} c_{N,2} … c_{N,k_N}

輸出格式

請將最終獲得的金額（淨利）之最大值輸出於一行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

5 5
5 2 10 3 6
1 3
1 3
0
1 5
0

輸出：

2

說明： 依序進入房屋 1,2,31, 2, 3 為最優策略，可獲得 5+2+10−3×5=25+2+10-3\times 5=2 圓。

❌ Unsupported block (heading_4)

輸入：

6 10
8 6 9 1 2 0
1 3
2 3 4
1 5
1 5
1 6
0

輸出：

0

說明： 有時不進入任何房屋為最優選擇。

041 - AtCoder 農場的木樁 / Piles in AtCoder Farm（★7）

題目描述

AtCoder 農場中有 NN 根木樁，第 ii 根木樁釘在座標 (Xi,Yi)(X_i, Y_i) 的位置。

你想建造一道圍牆將所有的木樁包圍起來，並在圍牆邊界（周上）以及圍牆內部的所有整數座標點（格子點）上都釘上木樁。

由於建造太長的圍牆很累，因此你想在所有能包圍全部現有木樁的圍牆中，建造周長最短的一道圍牆。

請計算你新需要釘下的木樁數量。

保證木樁的粗細與圍牆的厚度均可忽略不計。

數據範圍

  • 3≤N≤1053 \leq N \leq 10^5
  • 0≤Xi,Yi≤109 (1≤i≤N)0 \leq X_i, Y_i \leq 10^9\ (1\leq i\leq N)
  • 若 i≠ji\neq j，則 (Xi,Yi)≠(Xj,Yj)(X_i, Y_i)\neq(X_j, Y_j)
  • 所有輸入皆為整數

輸入格式

N
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N

輸出格式

輸出你需要新釘下的木樁數量。

範例測資

❌ Unsupported block (heading_4)

輸入：

3
1 4
6 1
5 8

輸出：

17

說明： 你所建造的圍牆形狀為包圍這 3 個點的凸多邊形。 此時圍牆的周長為 92+34=18.5588…9\sqrt{2}+\sqrt{34}=18.5588\ldots，不存在周長更短且能包圍所有木樁的圍牆。 需要新釘上木樁的點為 (2,4),(2,5),(3,3),(3,4),(3,5),(3,6),(4,3),(4,4),(4,5),(4,6),(4,7),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7)(2,4),(2,5),(3,3),(3,4),(3,5),(3,6),(4,3),(4,4),(4,5),(4,6),(4,7),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7)，共 1717 根木樁，因此答案為 1717。

❌ Unsupported block (heading_4)

輸入：

3
2 2
2 3
3 2

輸出：

0

說明： 也有可能不需要釘下任何新的木樁。

❌ Unsupported block (heading_4)

輸入：

3
2 39
39 35
17 5

輸出：

599

說明： 新需要釘下 599599 根木樁。

❌ Unsupported block (heading_4)

輸入：

10
72 7
54 25
97 48
37 47
34 54
4 16
62 1
59 22
99 73
34 75

輸出：

4828

說明： 新需要釘下 48284828 根木樁。

❌ Unsupported block (heading_4)

輸入：

30
878317816 654163251
686185971 65193664
421988001 893301255
337790787 848308131
116633641 453711858
147679897 275450390
871549713 368160131
945135251 515070794
113677189 553747963
648722370 798825746
334960984 163211483
477414168 849868430
46724716 593116536
424597820 84043071
456749260 981436379
167906984 546584517
187306934 201207913
535850448 43428774
602081737 111568378
607467836 80430906
965538187 537789555
69199019 485172741
267885487 934316143
883812229 276272851
507976072 19708905
951100460 639017801
43859603 556279043
300658736 79240016
231304846 220059094
854667690 399502355

輸出：

607281204170558988

說明： 請注意輸出的答案可能超出 32 位元整數的範圍。

042 - 9 的倍數 / Multiple of 9（★4）

題目描述

請計算僅由非 00 數字（即 1∼91 \sim 9）組成的正整數 XX 中，同時滿足以下條件的正整數共有多少個？並將答案對 109+710^9 + 7 取模後輸出。

  • XX 是 99 的倍數
  • 將 XX 以十進位表示時，各個數位之和為 KK

數據範圍

  • 1≤K≤1000001 \leq K \leq 100000
  • KK 為整數

輸入格式

K

輸出格式

請將答案輸出在一行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

1

輸出：

0

說明： 僅由非 00 數字組成的正整數中，各數位之和為 11 的數只有 11。 由於 11 不是 99 的倍數，因此不存在符合條件的整數 XX。故答案為 00 種。

❌ Unsupported block (heading_4)

輸入：

234

輸出：

757186539

說明： 請注意需要輸出對 109+710^9 + 7 取模後的餘數。

043 - 睡眠不足的迷宮挑戰 / Maze Challenge with Lack of Sleep（★4）

題目描述

有一個由 HH 行 WW 列組成的網格狀迷宮，從上數來第 ii 行、從左數來第 jj 列的格子記為 (i,j)(i,j)。當 Si,j=S_{i,j} = # 時該格子為牆壁；當 Si,j=S_{i,j} = . 時該格子不是牆壁（為通道）。

你想透過重複移動到上下左右相鄰且非牆壁的格子，從格子 (rs,cs)(r_s,c_s) 移動到格子 (rt,ct)(r_t,c_t)。然而，如果移動方向改變的次數過多會讓大腦感到疲倦，因此轉向次數越少越好。此外，不能移動到迷宮外部。

請計算移動方向改變次數（轉向次數）的最小值。

數據範圍

  • 2≤H,W≤10002 \leq H,W \leq 1000
  • 1≤rs,rt≤H1 \leq r_s,r_t \leq H
  • 1≤cs,ct≤W1 \leq c_s,c_t \leq W
  • (rs,cs)≠(rt,ct)(r_s,c_s) \ne (r_t,c_t)
  • H,W,rs,cs,rt,ctH,W,r_s,c_s,r_t,c_t 皆為整數
  • Si,jS_{i,j} 為 # 或 .
  • Srs,cs,Srt,ctS_{r_s,c_s},S_{r_t,c_t} 皆為 .
  • 保證可以從格子 (rs,cs)(r_s,c_s) 移動到格子 (rt,ct)(r_t,c_t)

輸入格式

H W
r_s c_s
r_t c_t
S_{1,1} S_{1,2} … S_{1,W}
⋮
S_{H,1} S_{H,2} … S_{H,W}

輸出格式

輸出轉向次數的最小值。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 3
1 1
3 3
..#
#.#
#..

輸出：

2

說明： 沿著最優路徑前進時，在格子 (1,2)(1,2) 和格子 (3,2)(3,2) 各改變了一次移動方向，共改變 22 次方向。

❌ Unsupported block (heading_4)

輸入：

3 3
2 1
2 3
#.#
...
#.#

輸出：

0

❌ Unsupported block (heading_4)

輸入：

4 6
2 1
1 5
...#..
.#.##.
.#....
...##.

輸出：

5

044 - 平移與交換 / Shift and Swapping（★3）

題目描述

給定一個長度為 NN 的整數數列 {An}\{A_n\}。請依序處理以下 QQ 個操作：

  • 當 Ti=1T_i=1 時：交換數列中第 xx 項（=Ax=A_x）與第 yy 項（=Ay=A_y）的值。
  • 當 Ti=2T_i=2 時：將數列向右平移（循環右移）一位。也就是說，將數列變為 {An}=AN,A1,A2,⋯ ,AN−1\{A_n\} = A_N, A_1, A_2, \cdots, A_{N-1}。
  • 當 Ti=3T_i=3 時：求出此時數列中第 xx 項（=Ax=A_x）的值。

數據範圍

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Q≤2×1051 \leq Q \leq 2 \times 10^5
  • 1≤An≤1091 \leq A_n \leq 10^9 (1≤n≤N1 \leq n \leq N)
  • 1≤Ti≤31 \leq T_i \leq 3 (1≤i≤Q1 \leq i \leq Q)
  • 若 Ti=1T_i = 1，則 1≤xi,yi≤N1 \leq x_i, y_i \leq N 且 xi≠yix_i \neq y_i
  • 若 Ti=2T_i = 2，則 xi=yi=0x_i=y_i=0
  • 若 Ti=3T_i = 3，則 1≤xi≤N1 \leq x_i \leq N 且 yi=0y_i=0
  • 輸入中的所有數值皆為整數

輸入格式

N Q
A_1 A_2 … A_N
T_1 x_1 y_1
⋮
T_Q x_Q y_Q

輸出格式

對於所有 Ti=3T_i=3 的查詢，依序輸出其答案，每個答案佔一行。

範例測資

❌ Unsupported block (heading_4)

輸入：

8 5
6 17 2 4 17 19 1 7
2 0 0
1 7 2
1 2 6
1 4 5
3 4 0

輸出：

4

說明： 最初，數列為 6,17,2,4,17,19,1,76, 17, 2, 4, 17, 19, 1, 7。 第 1 個操作將數列向右平移，操作後數列變為 7,6,17,2,4,17,19,17, 6, 17, 2, 4, 17, 19, 1。 第 2 個操作交換數列的第 77 項與第 22 項，操作後數列變為 7,19,17,2,4,17,6,17, 19, 17, 2, 4, 17, 6, 1。 第 3 個操作交換數列的第 22 項與第 66 項，操作後數列變為 7,17,17,2,4,19,6,17, 17, 17, 2, 4, 19, 6, 1。 第 4 個操作交換數列的第 44 項與第 55 項，操作後數列變為 7,17,17,4,2,19,6,17, 17, 17, 4, 2, 19, 6, 1。 第 5 個操作輸出數列第 44 項的值 A4=4A_4=4。

❌ Unsupported block (heading_4)

輸入：

9 6
16 7 10 2 9 18 15 20 5
2 0 0
1 1 4
2 0 0
1 8 5
2 0 0
3 6 0

輸出：

18

說明： 最初，數列為 16,7,10,2,9,18,15,20,516, 7, 10, 2, 9, 18, 15, 20, 5。 第 1 個操作後，數列變為 5,16,7,10,2,9,18,15,205, 16, 7, 10, 2, 9, 18, 15, 20。 第 2 個操作後，數列變為 10,16,7,5,2,9,18,15,2010, 16, 7, 5, 2, 9, 18, 15, 20。 第 3 個操作後，數列變為 20,10,16,7,5,2,9,18,1520, 10, 16, 7, 5, 2, 9, 18, 15。 第 4 個操作後，數列變為 20,10,16,7,18,2,9,5,1520, 10, 16, 7, 18, 2, 9, 5, 15。 第 5 個操作後，數列變為 15,20,10,16,7,18,2,9,515, 20, 10, 16, 7, 18, 2, 9, 5。 第 6 個操作輸出數列第 66 項的值 A6=18A_6=18。

❌ Unsupported block (heading_4)

輸入：

11 18
23 92 85 34 21 63 12 9 81 44 96
3 10 0
3 5 0
1 3 4
2 0 0
1 4 11
3 11 0
1 3 5
2 0 0
2 0 0
3 9 0
2 0 0
3 6 0
3 10 0
1 6 11
2 0 0
3 10 0
3 4 0
3 5 0

輸出：

44
21
34
63
85
63
21
34
96

045 - 簡易分組 / Simple Grouping（★6）

題目描述

在歐幾里得平面上有 NN 個點 (X1,Y1)(X_1,Y_1), (X2,Y2)(X_2,Y_2), ⋯\cdots, (XN,YN)(X_N,Y_N)。 考慮將這 NN 個點分成 KK 個分組，且必須滿足以下條件：

  • 每個點不能屬於多個分組。
  • 每個點都必須屬於某個分組。
  • 不能存在任何沒有包含任何點的分組（即不可有空分組）。

在所有滿足條件的分組方案中，請最小化「同一分組內兩點間距離的最大值」。 請輸出此時同一分組內兩點間距離最大值的平方。

保證此時最大值的平方一定為整數。

數據範圍

  • 2≤K<N≤152\leq K< N\leq 15
  • 0≤Xi,Yi≤1090\leq X_i,Y_i\leq 10^9
  • 若 i≠ji\neq j，則 (Xi,Yi)≠(Xj,Yj)(X_i,Y_i)\neq (X_j,Y_j)
  • 所有輸入皆為整數

輸入格式

N K
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N

輸出格式

在所有可能的分組方案中，計算同一分組內兩點間距離最大值的最小值，並將該最小值的平方以整數形式輸出在一行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 2
0 1
1 2
2 0

輸出：

2

說明： 若分成 {(0,1),(1,2)}\{(0,1),(1,2)\} 與 {(2,0)}\{(2,0)\} 兩組，則同一組內兩點間距離的最大值為 2\sqrt 2，這是所有分組方案中的最小值。因此輸出其平方值 22。

❌ Unsupported block (heading_4)

輸入：

5 3
0 0
1 1
0 2
2 3
3 1

輸出：

4

說明： 若分成 {(0,0),(0,2)}\{(0,0),(0,2)\}、{(1,1),(3,1)}\{(1,1),(3,1)\}、{(2,3)}\{(2,3)\} 三組，兩點間距離的最大值為 22。 若分成 {(0,0)}\{(0,0)\}、{(0,2),(1,1)}\{(0,2),(1,1)\}、{(2,3),(3,1)}\{(2,3),(3,1)\}，此時同一組內兩點間距離最大值分別為 2\sqrt2 與 5\sqrt5。

❌ Unsupported block (heading_4)

輸入：

10 4
0 3
3 5
2 7
9 0
5 6
4 3
7 8
6 5
9 9
2 1

輸出：

20

❌ Unsupported block (heading_4)

輸入：

3 2
0 0
500000000 500000000
1000000000 1000000000

輸出：

500000000000000000

046 - 我愛 46 / I Love 46（★3）

題目描述

給定三個長度均為 NN 的整數數列 A=(A1,A2,⋯ ,AN)A = (A_1, A_2, \cdots, A_N)、B=(B1,B2,⋯ ,BN)B = (B_1, B_2, \cdots, B_N)、C=(C1,C2,⋯ ,CN)C = (C_1, C_2, \cdots, C_N)。

請計算滿足 Ai+Bj+CkA_i + B_j + C_k 是 4646 的倍數的三元組 (i,j,k)(i, j, k)（1≤i,j,k≤N1 \leq i,j,k \leq N）的組合總數。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 0≤Ai,Bj,Ck≤1090 \leq A_i, B_j, C_k \leq 10^9
  • 所有輸入皆為整數

輸入格式

N
A_1 A_2 … A_N
B_1 B_2 … B_N
C_1 C_2 … C_N

輸出格式

將答案輸出在一行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

3
10 13 93
5 27 35
55 28 52

輸出：

3

說明： 使 Ai+Bj+CkA_i + B_j + C_k 為 4646 的倍數的三元組 (i,j,k)(i, j, k) 共有 (1,2,1)(1, 2, 1)、(2,1,2)(2, 1, 2)、(2,2,3)(2, 2, 3) 這 33 組。

❌ Unsupported block (heading_4)

輸入：

3
10 56 102
16 62 108
20 66 112

輸出：

27

說明： 無論如何選擇，這三個整數之和都是 4646 的倍數。

❌ Unsupported block (heading_4)

輸入：

20
238 395 46 238 264 114 354 52 324 14 472 64 307 280 209 24 165 194 179 248
270 83 377 332 173 21 362 75 66 342 229 117 124 481 48 235 376 13 420 74
175 427 76 278 486 169 311 47 348 225 41 482 355 356 263 95 170 156 340 289

輸出：

183

047 - 單色對角線 / Monochromatic Diagonal（★7）

題目描述

給定兩個僅由字元 R、G、B 組成且長度均為 NN 的字串 S,TS, T。 令 SS 的第 ii 個字元為 sis_i，TT 的第 jj 個字元為 tjt_j。

現有一個 N×NN\times N 的網格，並依照以下規則給網格塗色。 此處，將字元 R、G、B 分別對應為紅色、綠色、藍色：

  • 當 si=tjs_i = t_j 時，將從上數來第 ii 行、從左數來第 jj 列的格子塗成顏色 sis_i。
  • 當 si≠tjs_i \neq t_j 時，將從上數來第 ii 行、從左數來第 jj 列的格子塗成紅、綠、藍三種顏色中與 sis_i 和 tjt_j 皆不同的第三種顏色。

在這個網格中，共有 2N−12N-1 條由左上往右下延伸的斜列（對角線）。 請計算有多少條斜列上的所有格子都被塗成了同一種顏色。

更嚴格地說，請計算滿足以下條件的整數 k (−N<k<N)k\ (-N < k < N) 共有多少個：

  • 存在某種顏色 cc，使得對於所有滿足 1≤i≤N1 \leq i \leq N 且 1≤i+k≤N1 \leq i+k \leq N 的整數 ii，格子 (i,i+k)(i, i+k) 的顏色皆為 cc。

數據範圍

  • 1≤N≤1061 \leq N \leq 10^6
  • S,TS, T 僅由字元 R、G、B 組成

輸入格式

N
S
T

輸出格式

請將所有格子均塗為相同顏色的斜列數量輸出在一行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

5
RGBGB
GRGRB

輸出：

6

說明： 滿足條件的 kk 共有 66 個，分別為 k=−4,−3,−1,2,3,4k = -4, -3, -1, 2, 3, 4。 例如，k=−3k = -3 符合條件，因為格子 (4,1)(4,1) 和 (5,2)(5,2) 都被塗成了綠色。

❌ Unsupported block (heading_4)

輸入：

3
RRR
BBB

輸出：

5

❌ Unsupported block (heading_4)

輸入：

10
BGGGRBBGRG
RGBBRGRGGG

輸出：

4

048 - 我不會留級 / I will not drop out（★3）

題目描述

有一場包含 NN 道題目的考試。第 ii 道題目的滿分為 AiA_i 分，部分分為 BiB_i 分。此處部分分小於滿分且大於滿分的一半，即滿足 Ai2<Bi<Ai\frac{A_i}{2} < B_i < A_i。

E869120 君對於任何一道題目，只要花費 11 分鐘就能獲得該題的部分分；如果再花費 11 分鐘（累計花費 22 分鐘），就能獲得該題的滿分。

在考試時間共 KK 分鐘內，請計算 E869120 君所能獲得的總得分的最大值。

數據範圍

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤K≤2N1 \leq K \leq 2N
  • 3≤Ai≤109 (1≤i≤N)3 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
  • Ai2<Bi<Ai (1≤i≤N)\frac{A_i}{2} < B_i < A_i \ (1 \leq i \leq N)
  • 所有輸入皆為整數

輸入格式

N K
A_1 B_1
A_2 B_2
⋮
A_N B_N

輸出格式

請輸出 E869120 君在 KK 分鐘內所能獲得的總得分的最大值。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 3
4 3
9 5
15 8
8 6

輸出：

21

說明： E869120 君可以在第 33 題花費 22 分鐘取得滿分 1515 分，並在第 44 題花費 11 分鐘取得部分分 66 分，總共獲得 2121 分。 由於無法獲得超過 2121 分，因此答案為 2121。

❌ Unsupported block (heading_4)

輸入：

2 2
7 6
3 2

輸出：

8

❌ Unsupported block (heading_4)

輸入：

10 12
987753612 748826789
36950727 36005047
961239509 808587458
905633062 623962559
940964276 685396947
959540552 928301562
60467784 37828572
953685176 482123245
87983282 66762644
912605260 709048491

輸出：

6437530406

049 - 翻轉數位 2 / Flip Digits 2（★6）

題目描述

E869120 君有一個長度為 NN 的二進位字串 SS。最初，SS 的所有字元都是 0。

ABC 商店中販售 MM 個道具，編號分別為 11 到 MM。道具 ii 的售價為 CiC_i 元，使用該道具可以將 SS 中第 LiL_i 到第 RiR_i 個字元進行翻轉。也就是說，將 SS 的第 Li∼RiL_i \sim R_i 個字元中，原為 0 的變為 1，原為 1 的變為 0。

E869120 君希望從這 MM 個道具中購買若干個，使得以下條件得到滿足：

條件：對於任意長度為 NN 的二進位字串 TT（共有 2N2^N 種可能），都可以透過從已購買的道具中選擇道具並使用任意次（也可以是 00 次），將 SS 變換為 TT。

請計算為了滿足條件，他所需要購買道具的總金額的最小值。

如果即使買下所有道具也無法滿足條件，請輸出 -1。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤M≤1051 \leq M \leq 10^5
  • 1≤Ci≤1091 \leq C_i \leq 10^9
  • 1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N
  • 所有輸入皆為整數

輸入格式

N M
C_1 L_1 R_1
C_2 L_2 R_2
⋮
C_M L_M R_M

輸出格式

如果買下所有道具仍無法滿足條件，請輸出 -1。 否則，輸出為了滿足條件 E869120 君需要購買道具的總金額最小值。

範例測資

❌ Unsupported block (heading_4)

輸入：

2 3
1 1 1
1 2 2
10 1 2

輸出：

2

說明： 考慮購買道具 1,21, 2 的情況。 對於每個 TT，例如可以透過以下操作將 SS 變換為 TT： - 當 T=T= 00 時：不進行任何操作 - 當 T=T= 01 時：使用道具 22 - 當 T=T= 10 時：使用道具 11 - 當 T=T= 11 時：先使用道具 11，接著使用道具 22

此時總金額為 1+1=21 + 1 = 2 元，為最小值。

❌ Unsupported block (heading_4)

輸入：

2 3
1 1 1
10 2 2
1 1 2

輸出：

2

說明： 考慮購買道具 1,31, 3 的情況。 對於每個 TT，例如可以透過以下操作將 SS 變換為 TT： - 當 T=T= 00 時：不進行任何操作 - 當 T=T= 01 時：先使用道具 33，接著使用道具 11 - 當 T=T= 10 時：使用道具 11 - 當 T=T= 11 時：使用道具 33

此時總金額為 1+1=21 + 1 = 2 元，為最小值。

❌ Unsupported block (heading_4)

輸入：

4 5
3 1 2
5 2 4
9 3 4
4 1 4
8 2 4

輸出：

-1

說明： 輸入中可能包含具有相同 (Li,Ri)(L_i, R_i) 的多個道具。

❌ Unsupported block (heading_4)

輸入：

9 11
10 2 7
100 1 6
1 2 8
39 4 5
62 3 4
81 1 3
55 8 8
91 5 5
14 8 9
37 5 5
41 7 9

輸出：

385

050 - 階梯跳躍 / Stair Jump（★3）

題目描述

E869120 君準備爬上一座共有 NN 階的樓梯。他一步可以往上爬 11 階或 LL 階。

請計算從第 00 階出發、到達第 NN 階的移動方法共有多少種，並將答案對 109+710^9 + 7 取模後輸出。

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • 2≤L≤1000002 \leq L \leq 100000
  • 所有輸入皆為整數

輸入格式

N L

輸出格式

請將答案輸出在一行中。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 2

輸出：

3

說明： 移動方法共有以下 33 種： - 爬 11 階 →\to 爬 11 階 →\to 爬 11 階 - 爬 11 階 →\to 爬 22 階 - 爬 22 階 →\to 爬 11 階

❌ Unsupported block (heading_4)

輸入：

4 4

輸出：

2

說明： 有一步一步爬 11 階的方法，以及一口氣爬 44 階的方法。

❌ Unsupported block (heading_4)

輸入：

5 2

輸出：

8

❌ Unsupported block (heading_4)

輸入：

6783 125

輸出：

674508908

說明： 請注意需要輸出對 109+710^9 + 7 取模後的餘數。

051 - 典型商店 / Typical Shop（★5）

題目描述

典型商店中有 NN 件互相可區分的商品。商品編號為 1,2,…,N1, 2, \dots, N，其中商品 ii 的價格為 AiA_i 元。

你想從商店販售的商品中恰好挑選 KK 件，且使得總價格在 PP 元以下。請問一共有多少種不同的挑選方式？

注意：如果存在某個商品 ii，在一種挑選方式中被選中而在另一種方式中未被選中，則這兩種挑選方式視為不同。

數據範圍

  • 1≤K≤N≤401 \leq K \leq N \leq 40
  • 1≤P≤10181 \leq P \leq 10^{18}
  • 1≤Ai≤10161 \leq A_i \leq 10^{16} (1≤i≤N1 \leq i \leq N)
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N K P
A_1 A_2 … A_N

輸出格式

輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

5 2 10
3 8 7 5 11

輸出：

2

說明： 恰好挑選 22 件商品且總價格在 1010 元以下的挑選方式有以下 22 種： - 選擇商品 11 與商品 33（3+7=103 + 7 = 10 元） - 選擇商品 11 與商品 44（3+5=83 + 5 = 8 元）

❌ Unsupported block (heading_4)

輸入：

5 1 10
7 7 7 7 7

輸出：

5

說明： 請注意，即使商品的價格相同，也視為不同的商品。

❌ Unsupported block (heading_4)

輸入：

40 20 100
1 3 1 3 4 1 3 5 5 3 3 4 1 5 4 4 3 1 3 4 1 3 2 4 4 1 5 2 5 3 1 3 3 3 5 5 5 2 3 5

輸出：

137846528820

說明： 請注意答案可能超出 3232 位元整數的表示範圍。

052 - 骰子乘積 / Dice Product（★3）

題目描述

有 NN 個 66 面骰子，編號分別為 1,2,3,…,N1, 2, 3, \dots, N。骰子 ii 的第 jj 個面（1≤j≤61 \leq j \leq 6）上寫著整數 Ai,jA_{i,j}。對於每個骰子，其各面上所寫的整數皆不相同。

現在，我們將擲出骰子的點數定義得分如下： - 得分為 NN 個骰子擲出點數的總乘積。 - 也就是說，若骰子 ii 擲出的點數為 RiR_i，則得分計算為 R1×R2×⋯×RNR_1 \times R_2 \times \dots \times R_N。

擲這 NN 個骰子一共有 6N6^N 種可能的結果。請計算所有可能結果的得分總和 SS 除以 109+710^9 + 7 的餘數。此處假設所有骰子彼此皆可區分。

數據範圍

  • 1≤N≤1001 \leq N \leq 100
  • 1≤Ai,1<Ai,2<Ai,3<Ai,4<Ai,5<Ai,6≤1001 \leq A_{i,1} < A_{i,2} < A_{i,3} < A_{i,4} < A_{i,5} < A_{i,6} \leq 100
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N
A_{1,1} A_{1,2} A_{1,3} A_{1,4} A_{1,5} A_{1,6}
⋮
A_{N,1} A_{N,2} A_{N,3} A_{N,4} A_{N,5} A_{N,6}

輸出格式

輸出 SS 除以 109+710^9+7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

2
1 2 3 5 7 11
4 6 8 9 10 12

輸出：

1421

說明： 例如，若擲出的點數分別為 3,103, 10，則得分為 3×10=303 \times 10 = 30。擲骰子的結果共有 62=366^2 = 36 種可能，所有可能得分的總和為 14211421。

❌ Unsupported block (heading_4)

輸入：

1
11 13 17 19 23 29

輸出：

112

說明： 只有 11 個骰子時，答案即為該骰子各面上所寫整數的總和。

❌ Unsupported block (heading_4)

輸入：

7
19 23 51 59 91 99
15 45 56 65 69 94
7 11 16 34 59 95
27 30 40 43 83 85
19 23 25 27 45 99
27 48 52 53 60 81
21 36 49 72 82 84

輸出：

670838273

說明： 得分總和為 S=211411531150718976S = 211411531150718976，請注意應輸出 SS 除以 109+710^9+7 的餘數 670838273670838273。

053 - 離散探測 / Discrete Dowsing（★7）

題目描述

這是一道互動題（Interactive Problem）。

請針對 TT 組測試資料求解以下問題：

有一個隱藏的長度為 NN 的非負整數數列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) 以及一個整數 kk（1≤k≤N1 \le k \le N）。已知數列 AA 滿足以下條件： - 當 1≤i≤k−11 \le i \le k-1 時，Ai<Ai+1A_i < A_{i+1}（嚴格單調遞增） - 當 k≤i≤N−1k \le i \le N-1 時，Ai>Ai+1A_i > A_{i+1}（嚴格單調遞減）

在給定整數 NN 後，你可以發送若干次查詢。在一次查詢中，你可以指定一個滿足 1≤i≤N1 \le i \le N 的索引 ii 來獲取 AiA_i 的值。請用盡可能少的查詢次數找出數列 AA 的最大值（詳見子任務與計分）。

❌ Unsupported block (heading_4)

本題的分數根據所有測試資料中單一測試資料的最大查詢次數 QmaxQ_{\mathrm{max}} 計算： - 若 1500<Qmax1500 < Q_{\mathrm{max}}，得 00 點 - 若 40<Qmax≤150040 < Q_{\mathrm{max}} \leq 1500 ，得 11 點 - 若 22<Qmax≤4022 < Q_{\mathrm{max}} \leq 40 ，得 33 點 - 若 15<Qmax≤2215 < Q_{\mathrm{max}} \leq 22 ，得 44 點 - 若 Qmax≤15Q_{\mathrm{max}} \leq 15 ，得 77 點

數據範圍

  • 1≤T≤501 \leq T \leq 50
  • 1≤N≤15001 \leq N \leq 1500
  • 0≤Ai≤1090 \leq A_i \leq 10^9（1≤i≤N1 \leq i \leq N）
  • 所有輸入值皆為整數

輸入格式

首先，標準輸入會給出測試資料組數 TT：

T

隨後進行 TT 組測試資料的互動。

每組測試資料開始時，由標準輸入給定數列長度 NN：

N

發送查詢時，請依照以下格式輸出至標準輸出：

? i

評判系統會對此查詢返回數列中該位置的值：

A_i

當確定數列 AA 的最大值為 AmaxA_{\mathrm{max}} 時，請依照以下格式輸出答案：

! A_{max}

輸出答案後，若還有下一組測試資料則繼續處理；若無則請立即結束程式。

若你的程式輸出了無效的查詢，評判系統將輸入 -1。此時請立即終止程式。

輸出格式

本題為互動題，請依照上述互動協議進行輸出，並在每次輸出後清空標準輸出緩衝區（flush）。

注意事項

  • 本題的評判是自適應的（Adaptive）。換句話說，只要與先前所有查詢的結果不產生矛盾，數列的內容可能會在互動過程中發生改變。
  • 在輸出所有測試資料的答案後，或收到 1 後，若未立即結束程式，評測結果將未定義。
  • 每次輸出後請務必清空標準輸出緩衝區（flush），否則可能會導致 TLE。
  • 由於 AtCoder 系統特性，只要獲得 11 點以上就會顯示為 AC（即使為 AC 也不代表獲得滿分）。

範例測資

❌ Unsupported block (heading_4)

互動過程說明： | 輸入 | 輸出 | 說明 | | :— | :— | :— | | 1 | | T=1T = 1 | | 8 | | 第 11 組測試資料，N=8N = 8 | | | ? 6 | 查詢 A6A_6 | | 6 | | 返回 A6=6A_6 = 6 | | | ? 7 | 查詢 A7A_7 | | 9 | | 返回 A7=9A_7 = 9 | | | ? 8 | 查詢 A8A_8 | | 1 | | 返回 A8=1A_8 = 1 | | | ! 9 | 回答最大值為 99 |

說明： 隱藏數列 AA 為 (1,2,3,4,5,6,9,1)(1, 2, 3, 4, 5, 6, 9, 1)，k=7k = 7。數列 AA 的最大值為 99。 例如，在第 11 次查詢結束時，數列 AA 也可以是 (7,8,9,8,7,6,5,4)(7, 8, 9, 8, 7, 6, 5, 4)，因為這與當前已查詢的內容不矛盾，評判系統有可能動態調整成該數列。

❌ Unsupported block (heading_4)

互動過程說明： | 輸入 | 輸出 | 說明 | | :— | :— | :— | | 2 | | T=2T = 2 | | 1 | | 第 11 組測試資料，N=1N = 1 | | | ? 1 | 查詢 A1A_1 | | 0 | | 返回 A1=0A_1 = 0 | | | ! 0 | 回答最大值為 00 | | 1 | | 第 22 組測試資料，N=1N = 1 | | | ? 1 | 查詢 A1A_1 | | 1000000000 | | 返回 A1=1000000000A_1 = 1000000000 | | | ! 1000000000 | 回答最大值為 10000000001000000000 |

054 - 高橋數 / Takahashi Number（★6）

題目描述

由於研究員高橋先生撰寫了大量的共同著作論文，同行們出於敬意與幽默感，創造了「高橋數」的概念。每位研究員的高橋數定義如下： - 高橋先生的高橋數為 00。 - 若某位研究員曾與高橋數為 nn 的研究員共同發表過論文，且未曾與高橋數小於 nn 的研究員共同發表過論文，則該研究員的高橋數定義為 n+1n+1。 - 若根據上述規則無法決定高橋數，則該研究員的高橋數未定義（不存在）。

目前，在這個世界上包括高橋先生在內共有 NN 位研究員，共發表了 MM 篇合著論文。第 ii 篇合著論文由 KiK_i 位研究員 Ri,1,…,Ri,KiR_{i,1}, \dots, R_{i,K_i} 共同撰寫。在此，高橋先生為研究員 11。 請問：對於這 NN 位研究員中的每一位，其高橋數是否已定義？若有定義，其數值為多少？

數據範圍

  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤M≤1051 \leq M \leq 10^5
  • 2≤Ki≤N2 \leq K_i \leq N
  • K1+K2+⋯+KM≤2×105K_1+K_2+\dots+K_M \leq 2 \times 10^5
  • 1≤Ri,1<⋯<Ri,Ki≤N1 \leq R_{i,1} < \dots < R_{i,K_i} \leq N
  • 輸入的所有數值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N M
K_1
R_{1,1} … R_{1,K_1}
⋮
K_M
R_{M,1} … R_{M,K_M}

輸出格式

輸出共有 NN 行。第 jj 行（1≤j≤N1 \leq j \leq N）若研究員 jj 的高橋數存在，輸出其高橋數；若不存在，輸出 -1。

範例測資

❌ Unsupported block (heading_4)

輸入：

6 3
3
1 2 3
2
3 4
2
5 6

輸出：

0
1
1
2
-1
-1

說明：66 位研究員的高橋數分別求法如下： - 研究員 11（高橋先生）根據定義高橋數為 00。 - 研究員 2,32, 3 曾與高橋數為 00 的研究員 11 合著，且未曾與高橋數小於 00 的研究員合著，因此高橋數為 11。 - 研究員 44 曾與高橋數為 11 的研究員 33 合著，且未曾與高橋數小於 11 的研究員合著，因此高橋數為 22。 - 研究員 5,65, 6 彼此合著，但未曾與任何已有定義高橋數的研究員合著，因此高橋數未定義。

綜上所述，從研究員 11 到 66 的高橋數依序為 0,1,1,2,−1,−10, 1, 1, 2, -1, -1。

❌ Unsupported block (heading_4)

輸入：

4 3
2
1 2
2
2 3
2
3 4

輸出：

0
1
2
3

❌ Unsupported block (heading_4)

輸入：

4 1
3
2 3 4

輸出：

0
-1
-1
-1

❌ Unsupported block (heading_4)

輸入：

11 5
4
2 6 9 10
3
1 3 8
5
2 4 6 8 10
2
6 7
4
5 6 7 8

輸出：

0
2
1
2
2
2
2
1
3
2
-1

055 - 選取五個數 / Select 5（★2）

題目描述

給定 NN 個整數 A1,A2,…,ANA_1, A_2, \dots, A_N。 請計算從中選取 55 個整數的方法數，使得這 55 個整數的乘積除以 PP 的餘數為 QQ。

數據範圍

  • 5≤N≤1005 \leq N \leq 100
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • 0≤Q<P≤1090 \leq Q < P \leq 10^9
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N P Q
A_1 A_2 A_3 … A_N

輸出格式

輸出一行表示滿足條件的組合數。

範例測資

❌ Unsupported block (heading_4)

輸入：

6 7 1
1 2 3 4 5 6

輸出：

1

說明： 只有選取 A1,A2,A3,A4,A5A_1, A_2, A_3, A_4, A_5 時（1×2×3×4×5=1201 \times 2 \times 3 \times 4 \times 5 = 120，120 mod 7=1120 \bmod 7 = 1），乘積除以 77 的餘數才為 11。

❌ Unsupported block (heading_4)

輸入：

10 1 0
0 0 0 0 0 0 0 0 0 0

輸出：

252

056 - 幸運福袋 / Lucky Bag（★5）

題目描述

在高橋屋百貨公司，將連續 NN 天舉辦新春特賣活動。 在第 ii（1≤i≤N1 \leq i \leq N）天，將販售 AiA_i 元的福袋 A 與 BiB_i 元的福袋 B。

低橋君打算在這 NN 天內，每天都前往高橋屋購買福袋 A 或福袋 B 兩者之一。（每天必須且只能購買一件，不能什麼都不買。） 他希望在 NN 天內購買的 NN 個福袋總金額恰好為 SS 元。

由於低橋君不擅長計算，請你代為規劃符合條件的福袋購買計畫。 如果不存在滿足條件的購買計畫，請回報無解。

數據範圍

  • 1≤N≤1001 \leq N \leq 100
  • 1≤S≤1051 \leq S \leq 10^5
  • 1≤Ai,Bi≤1051 \leq A_i, B_i \leq 10^5（1≤i≤N1 \leq i \leq N）
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N S
A_1 B_1
A_2 B_2
⋮
A_N B_N

輸出格式

請以長度為 NN 的字串 TT 輸出滿足題目條件的購買計畫： - 若第 ii（1≤i≤N1 \leq i \leq N）天購買福袋 A，則 Ti=T_i = 'A'；若購買福袋 B，則 Ti=T_i = 'B'。

如果不存在滿足條件的購買計畫，請輸出 'Impossible'。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 34
3 14
15 9
26 5

輸出：

BAB

說明： 依照以下方式購買，總金額恰好為 14+15+5=3414 + 15 + 5 = 34 元： - 第 11 天購買福袋 B（1414 元） - 第 22 天購買福袋 A（1515 元） - 第 33 天購買福袋 B（55 元）

❌ Unsupported block (heading_4)

輸入：

5 77
1 16
3 91
43 9
4 26
23 11

輸出：

BABBA

說明： 按照此種購買方式，總金額為 16+3+9+26+23=7716 + 3 + 9 + 26 + 23 = 77 元。 除此之外，輸出 BAAAB 其總金額亦為 16+3+43+4+11=7716 + 3 + 43 + 4 + 11 = 77 元，同樣為正確答案。

❌ Unsupported block (heading_4)

輸入：

5 59
8 13
55 5
58 8
23 14
4 61

輸出：

Impossible

說明： 也有可能不存在滿足條件的購買方式。

057 - 翻轉開關 / Flip Flap（★6）

題目描述

有 MM 個編號為 1,2,…,M1, 2, \dots, M 的面板，所有面板一開始皆為背面朝上。 此外，你面前有 NN 個編號為 1,2,…,N1, 2, \dots, N 的開關。按下開關 ii 會觸發以下事件： - TiT_i 個面板 Ai,1,…,Ai,TiA_{i,1}, \dots, A_{i,T_i} 會被翻轉，正反面狀態改變。

在此，每個開關一旦按下後便不能再按第二次。

你的任務是將這 MM 個面板的正反面狀態調整為期望的狀態。期望的狀態由長度為 MM 且由 0 和 1 組成的序列 SS 給定，其中 Sj=0S_j=0 代表希望面板 jj 背面朝上，Sj=1S_j=1 代表希望面板 jj 正面朝上。

不考慮按下順序時，一共有 2N2^N 種按下開關的組合方式。請問其中有多少種方式能達到期望的狀態？由於答案可能非常大，請輸出答案除以 998244353998244353 的餘數。

數據範圍

  • 1≤N,M≤3001 \leq N, M \leq 300
  • 1≤Ti≤M1 \leq T_i \leq M
  • 1≤Ai,1<⋯<Ai,Ti≤M1 \leq A_{i,1} < \dots < A_{i,T_i} \leq M
  • Si=0S_i = 0 或 Si=1S_i = 1
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N M
T_1
A_{1,1} … A_{1,T_1}
⋮
T_N
A_{N,1} … A_{N,T_N}
S_1 … S_M

輸出格式

輸出能滿足期望狀態的開關按下方案數除以 998244353998244353 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

2 3
2
1 2
2
2 3
1 0 1

輸出：

1

說明： 按下開關 11 與開關 22，可以使 33 個面板的正反面狀態符合期望。此外不存在其他方式能使 33 個面板符合期望，因此答案為 11 種。

❌ Unsupported block (heading_4)

輸入：

2 3
1
1
1
2
0 1 1

輸出：

0

說明： 不存在任何能改變面板 33 狀態的開關，因此無法將面板 33 變為正面朝上。故答案為 00 種。

❌ Unsupported block (heading_4)

輸入：

3 2
1
1
1
2
1
2
1 0

輸出：

2

說明： 使 22 個面板符合期望的開關按下方式有以下 22 種： - 僅按下開關 11。 - 按下開關 1,2,31, 2, 3 全部。

❌ Unsupported block (heading_4)

輸入：

13 6
3
1 3 5
3
1 4 5
4
3 4 5 6
2
2 5
4
1 2 3 5
3
3 4 6
3
4 5 6
6
1 2 3 4 5 6
4
1 3 5 6
3
1 2 4
3
1 5 6
4
1 2 3 4
1
5
1 0 0 1 0 0

輸出：

128

058 - 奇特計算機 / Original Calculator（★4）

題目描述

你擁有一台奇特的計算機。這台計算機可以顯示一個介於 00 到 105−110^5-1 之間的整數。計算機上有一個名為 按鈕 A 的按鈕。當螢幕上顯示整數 xx 時，按下一次按鈕 A 會依序執行以下處理： - 計算 xx 在十進位表示下的各位數字之和，記為 yy。 - 計算 x+yx + y 除以 10510^5 的餘數，記為 zz。 - 將螢幕上顯示的整數更新為 zz。

例如，當顯示 9999999999 時按下一次按鈕 A，由於 99999+(9+9+9+9+9)=10004499999 + (9 + 9 + 9 + 9 + 9) = 100044，顯示的整數將變更為 4444。

現在，這台計算機上顯示著整數 NN。請計算按下按鈕 A 恰好 KK 次後，計算機上顯示的整數。

數據範圍

  • 0≤N≤105−10 \leq N \leq 10^5-1
  • 1≤K≤10181 \leq K \leq 10^{18}
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N K

輸出格式

輸出按下按鈕 A 共 KK 次後顯示的整數。

範例測資

❌ Unsupported block (heading_4)

輸入：

5 3

輸出：

13

說明： - 第 11 次按下按鈕 A 後顯示的整數為 5+(5)=105 + (5) = 10。 - 第 22 次按下按鈕 A 後顯示的整數為 10+(1+0)=1110 + (1 + 0) = 11。 - 第 33 次按下按鈕 A 後顯示的整數為 11+(1+1)=1311 + (1 + 1) = 13。

❌ Unsupported block (heading_4)

輸入：

0 100

輸出：

0

說明： - 顯示 00 時按下按鈕 A，顯示的整數依然是 00。

❌ Unsupported block (heading_4)

輸入：

99999 1000000000000000000

輸出：

84563

059 - 大量圖查詢 / Many Graph Queries（★7）

題目描述

給定一個具有 NN 個頂點與 MM 條邊的有向圖。在此圖中，邊 ii 從頂點 XiX_i 指向頂點 YiY_i。

請回答 QQ 個以下形式的查詢： - 查詢 jj：能否沿著有向邊的方向，從頂點 AjA_j 移動到頂點 BjB_j？

數據範圍

  • 2≤N≤1052 \leq N \leq 10^5
  • 1≤M≤1051 \leq M \leq 10^5
  • 1≤Q≤1051 \leq Q \leq 10^5
  • 1≤Xi<Yi≤N1 \leq X_i < Y_i \leq N
  • 1≤Aj<Bj≤N1 \leq A_j < B_j \leq N
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N M Q
X_1 Y_1
X_2 Y_2
⋮
X_M Y_M
A_1 B_1
A_2 B_2
⋮
A_Q B_Q

輸出格式

輸出共有 QQ 行。第 jj 行若能從頂點 AjA_j 移動到頂點 BjB_j 輸出 Yes，否則輸出 No。

範例測資

❌ Unsupported block (heading_4)

輸入：

6 6 3
1 3
2 4
1 4
4 6
5 6
1 5
2 6
1 5
3 6

輸出：

Yes
Yes
No

說明： 在第 1,21, 2 個查詢中，分別可以經由路徑 2→4→62 \rightarrow 4 \rightarrow 6 與 1→51 \rightarrow 5 進行移動。 在第 33 個查詢中，無法從頂點 33 移動到頂點 66。

❌ Unsupported block (heading_4)

輸入：

3 2 2
1 2
1 2
1 2
2 3

輸出：

Yes
No

說明： 圖中可能包含重邊（不一定是簡單圖）。

❌ Unsupported block (heading_4)

輸入：

2 1 1
1 2
1 2

輸出：

Yes

060 - 奇美拉 / Chimera（★5）

題目描述

給定一個長度為 NN 的數列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N)。 我們考慮 AA 的一個（不一定連續的）子序列 B=(B1,B2,…,BM)B = (B_1, B_2, \dots, B_M)，且滿足以下條件：

條件：存在一個整數 KK（1≤K≤M1 \leq K \leq M），使得以下兩個條件同時成立： - 對於所有滿足 1≤j<K1 \leq j < K 的 jj，皆成立 Bj<Bj+1B_j < B_{j+1}（前半部分嚴格單調遞增） - 對於所有滿足 K≤j<MK \leq j < M 的 jj，皆成立 Bj>Bj+1B_j > B_{j+1}（後半部分嚴格單調遞減）

請找出 BB 的長度（元素個數）MM 的最大可能值。

數據範圍

  • 1≤N≤3000001 \leq N \leq 300000
  • 1≤Ai≤N1 \leq A_i \leq N
  • 所有輸入值皆為整數

輸入格式

輸入以以下格式由標準輸入給出：

N
A_1 A_2 … A_N

輸出格式

輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

6
1 2 3 3 2 1

輸出：

5

說明： 從 A1,A2,A3,A5,A6A_1, A_2, A_3, A_5, A_6 得到子序列 B=(1,2,3,2,1)B = (1, 2, 3, 2, 1)。 若取 K=3K = 3，則 BB 滿足條件，其元素個數為 55。 不存在長度大於 55 且滿足條件的子序列，因此答案為 55。

❌ Unsupported block (heading_4)

輸入：

4
1 2 3 4

輸出：

4

❌ Unsupported block (heading_4)

輸入：

5
3 3 3 3 3

輸出：

1

061 - 牌堆 / Deck（★2）

題目描述

你為了整理卡牌，要建立一個牌堆。 最初，牌堆中沒有任何卡牌。

接下來將進行 QQ 次操作。第 ii 次操作 (1≤i≤Q)(1 \leq i \leq Q) 如下：

  • 當 ti=1t_i = 1 時：將寫有整數 xix_i 的卡牌放入牌堆的最上方。
  • 當 ti=2t_i = 2 時：將寫有整數 xix_i 的卡牌放入牌堆的最下方。
  • 當 ti=3t_i = 3 時：將牌堆從上方數來第 xix_i 張卡牌上所寫的整數寫在紙上。

請撰寫一個程式，依操作順序輸出所有 ti=3t_i = 3 的操作中所記錄的整數。

數據範圍

  • 2≤Q≤1052 \leq Q \leq 10^5
  • 1≤ti≤31 \leq t_i \leq 3
  • 當 ti=1,2t_i = 1, 2 時，1≤xi≤1091 \leq x_i \leq 10^9
  • 當 ti=3t_i = 3 時，1≤xi≤ki1 \leq x_i \leq k_i（kik_i 為滿足 1≤j≤i1 \leq j \leq i 且 tj=1,2t_j = 1, 2 的 jj 的個數）
  • 至少存在一個 ii 滿足 ti=1,2t_i = 1, 2
  • 至少存在一個 ii 滿足 ti=3t_i = 3
  • 所有輸入皆為整數

輸入格式

Q
t_1 x_1
t_2 x_2
:
t_Q x_Q

輸出格式

在給定的 QQ 次操作中，將所有 ti=3t_i = 3 操作所記錄的整數依序每行輸出一個。

範例測資

❌ Unsupported block (heading_4)

輸入：

6
1 2
1 1
2 3
3 1
3 2
3 3

輸出：

1
2
3

說明： 各次操作後牌堆的狀態如下：

  • 第 11 次操作後：卡牌上的整數由上至下依序為 (2)(2)
  • 第 22 次操作後：卡牌上的整數由上至下依序為 (1,2)(1, 2)
  • 第 33 次操作後：卡牌上的整數由上至下依序為 (1,2,3)(1, 2, 3)

因此，記錄下來的整數依序為 11、22、33。

❌ Unsupported block (heading_4)

輸入：

6
2 1
3 1
2 2
3 1
2 3
3 1

輸出：

1
1
1

說明： 僅進行將卡牌放入牌堆最下方的操作。 最初放入寫有 11 的卡牌，因此在 ti=3t_i = 3 時記錄下的數字始終為 11。

❌ Unsupported block (heading_4)

輸入：

6
1 1000000000
2 200000000
1 30000000
2 4000000
1 500000
3 3

輸出：

1000000000

062 - 全部塗黑 / Paint All（★6）

題目描述

有 NN 顆白色球與 NN 個道具。球與道具分別編號為 11 到 NN。 對於道具 ii，已知以下事項：

  • 當且僅當球 AiA_i 與球 BiB_i 中至少有一顆是白色時，才可以使用該道具。
  • 使用該道具後，可以將球 ii 塗成黑色。

請判定是否能藉由以適當的順序使用這 NN 個道具，將所有的球都塗成黑色。 若可行，請輸出其中一種使用道具的順序。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N
  • 所有輸入皆為整數

輸入格式

N
A_1 B_1
A_2 B_2
⋮
A_N B_N

輸出格式

若無法將所有的球都塗成黑色，請輸出 -1。 若可行，請依以下格式輸出：

X_1
X_2
⋮
X_N

其中 XiX_i 表示第 ii 個使用的道具編號。 這裡必須滿足 1≤Xi≤N1 \le X_i \le N、Xi≠Xj (i≠j)X_i \neq X_j\ (i \neq j) 且 XiX_i 皆為整數。

若存在多種可行的道具使用順序，輸出其中任意一種皆可。

範例測資

❌ Unsupported block (heading_4)

輸入：

4
3 4
1 3
2 3
2 1

輸出：

4
2
1
3

說明： 以下說明此輸出範例為正確解答：

  • 球 2 (=A4)2\ (=A_4) 與球 1 (=B4)1\ (=B_4) 均為白色，因此可以使用道具 44 將球 44 塗成黑色。
  • 球 1 (=A2)1\ (=A_2) 與球 3 (=B2)3\ (=B_2) 均為白色，因此可以使用道具 22 將球 22 塗成黑色。
  • 雖然球 4 (=B1)4\ (=B_1) 已是黑色，但球 3 (=A1)3\ (=A_1) 仍為白色，因此可以使用道具 11 將球 11 塗成黑色。
  • 雖然球 2 (=A3)2\ (=A_3) 已是黑色，但球 3 (=B3)3\ (=B_3) 仍為白色，因此可以使用道具 33 將球 33 塗成黑色。

如此一來，所有的球都被塗成了黑色。 請注意，即使操作後 Ai,BiA_i, B_i 都變成黑色，只要在操作前其中至少有一顆為白色即可。

此外，以 4,1,2,34, 1, 2, 3 的順序使用道具也是可行的。

❌ Unsupported block (heading_4)

輸入：

3
1 1
2 2
3 3

輸出：

3
2
1

說明： 以任意順序使用道具皆可。

另外請注意，本題中可能出現 Ai=BiA_i = B_i 的情況。

❌ Unsupported block (heading_4)

輸入：

5
3 4
4 5
1 1
5 1
3 2

輸出：

-1

說明： 無論如何都無法將所有的球塗成黑色。

❌ Unsupported block (heading_4)

輸入：

6
5 5
2 4
6 6
5 2
1 3
4 1

輸出：

1
5
3
6
4
2

說明： 此輸出為唯一的正確答案。

❌ Unsupported block (heading_4)

輸入：

10
5 1
3 9
7 8
9 3
3 7
10 10
3 5
4 7
1 1
6 6

輸出：

-1

063 - 單色子網格 / Monochromatic Subgrid（★4）

題目描述

給定一個高 HH 行、寬 WW 列的網格，由上數來第 ii 行、由左數來第 jj 列的格子記為 (i,j)(i, j)。格子 (i,j)(i, j) 上寫有整數 Pi,jP_{i, j}。

從此網格中選取（不一定需要連續的）11 個以上的行與 11 個以上的列所構成的「子網格」，若滿足以下條件，則稱為好的子網格。

條件：設選取的行為 i1,i2,…,iA (1≤i1<i2<⋯<iA≤H)i_1, i_2, \dots, i_A \ (1 \leq i_1 < i_2 < \dots < i_A \leq H)，選取的列為 j1,j2,…,jB (1≤j1<j2<⋯<jB≤W)j_1, j_2, \dots, j_B \ (1 \leq j_1 < j_2 < \dots < j_B \leq W)，則所有格子 (ia,jb) (1≤a≤A,1≤b≤B)(i_a, j_b) \ (1 \leq a \leq A, 1 \leq b \leq B) 上所寫的整數皆相同。

請計算好的子網格之大小可能的最大值。 其中，由 AA 個行與 BB 個列組成的子網格之大小定義為 A×BA \times B。

數據範圍

  • 1≤H≤81 \leq H \leq 8
  • 1≤W≤100001 \leq W \leq 10000
  • 1≤Pi,j≤HW1 \leq P_{i, j} \leq HW
  • 所有輸入皆為整數

輸入格式

H W
P_{1, 1} P_{1, 2} … P_{1, W}
P_{2, 1} P_{2, 2} … P_{2, W}
⋮
P_{H, 1} P_{H, 2} … P_{H, W}

輸出格式

輸出好的子網格之大小可能的最大值。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 6
1 1 1 1 1 2
1 2 2 2 2 2
1 2 2 3 2 3
1 2 3 2 2 3

輸出：

6

說明： 選取第 {2,3}\{2, 3\} 行與第 {2,3,5}\{2, 3, 5\} 列所構成的大小為 66 的子網格，如下所示，其所有格子上的數字均為 22：

. . . . . .
. 2 2 . 2 .
. 2 2 . 2 .
. . . . . .

因此，該子網格為好的子網格。由於不存在更大的好的子網格，故輸出 66。

❌ Unsupported block (heading_4)

輸入：

3 3
1 2 3
4 5 6
7 8 9

輸出：

1

❌ Unsupported block (heading_4)

輸入：

5 3
7 7 7
7 7 7
7 7 7
7 7 7
7 7 7

輸出：

15

064 - 地盤隆起 / Uplift（★3）

題目描述

某地被劃分為 NN 個區塊，由西向東數來第 ii 個區塊（以下稱為區塊 ii）的海拔高度為 AiA_i。

接下來會發生 QQ 次地殼變動。在第 ii 次地殼變動中，區塊 Li,Li+1,⋯ ,RiL_i, L_i+1, \cdots, R_i 的海拔高度會變化 ViV_i。（當 Vi≥0V_i \geq 0 時表示海拔上升 ∣Vi∣|V_i|；當 Vi<0V_i < 0 時表示海拔下降 ∣Vi∣|V_i|）

從區塊 11 前往區塊 NN 的不便程度定義如下：

設區塊 ii 的海拔高度為 EiE_i，則不便程度為 ∣E1−E2∣+∣E2−E3∣+⋯+∣EN−1−EN∣|E_1 - E_2| + |E_2 - E_3| + \cdots + |E_{N-1} - E_N|。

請計算每次地殼變動後的不便程度。

數據範圍

  • 1≤N,Q≤1051 \leq N, Q \leq 10^{5}
  • −109≤Ai,Vi≤109-10^{9} \leq A_i, V_i \leq 10^{9}
  • 1≤Li≤Ri≤N1 \leq L_i \leq R_i \leq N
  • 所有輸入皆為整數

輸入格式

N Q
A_1 A_2 … A_N
L_1 R_1 V_1
L_2 R_2 V_2
⋮
L_Q R_Q V_Q

輸出格式

輸出 QQ 行。第 ii 行輸出第 ii 次地殼變動結束後的不便程度。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 3
1 2 3
2 3 1
1 2 -1
1 3 2

輸出：

3
4
4

說明： - 第 11 次地殼變動後，各區塊由西向東的海拔依序為 1,3,41, 3, 4，不便程度為 ∣1−3∣+∣3−4∣=3|1 - 3| + |3 - 4| = 3。 - 第 22 次地殼變動後，各區塊由西向東的海拔依序為 0,2,40, 2, 4，不便程度為 ∣0−2∣+∣2−4∣=4|0 - 2| + |2 - 4| = 4。 - 第 33 次地殼變動後，各區塊由西向東的海拔依序為 2,4,62, 4, 6，不便程度為 ∣2−4∣+∣4−6∣=4|2 - 4| + |4 - 6| = 4。

❌ Unsupported block (heading_4)

輸入：

20 10
61 51 92 -100 -89 -65 -89 -64 -74 7 87 -2 51 -39 -50 63 -23 36 74 37
2 2 -45
6 19 82
2 9 36
7 13 71
16 20 90
18 20 -24
14 17 -78
10 11 -55
7 19 -26
20 20 -7

輸出：

1164
1328
1256
1350
1440
1416
1572
1482
1430
1437

065 - RGB 彩球 2 / RGB Balls 2（★7）

題目描述

有 RR 顆紅色球、GG 顆綠色球與 BB 顆藍色球。即使顏色相同，每顆球之間都是彼此可區分的。

現在要從這 R+G+BR+G+B 顆球中選出 KK 顆球，且必須同時滿足以下所有條件：

  • 選出的紅色球與綠色球總數不超過 XX 顆
  • 選出的綠色球與藍色球總數不超過 YY 顆
  • 選出的藍色球與紅色球總數不超過 ZZ 顆

問共有多少種選出 KK 顆球的方法？由於答案可能非常大，請輸出答案除以 998244353998244353 的餘數。

數據範圍

  • 1≤R,G,B≤2000001 \leq R, G, B \leq 200000
  • 1≤K≤min⁡(200000,R+G+B)1 \leq K \leq \min(200000, R+G+B)
  • 0≤X≤min⁡(K,R+G)0 \leq X \leq \min(K, R+G)
  • 0≤Y≤min⁡(K,G+B)0 \leq Y \leq \min(K, G+B)
  • 0≤Z≤min⁡(K,B+R)0 \leq Z \leq \min(K, B+R)
  • 所有輸入皆為整數

輸入格式

R G B K
X Y Z

輸出格式

輸出答案除以 998244353998244353 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 1 2 5
4 2 4

輸出：

2

說明： 此範例測資滿足子任務 1,2,31, 2, 3 的限制。

從 22 顆藍色球中恰好不選其中 11 顆，其餘球全部選取，即可達成條件。由於不存在其他滿足條件的選法，因此答案為 22 種。

❌ Unsupported block (heading_4)

輸入：

65 6 12 35
30 18 35

輸出：

257190020

說明： 此範例測資滿足子任務 2,32, 3 的限制。

請注意輸出答案除以 998244353998244353 的餘數。

❌ Unsupported block (heading_4)

輸入：

23502 65936 72385 95835
72759 85735 72385

輸出：

229429276

說明： 此範例測資滿足子任務 33 的限制。

066 - 多樣數列 / Various Arrays（★5）

題目描述

數列店的高橋君正在製作一個長度為 NN 的數列 aa。數列 aa 的第 ii 個元素 aia_i 的值，是從 LiL_i 以上、RiR_i 以下的整數中獨立且均勻隨機選取的。

請計算如此生成的數列 aa 的逆序數（轉倒數）的期望值。

長度為 mm 的數列 xx 的「逆序數」是指滿足 i<ji < j 且 xi>xjx_i > x_j 的數對 (i,j)(i, j) (1≤i,j≤m)(1 \leq i, j \leq m) 的個數。

數據範圍

  • 1≤N≤1001 \leq N \leq 100
  • 1≤Li≤Ri≤1001 \leq L_i \leq R_i \leq 100 (1≤i≤N)(1 \leq i \leq N)
  • 所有輸入皆為整數

輸入格式

N
L_1 R_1
⋮
L_N R_N

輸出格式

輸出答案。若輸出與標準答案的相對誤差或絕對誤差在 10−710^{-7} 以下，則視為正確。

範例測資

❌ Unsupported block (heading_4)

輸入：

2
1 2
1 2

輸出：

0.250000000000

說明： 數列 aa 可能的情況有以下 44 種：

  • a=(1,1)a = (1, 1)，逆序數為 00
  • a=(1,2)a = (1, 2)，逆序數為 00
  • a=(2,1)a = (2, 1)，逆序數為 11
  • a=(2,2)a = (2, 2)，逆序數為 00

因此，期望值為 14=0.25\frac{1}{4} = 0.25。

❌ Unsupported block (heading_4)

輸入：

3
3 3
1 1
4 4

輸出：

1.000000000000

說明： 數列 aa 唯一可能的情況為 a=(3,1,4)a = (3, 1, 4)，該數列的逆序數為 11。

❌ Unsupported block (heading_4)

輸入：

10
1 10
38 40
8 87
2 9
75 100
45 50
89 92
27 77
23 88
62 81

輸出：

13.696758921226

067 - 八進位轉九進位 / Base 8 to 9（★2）

題目描述

黑板上寫著一個以 88 進位表示的整數 NN。你將進行以下操作 KK 次：

  • 將黑板上的整數轉為 99 進位表示，並將其中出現的數字「88」改寫為「55」（改寫後的數被視為以 88 進位表示的整數）。

請輸出進行 KK 次操作後得到的數（以 88 進位表示）。

數據範圍

  • 0≤N<8200 \leq N \lt 8^{20}
  • 1≤K≤1001 \leq K \leq 100
  • NN 是以 88 進位表示的整數
  • NN 的開頭不包含多餘的前導 00
  • KK 為整數

輸入格式

N K

輸出格式

輸出進行 KK 次操作後得到的數（以 88 進位表示）。 此時，答案整數的開頭請勿包含多餘的前導 00。

範例測資

❌ Unsupported block (heading_4)

輸入：

21 1

輸出：

15

說明： 以 88 進位表示的整數 2121（十進位的 1717），轉換為 99 進位表示為 1818。 將其中的數字 88 改寫為 55 後得到 1515。

❌ Unsupported block (heading_4)

輸入：

1330 1

輸出：

555

說明： 以 88 進位表示的整數 13301330（十進位的 728728），轉換為 99 進位表示為 888888。 將其中的數字 88 改寫為 55 後得到 555555。

❌ Unsupported block (heading_4)

輸入：

2311640221315 15

輸出：

474547

068 - 相鄰成對資訊 / Paired Information（★5）

題目描述

有一個長度為 NN 的整數數列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)。 一開始，你對這個整數數列一無所知。

給定 QQ 個關於數列 AA 的資訊與詢問（統稱為事件）。從頭數來第 ii 個事件 (1≤i≤Q)(1 \leq i \leq Q) 由四個整數組成的四元組 (Ti,Xi,Yi,Vi)(T_i, X_i, Y_i, V_i) 表示，具體含義如下：

  • 當 Ti=0T_i = 0 時：表示給出資訊 AXi+AYi=ViA_{X_i} + A_{Y_i} = V_i。此處保證 Xi+1=YiX_i+1=Y_i。
  • 當 Ti=1T_i = 1 時：表示進行詢問「若假設 AXi=ViA_{X_i} = V_i，則 AYiA_{Y_i} 的值為何？」。 更嚴格地說，這表示詢問：在所有滿足 AXi=ViA_{X_i}=V_i 且同時滿足此時之前所有給出的資訊 AXj+AYj=Vj (1≤j<i,Tj=0)A_{X_j} + A_{Y_j} = V_j \ (1 \leq j \lt i, T_j = 0) 的長度為 NN 的整數數列 AA 中，AYiA_{Y_i} 的值為何？

請依序處理事件並回答各個詢問。 若在進行該詢問時，答案 AYiA_{Y_i} 無法唯一確定，請改為輸出 Ambiguous。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤Q≤1051 \leq Q \leq 10^5
  • Ti=0T_i = 0 或 Ti=1 (1≤i≤Q)T_i = 1\ (1 \leq i \leq Q)
  • 1≤Xi,Yi≤N (1≤i≤Q)1 \leq X_i, Y_i \leq N\ (1 \leq i \leq Q)
  • 若 Ti=0T_i = 0，則 Xi+1=Yi (1≤i≤Q)X_i + 1 = Y_i\ (1 \leq i \leq Q)
  • 0≤Vi≤2×109 (1≤i≤Q)0 \leq V_i \leq 2 \times 10^9\ (1 \leq i \leq Q)
  • 不會給出存在矛盾的輸入。 也就是說，對於 i=1,2,…,Qi = 1, 2, \ldots, Q：若 Ti=0T_i = 0，則存在長度為 NN 的整數數列 AA 滿足所有 1≤j≤i,Tj=01 \leq j \leq i, T_j = 0 的 AXj+AYj=VjA_{X_j} + A_{Y_j} = V_j；若 Ti=1T_i = 1，則存在長度為 NN 的整數數列 AA 同時滿足 AXi=ViA_{X_i} = V_i 與所有 1≤j<i,Tj=01 \leq j \lt i, T_j = 0 的 AXj+AYj=VjA_{X_j} + A_{Y_j} = V_j。
  • 所有輸入皆為整數

輸入格式

N
Q
T_1 X_1 Y_1 V_1
T_2 X_2 Y_2 V_2
⋮
T_Q X_Q Y_Q V_Q

輸出格式

依序輸出各個詢問的答案。 若在該詢問當下答案無法唯一確定，請輸出 Ambiguous。

範例測資

❌ Unsupported block (heading_4)

輸入：

4
7
0 1 2 3
1 1 2 1
1 3 4 5
0 3 4 6
1 3 4 5
0 2 3 6
1 3 1 5

輸出：

2
Ambiguous
1
2

說明： 各次詢問的答案如下：

  • 第 11 次詢問（i=2i=2）：滿足 A1=1A_1=1 與 A1+A2=3A_1+A_2=3 的數列 AA 皆滿足 A2=2A_2=2，因此輸出為 22。
  • 第 22 次詢問（i=3i=3）：滿足 A3=5A_3=5 與 A1+A2=3A_1+A_2=3 的數列 AA 可以是 (A1,A2,A3,A4)=(1,2,5,10)(A_1,A_2,A_3,A_4)=(1,2,5,10) 或 (A1,A2,A3,A4)=(3,0,5,0)(A_1,A_2,A_3,A_4)=(3,0,5,0) 等，A4A_4 的值無法唯一確定，因此輸出 Ambiguous。
  • 第 33 次詢問（i=5i=5）：滿足 A3=5A_3=5 且 A1+A2=3,A3+A4=6A_1+A_2=3, A_3+A_4=6 的數列 AA 皆滿足 A4=1A_4=1，因此輸出為 11。
  • 第 44 次詢問（i=7i=7）：滿足 A3=5A_3=5 且 A1+A2=3,A3+A4=6,A2+A3=6A_1+A_2=3, A_3+A_4=6, A_2+A_3=6 的數列 AA 皆滿足 A1=2A_1=2，因此輸出為 22。

❌ Unsupported block (heading_4)

輸入：

15
25
0 11 12 41
0 1 2 159
0 14 15 121
0 4 5 245
0 12 13 157
0 9 10 176
0 6 7 170
0 2 3 123
0 7 8 167
0 3 4 159
1 12 11 33
0 10 11 116
0 8 9 161
1 9 12 68
1 12 12 33
1 7 12 74
0 5 6 290
1 8 9 93
0 13 14 127
1 10 12 108
1 14 1 3
1 13 8 124
1 12 11 33
1 12 10 33
1 5 15 194

輸出：

8
33
33
33
68
33
144
93
8
108
118

069 - 彩色積木 2 / Colorful Blocks 2（★3）

題目描述

有 NN 個積木排成一列，由左至右依序編號為 11 到 NN。

現在考慮用 KK 種顏色中的某一種顏色為每個積木塗色。塗色時必須滿足以下條件：

  • 若 1≤∣i−j∣≤21 \leq |i-j| \leq 2，則積木 ii 與積木 jj 塗上的顏色必須不同。
  • 可以有某些顏色完全沒有被使用。

請計算滿足條件的積木塗色方法共有多少種，並輸出其除以 109+710^9 + 7 的餘數。兩種塗色方式不同，定義為存在至少一個整數 i (1≤i≤N)i\ (1 \leq i \leq N)，使得積木 ii 所塗的顏色不同。

數據範圍

  • 1≤N≤10181 \leq N \leq 10^{18}
  • 1≤K≤1091 \leq K \leq 10^9
  • 所有輸入皆為整數

輸入格式

N K

輸出格式

輸出滿足條件的塗色方法數除以 109+710^9+7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

2 3

輸出：

6

說明： 為了滿足條件，這 22 個積木必須塗上彼此不同的顏色。由於 K=3K=3，滿足條件的塗色方法共有 66 種。

❌ Unsupported block (heading_4)

輸入：

10 2

輸出：

0

說明： 僅用 22 種顏色無法將 1010 個積木塗成滿足條件的狀態。

❌ Unsupported block (heading_4)

輸入：

2021 617

輸出：

53731843

說明： 請注意輸出答案除以 109+710^9+7 的餘數。

070 - 發電廠選址 / Plant Planning（★4）

題目描述

在二維平面上有 NN 座工廠，第 ii 座工廠位於座標 (Xi,Yi)(X_i, Y_i)。

現在你可以在二維平面上的任意位置選擇一處建造一座發電廠。

定義發電廠的「不便程度」為發電廠到各工廠的曼哈頓距離總和。請計算不便程度的最小可能值。在本題限制下，可以證明答案必為整數。

關於曼哈頓距離

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • −109≤Xi,Yi≤109-10^9 \leq X_i, Y_i \leq 10^9
  • 所有輸入皆為整數

輸入格式

N
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N

輸出格式

輸出不便程度的最小值（整數）。

範例測資

❌ Unsupported block (heading_4)

輸入：

2
-1 2
1 1

輸出：

3

說明： 若將發電廠建在 (0,1)(0, 1)，則發電廠到各工廠的曼哈頓距離如下：

  • 工廠 11：∣−1−0∣+∣2−1∣=2|-1 - 0| + |2 - 1| = 2
  • 工廠 22：∣1−0∣+∣1−1∣=1|1 - 0| + |1 - 1| = 1

此時的不便程度為 2+1=32 + 1 = 3。由於不便程度不可能小於 33，因此輸出 33。

❌ Unsupported block (heading_4)

輸入：

2
1 0
0 1

輸出：

2

說明： 若將發電廠建在 (1,0)(1, 0)，可達成最小不便程度 22。

此外，若將發電廠建在 (0.5,0.5)(0.5, 0.5) 或 (0,1)(0, 1)，不便程度同樣為 22。

❌ Unsupported block (heading_4)

輸入：

5
2 5
2 5
-3 4
-4 -8
6 -2

輸出：

35

說明： 多個工廠可能位於相同的座標上。

❌ Unsupported block (heading_4)

輸入：

4
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000

輸出：

8000000000

071 - 模糊優先級 / Fuzzy Priority（★7）

題目描述

請找出 KK 個滿足以下條件的 (1,2,3,⋯ ,N)(1,2,3, \cdots ,N) 排列 P=(P1,P2,P3,⋯ ,PN)P = (P_1,P_2,P_3, \cdots ,P_N)。若不存在 KK 個這樣的排列，請報告此情況。

  • 對於每個 i=1,2,3,⋯ ,Mi=1,2,3, \cdots ,M，在排列 PP 中 AiA_i 都出現在 BiB_i 之前。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 0≤M≤1050 \leq M \leq 10^5
  • 1≤K≤101 \leq K \leq 10
  • 1≤Ai≤N1 \leq A_i \leq N
  • 1≤Bi≤N1 \leq B_i \leq N
  • Ai≠BiA_i \neq B_i
  • 若 i≠ji \neq j，則 (Ai,Bi)≠(Aj,Bj)(A_i,B_i) \neq (A_j,B_j)
  • 輸入皆為整數

輸入格式

N M K
A_1 B_1
A_2 B_2
⋮
A_M B_M

輸出格式

若滿足條件的排列 PP 不足 KK 個，請輸出 -1。

若存在，輸出應包含 KK 行。每行請依以下格式輸出一個滿足條件的排列 PP：

P_1 P_2 P_3 … P_N

這 KK 個排列必須互不相同。

範例測資

❌ Unsupported block (heading_4)

輸入：

5 2 3
1 2
3 4

輸出：

1 2 3 4 5
1 3 2 4 5
1 3 5 2 4

說明： 此範例測資滿足部分子任務限制。

排列 PP 的條件為： - 11 在 22 之前 - 33 在 44 之前

必須同時滿足這 22 個條件。

只要是滿足此條件且互不相同的 KK 個排列，即使輸出與範例輸出不同亦視為正確。此外，輸出這 KK 個排列的順序不同亦視為正確。

❌ Unsupported block (heading_4)

輸入：

5 2 1
1 3
3 1

輸出：

-1

說明： 此範例測資滿足所有子任務限制。

不存在任何滿足條件的排列。

❌ Unsupported block (heading_4)

輸入：

10 15 10
8 4
9 4
10 2
6 2
10 6
1 3
7 4
6 8
8 1
5 6
10 9
3 7
8 3
3 9
2 3

輸出：

5 10 6 2 8 1 3 7 9 4
5 10 6 2 8 1 3 9 7 4
5 10 6 8 2 1 3 7 9 4
5 10 6 8 2 1 3 9 7 4
5 10 6 8 1 2 3 7 9 4
5 10 6 8 1 2 3 9 7 4
10 5 6 2 8 1 3 7 9 4
10 5 6 2 8 1 3 9 7 4
10 5 6 8 2 1 3 7 9 4
10 5 6 8 2 1 3 9 7 4

說明： 此範例測資滿足部分子任務限制。

072 - 環狀鐵路計畫 / Loop Railway Plan（★4）

題目描述

ABC 王國以 HH 行 WW 列的網格表示。每個方格不是山方格就是平原方格。由上數來第 ii 行、由左數來第 jj 列的方格若為山方格，則 ci,jc_{i,j} 為 #；若為平原方格，則 ci,jc_{i,j} 為 .。

你想要建造一條鐵路路線。鐵路路線的路徑必須同時滿足以下所有條件：

  • 條件 1：以某個方格為起點，重複移動到共享邊的相鄰方格 kk 次（3≤k3 \le k），並回到起點。
  • 條件 2：在 kk 次移動中，所到達的方格皆不相同。（起點與終點可以重合）
  • 條件 3：不經過任何山方格。

請計算鐵路路線所經過方格數量的最大可能值。若不存在滿足條件的鐵路路線，請報告此情況（輸出 -1）。

數據範圍

  • H,WH, W 為正整數
  • H×W≤16H \times W \leq 16
  • ci,jc_{i,j} 為 # 或 .
  • 至少存在一個 i,ji,j（1≤i≤H,1≤j≤W1 \leq i \leq H, 1 \leq j \leq W）使得 ci,jc_{i,j} 為 .

輸入格式

H W
c_{1,1} c_{1,2} … c_{1,W}
c_{2,1} c_{2,2} … c_{2,W}
⋮
c_{H,1} c_{H,2} … c_{H,W}

輸出格式

請輸出鐵路路線所經過方格數量的最大值。

若不存在滿足條件的鐵路路線，請輸出 -1。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 3
...
.#.
...

輸出：

8

說明： 例如，繞外圍一圈的鐵路路線會經過 88 個方格。

❌ Unsupported block (heading_4)

輸入：

1 6
......

輸出：

-1

說明： 由於不存在滿足條件的鐵路路線，故輸出 -1。

❌ Unsupported block (heading_4)

輸入：

4 4
....
#...
....
...#

輸出：

12

說明： 例如，存在一條經過 1212 個方格的鐵路路線。

073 - 我們需要 a 與 b / We Need Both a and b（★5）

題目描述

給定一棵包含 NN 個頂點的樹。樹的頂點編號為 1,2,⋯ ,N1, 2, \cdots, N，第 ii 條邊雙向連接頂點 aia_i 與頂點 bib_i。

每個頂點上都寫有文字 a 或 b，頂點 ii 上寫的文字為 cic_i。

刪除 00 條或更多條邊的方法共有 2N−12^{N-1} 種。在這些方法中，求滿足「刪除邊之後，所有的連通分量都同時包含文字 a 與 b」的方法數，並輸出其除以 109+710^9+7 的餘數。

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • cic_i 為 a 或 b
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 給定的圖為一棵樹

輸入格式

N
c_1 c_2 … c_N
a_1 b_1
⋮
a_{N - 1} b_{N - 1}

輸出格式

請輸出一行，表示答案除以 109+710^9+7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

7
b a b a b b a
2 1
3 7
3 2
3 4
5 4
4 6

輸出：

4

說明： 滿足條件的刪邊方法有以下 44 種： - 不刪除任何邊 - 刪除邊 (3,2)(3, 2) - 刪除邊 (3,4)(3, 4) - 刪除邊 (3,2)(3, 2) 與邊 (3,4)(3, 4)

❌ Unsupported block (heading_4)

輸入：

2
a b
1 2

輸出：

1

說明： 無法刪除任何邊。

❌ Unsupported block (heading_4)

輸入：

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

輸出：

16

074 - ABC 字串 2 / ABC String 2（★6）

題目描述

現在電子看板上顯示著一個由 a、b、c 組成且長度為 NN 的字串 SS。

你可以依任意順序執行以下 22 種操作任意多次。其中「變換」是指將原本為 a 的字元變為 b，b 變為 c，c 變為 a：

  • 選擇一個滿足 Si=‘b‘S_i = \text{`b`} 的索引 ii（1≤i≤N1 \leq i \leq N），將 SiS_i 改為 a 之後，將 S1,S2,⋯ ,Si−1S_1, S_2, \cdots, S_{i-1} 進行變換。
  • 選擇一個滿足 Si=‘c‘S_i = \text{`c`} 的索引 ii（1≤i≤N1 \leq i \leq N），將 SiS_i 改為 b 之後，將 S1,S2,⋯ ,Si−1S_1, S_2, \cdots, S_{i-1} 進行變換。

請計算最多可以執行多少次操作。

數據範圍

  • 1≤N≤601 \leq N \leq 60
  • SS 是由 a、b、c 組成且長度為 NN 的字串

輸入格式

N
S

輸出格式

請輸出最多可以執行的操作次數。

範例測資

❌ Unsupported block (heading_4)

輸入：

3
aba

輸出：

2

說明： 例如透過以下步驟，可以執行 22 次操作： - 首先選擇 i=2i = 2 執行操作。此時字串 SS 由 aba 變為 baa。 - 接著選擇 i=1i = 1 執行操作。此時字串 SS 由 baa 變為 aaa。

❌ Unsupported block (heading_4)

輸入：

10
aaaaaaaaaa

輸出：

0

說明： 由於所有字元皆為 a，因此無法進行任何操作。

❌ Unsupported block (heading_4)

輸入：

5
baaca

輸出：

17

075 - 球與魔法 / Magic For Balls（★3）

題目描述

對寫有整數 xx 的球進行敲擊時，會進行以下操作：

  • 若 xx 不是質數：被敲擊的球消失，並新增一顆寫有整數 aa 的球與一顆寫有整數 bb 的球。其中 a,ba, b 可以自由選擇滿足 ab=xab = x 且 a≥2,b≥2a \geq 2, b \geq 2 的整數。
  • 若 xx 是質數：什麼事都不會發生。

此外，施展 11 次魔法可以同時敲擊當前所有的球。另一方面，除了施展魔法以外，沒有其他敲擊球的方法。

現在只有 11 顆寫有整數 NN 的球。你想透過施展幾次魔法，使得所有球上寫的數字都變成質數。最少需要施展幾次魔法？

數據範圍

  • 2≤N≤10122 \leq N \leq 10^{12}
  • NN 為整數

輸入格式

N

輸出格式

請輸出最少需要施展魔法的次數。

範例測資

❌ Unsupported block (heading_4)

輸入：

42

輸出：

2

說明： 一開始有一顆寫有 4242 的球。使用魔法敲擊此球，例如可以進行以下操作： - 讓寫有 4242 的球消失，並新增寫有 77 的球與寫有 66 的球。

現在有兩顆球，分別寫有 6,76, 7。使用魔法敲擊這些球，會進行以下操作： - 敲擊寫有 77 的球什麼都不會發生。 - 讓寫有 66 的球消失，並新增寫有 22 的球與寫有 33 的球。

現在有三顆球，分別寫有 2,3,72, 3, 7。因為這些數字都是質數，所以透過 22 次魔法即可達成目標。無法在少於 22 次的情況下達成目標。

❌ Unsupported block (heading_4)

輸入：

48

輸出：

3

說明： 例如進行適當的分解操作，可以在 33 次魔法後使所有球上的數字皆為質數。

❌ Unsupported block (heading_4)

輸入：

54

輸出：

2

❌ Unsupported block (heading_4)

輸入：

53

輸出：

0

說明： 一開始就是質數的情況下，無需施展魔法即已滿足條件，因此請輸出 00。

076 - 切蛋糕 / Cake Cut（★3）

題目描述

有一個被分成 NN 塊的圓形完整蛋糕，依順時針方向第 ii 塊蛋糕（以下稱為塊 ii）的大小為 AiA_i。對於 1≤i≤N−11 \leq i \leq N-1，塊 ii 與塊 i+1i+1 相鄰，且塊 NN 與塊 11 也相鄰。

請判定是否存在一種選取蛋糕中連續幾塊的方法，使得選取部分的大小恰好為蛋糕總大小的 110\frac{1}{10}（十分之一）。

數據範圍

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 輸入皆為整數

輸入格式

N
A_1 A_2 … A_N

輸出格式

若存在一種選取方式使得選取部分的大小恰好為總大小的 110\frac{1}{10}，請輸出 Yes；否則輸出 No。

範例測資

❌ Unsupported block (heading_4)

輸入：

10
1 1 1 1 1 1 1 1 1 1

輸出：

Yes

說明： 蛋糕總大小為 1010，因此需要選取連續的蛋糕塊使得大小總和為 11。 例如只選取塊 11 即可。

❌ Unsupported block (heading_4)

輸入：

3
1 1 1

輸出：

No

說明： 不存在任何選法使得選取部分的大小為總大小的 110\frac{1}{10}。

❌ Unsupported block (heading_4)

輸入：

3
1 18 1

輸出：

Yes

說明： 選取塊 11 與塊 33，選取部分的大小總和為 22，恰好是總大小 2020 的 110\frac{1}{10}。 請注意塊 11 與塊 NN 是相鄰的。

❌ Unsupported block (heading_4)

輸入：

4
1 9 1 9

輸出：

No

說明： 雖然選取塊 11 與塊 33 大小總和為 22（總大小為 2020 的 110\frac{1}{10}），但它們並不連續，不能以不連續的方式選取。

077 - 平面上的飛機 / Planes on a 2D Plane（★7）

題目描述

在可視為 22 維座標平面的天空中，有 NN 架飛機正在飛行。 對於 i=1,2,⋯ ,Ni=1,2, \cdots ,N，第 ii 架飛機在時刻 00 位於座標 (AXi,AYi)(AX_i,AY_i)。

每架飛機都朝向方向 1,2,3,4,5,6,7,81,2,3,4,5,6,7,8 之一飛行。 在時刻 tt 位於座標 (x,y)(x,y) 且朝向方向 dd 的飛機，在時刻 t+1t+1 將位於：

  • 若 d=1d=1，位於座標 (x+1,y)(x+1,y)
  • 若 d=2d=2，位於座標 (x+1,y+1)(x+1,y+1)
  • 若 d=3d=3，位於座標 (x,y+1)(x,y+1)
  • 若 d=4d=4，位於座標 (x−1,y+1)(x-1,y+1)
  • 若 d=5d=5，位於座標 (x−1,y)(x-1,y)
  • 若 d=6d=6，位於座標 (x−1,y−1)(x-1,y-1)
  • 若 d=7d=7，位於座標 (x,y−1)(x,y-1)
  • 若 d=8d=8，位於座標 (x+1,y−1)(x+1,y-1)

此外，在飛行過程中飛機不會改變方向。

你收到了管制員高橋同學的以下報告：

「在時刻 TT，座標 (BX1,BY1),(BX2,BY2),⋯ ,(BXN,BYN)(BX_1,BY_1),(BX_2,BY_2), \cdots ,(BX_N,BY_N) 處各有一架飛機。」

請判定是否存在與他的報告不矛盾的 NN 架飛機飛行方向組合；若存在，請輸出一組可行的方向配置。

數據範圍

  • 1≤N≤200001 \leq N \leq 20000
  • 1≤T≤1091 \leq T \leq 10^9
  • 0≤AXi,AYi,BXi,BYi≤1090 \leq AX_i,AY_i,BX_i,BY_i \leq 10^9
  • 若 i≠ji \ne j，則 (AXi,AYi)≠(AXj,AYj)(AX_i,AY_i) \ne (AX_j,AY_j)
  • 若 i≠ji \ne j，則 (BXi,BYi)≠(BXj,BYj)(BX_i,BY_i) \ne (BX_j,BY_j)
  • 輸入皆為整數

輸入格式

N T
AX_1 AY_1
AX_2 AY_2
 ⋮
AX_N AY_N
BX_1 BY_1
BX_2 BY_2
 ⋮
BX_N BY_N

輸出格式

若不存在與高橋同學的報告不矛盾的方向組合，請輸出 No。

若存在，請依以下格式輸出第 1,2,⋯ ,N1, 2, \cdots, N 架飛機的方向（以空格分隔）：

Yes
D_1 D_2 D_3 … D_N

其中 DiD_i 為飛機 ii 的飛行方向。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 2
3 3
5 5
9 2
11 2
5 5
3 3

輸出：

Yes
2 6 1

說明： 在時刻 TT 時，第 11 架飛機位於座標 (BX2,BY2)(BX_2,BY_2)，第 22 架飛機位於座標 (BX3,BY3)(BX_3,BY_3)，第 33 架飛機位於座標 (BX1,BY1)(BX_1,BY_1)。

❌ Unsupported block (heading_4)

輸入：

3 2
3 3
5 5
9 2
11 1000000000
5 5
3 3

輸出：

No

說明： 不存在與高橋同學的報告不矛盾的方向組合。

❌ Unsupported block (heading_4)

輸入：

20 774
540130346 269080121
139837096 165633078
731188937 784167460
18996195 52176517
153153670 738204723
179733158 825294112
698198250 713974773
449248931 563096572
249863070 242694893
428066819 476630383
554127636 460973490
389988495 32320086
889782910 956212985
43905938 212030305
638141790 667879166
985957895 358743012
971007109 827787244
804625543 141347414
905270323 167192824
614855582 963943648
179733932 825294886
731188163 784166686
153154444 738205497
554128410 460973490
804626317 141348188
449249705 563096572
540129572 269079347
638142564 667878392
614855582 963944422
18996969 52177291
971007109 827788018
889782910 956213759
43906712 212031079
389987721 32319312
139836322 165633078
428067593 476631157
905271097 167192824
249862296 242694893
985958669 358742238
698199024 713975547

輸出：

Yes
6 5 6 2 2 2 2 1 5 2 1 6 3 2 8 8 3 2 1 3

078 - 簡易圖論問題 / Easy Graph Problem（★2）

題目描述

給定一個包含 NN 個頂點與 MM 條邊的連通簡單無向圖。圖中的頂點編號分別為 11 到 NN。 第 ii 條邊雙向連接頂點 aia_i 與 bib_i。

請輸出滿足以下條件的頂點數量：

  • 恰好存在 11 個編號比自己小的相鄰頂點。

數據範圍

  • 2≤N≤1000002 \leq N \leq 100000
  • N−1≤M≤min⁡(N(N−1)2,100000)N - 1 \leq M \leq \min(\frac{N(N - 1)}{2}, 100000)
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 給定的圖為簡單圖
  • 給定的圖為連通圖
  • 所有輸入皆為整數

輸入格式

N M
a_1 b_1
⋮
a_{M} b_{M}

輸出格式

請輸出一行，表示滿足條件的頂點數量。

範例測資

❌ Unsupported block (heading_4)

輸入：

5 5
1 2
1 3
3 2
5 2
4 2

輸出：

3

說明： 滿足條件的頂點有 22、44、55 共 33 個： - 頂點 22 只有頂點 11 這 11 個比自己編號小的相鄰頂點。 - 頂點 44 只有頂點 22 這 11 個比自己編號小的相鄰頂點。 - 頂點 55 只有頂點 22 這 11 個比自己編號小的相鄰頂點。

❌ Unsupported block (heading_4)

輸入：

2 1
1 2

輸出：

1

說明： 滿足條件的頂點僅有 22。

❌ Unsupported block (heading_4)

輸入：

7 18
7 2
1 6
5 2
1 3
7 6
5 3
5 6
5 4
1 7
2 6
3 4
5 1
4 7
4 6
5 7
3 2
4 2
1 4

輸出：

0

079 - 2x2 操作 / Two by Two（★3）

題目描述

給定一個 H×WH \times W 的 22 維陣列 AA 與 BB。你可以依任意順序執行以下 22 種操作任意多次：

  • 選擇整數 x,yx, y（1≤x<H,1≤y<W1 \leq x \lt H, 1 \leq y \lt W），將 Ax,y,Ax+1,y,Ax,y+1,Ax+1,y+1A_{x, y}, A_{x+1, y}, A_{x, y+1}, A_{x+1, y+1} 的值各自增加 11。
  • 選擇整數 x,yx, y（1≤x<H,1≤y<W1 \leq x \lt H, 1 \leq y \lt W），將 Ax,y,Ax+1,y,Ax,y+1,Ax+1,y+1A_{x, y}, A_{x+1, y}, A_{x, y+1}, A_{x+1, y+1} 的值各自減少 11。

請問是否可能透過執行 00 次或多次操作，使 AA 與 BB 完全一致？ 若可能，請同時輸出最少的操作次數。

數據範圍

  • 2≤H,W≤1002 \leq H, W \leq 100
  • 0≤Ai,j,Bi,j≤1050 \leq A_{i, j}, B_{i, j} \leq 10^5
  • 輸入皆為整數

輸入格式

H W
A_{1, 1} A_{1, 2} … A_{1, W}
A_{2, 1} A_{2, 2} … A_{2, W}
⋮
A_{H, 1} A_{H, 2} … A_{H, W}
B_{1, 1} B_{1, 2} … B_{1, W}
B_{2, 1} B_{2, 2} … B_{2, W}
⋮
B_{H, 1} B_{H, 2} … B_{H, W}

輸出格式

若可以透過操作使 AA 與 BB 一致，請在第 11 行輸出 Yes，第 22 行輸出最少操作次數。 若無法使 AA 與 BB 一致，請輸出 No。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 3
0 0 0
0 0 0
0 0 0
1 1 0
1 1 0
0 0 0

輸出：

Yes
1

說明： 選擇 (x,y)=(1,1)(x, y)=(1, 1) 執行增加 11 的操作，即可使 AA 與 BB 一致。

❌ Unsupported block (heading_4)

輸入：

3 3
0 0 0
0 0 0
0 0 0
0 0 0
0 1 0
0 0 0

輸出：

No

說明： 無論如何操作都無法使 AA 與 BB 一致。

❌ Unsupported block (heading_4)

輸入：

5 5
6 17 18 29 22
39 50 25 39 25
34 34 8 25 17
28 48 25 47 42
27 47 24 32 28
4 6 3 29 28
48 50 21 48 29
44 44 19 47 28
4 49 46 29 28
4 49 45 1 1

輸出：

Yes
140

080 - 共享位元 / Let’s Share Bit（★6）

題目描述

有 NN 個非負整數 A1,A2,ldots,ANA_1,A_2,\\ldots,A_N。

在所有滿足 0≤x<2D0 \leq x < 2^D 的整數 xx 中，請計算對所有 i=1,2,ldots,Ni=1,2,\\ldots,N 都滿足以下條件的 xx 有多少個：

  • AiA_i 與 xx 的按位與（Bitwise AND⁡\operatorname{AND}）不為 00。

❌ Unsupported block (heading_4)

非負整數 A,BA,B 的按位與（Bitwise AND⁡\operatorname{AND}）A AND⁡ BA\ \operatorname{AND}\ B 定義如下：

  • 將 A AND⁡ BA\ \operatorname{AND}\ B 以二進位表示時，其 2k (k≥0)2^k\ (k\geq0) 位上的數字在 A,BA,B 的二進位表示中 2k2^k 位皆為 11 時為 11，否則為 00。

例如 3 AND⁡ 5=13\ \operatorname{AND}\ 5=1（以二進位表示：011 AND⁡ 101=001011\ \operatorname{AND}\ 101=001）。

數據範圍

  • 1≤N≤201\leq N\leq20
  • 0≤D≤600\leq D\leq60
  • 0≤Ai<2D (1≤i≤N)0\leq A_i<2^D\ (1\leq i\leq N)
  • 輸入皆為整數

輸入格式

N D
A_1 A_2 … A_N

輸出格式

請輸出滿足所有 NN 個條件的整數 xx 的個數。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 3
1 3 4 5

輸出：

2

說明：00 以上小於 232^3 的整數 xx 分別滿足以下條件： - 00：不滿足任何條件。 - 11：滿足第 1,2,41,2,4 個條件，但不滿足第 33 個條件。 - 22：滿足第 22 個條件，但不滿足第 1,3,41,3,4 個條件。 - 33：滿足第 1,2,41,2,4 個條件，但不滿足第 33 個條件。 - 44：滿足第 3,43,4 個條件，但不滿足第 1,21,2 個條件。 - 55：滿足所有條件。 - 66：滿足第 2,3,42,3,4 個條件，但不滿足第 11 個條件。 - 77：滿足所有條件。

因此，答案為 22。

❌ Unsupported block (heading_4)

輸入：

5 21
1050624 32772 493952 144 869120

輸出：

869120

❌ Unsupported block (heading_4)

輸入：

20 60
216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760

輸出：

977902973481140224

說明： 輸入或輸出的數值可能會超出 3232 位元整數的範圍。

081 - 友好團體 / Friendly Group（★5）

題目描述

典型高中有 NN 名學生，每位學生的編號為 11 到 NN。學生 ii 的身高為 AiA_i，體重為 BiB_i。

從這 NN 名學生中選出 11 人以上組成一個隊伍，使得隊伍滿足以下所有條件：

  • 隊伍中任意兩名學生的身高之差的絕對值皆不超過 KK。
  • 隊伍中任意兩名學生的體重之差的絕對值皆不超過 KK。

請計算隊伍人數可能的最大值。

數據範圍

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤K≤50001 \leq K \leq 5000
  • 1≤Ai,Bi≤5000 (1≤i≤N)1 \leq A_i, B_i \leq 5000 \ (1 \leq i \leq N)
  • 所有輸入皆為整數

輸入格式

N K
A_1 B_1
A_2 B_2
⋮
A_N B_N

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 4
1 1
2 5
7 4

輸出：

2

說明： 由 ∣A1−A2∣=∣1−2∣=1≤K|A_1 - A_2| = |1 - 2| = 1 \leq K 且 ∣B1−B2∣=∣1−5∣=4≤K|B_1 - B_2| = |1 - 5| = 4 \leq K，可以選擇學生 11 與學生 22 組成 22 人的隊伍。

由於無法組成超過 22 人的隊伍，故輸出 22。

❌ Unsupported block (heading_4)

輸入：

2 123
4 5
678 901

輸出：

1

說明： 有時可能只能組成 11 人的隊伍。

❌ Unsupported block (heading_4)

輸入：

7 10
20 20
20 20
20 30
20 40
30 20
30 30
40 20

輸出：

5

說明： 可以選擇學生 1,2,3,5,61, 2, 3, 5, 6 共 55 人組成隊伍。

082 - 數數字 / Counting Numbers（★3）

題目描述

有一個什麼都沒寫的黑板。 依序對 x=L,L+1,…,Rx = L, L+1, \dots, R 進行以下操作：

  • 在黑板上寫下整數 xx 共 xx 次。

在所有操作結束後，請計算黑板上所寫的字元總個數除以 109+710^9+7 的餘數。

請注意，計算的是字元的數量而不是整數的個數。例如，整數 1515 會被計為 22 個字元。

數據範圍

  • 1≤L≤R≤10181 \leq L \leq R \leq 10^{18}
  • 所有輸入皆為整數

輸入格式

L R

輸出格式

在所有操作結束後，請輸出黑板上所寫的字元總個數除以 109+710^9+7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 5

輸出：

12

說明： 在所有操作結束後，黑板上寫有以下整數：

3,3,3,4,4,4,4,5,5,5,5,53, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5

因此，寫下的字元總個數為 1212。

❌ Unsupported block (heading_4)

輸入：

98 100

輸出：

694

說明： 在所有操作結束後，黑板上寫有 9898 個 9898、9999 個 9999 以及 100100 個 100100。

因此，寫下的字元總個數為 2×98+2×99+3×100=6942 \times 98 + 2 \times 99 + 3 \times 100 = 694。

❌ Unsupported block (heading_4)

輸入：

1001 869120

輸出：

59367733

說明： 請輸出除以 109+710^9+7 的餘數。

❌ Unsupported block (heading_4)

輸入：

381453331666495446 746254773042091083

輸出：

584127830

說明： 輸入可能無法以 3232 位元整數型態容納。

083 - 彩色圖 / Colorful Graph（★6）

題目描述

給定一個有 NN 個頂點、MM 條邊的連通簡單無向圖。圖中的頂點編號分別為 11 到 NN。 第 ii 條邊雙向連接頂點 aia_i 與 bib_i。

共有 10910^9 種顏色，每種顏色的編號為 11 到 10910^9。 最初，所有頂點都被塗上顏色 11。

接下來給定 QQ 個以下形式的查詢，請依序處理：

  • 給定整數 x,yx, y。輸出頂點 xx 目前的顏色編號，並將頂點 xx 以及與其相鄰的所有頂點重新塗上顏色 yy。

數據範圍

  • 1≤N≤2000001 \leq N \leq 200000
  • N−1≤M≤min⁡(N(N−1)2,200000)N - 1 \leq M \leq \min(\frac{N(N - 1)}{2}, 200000)
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 1≤Q≤2000001 \leq Q \leq 200000
  • 1≤xi≤N1 \leq x_i \leq N
  • 1≤yi≤1091 \leq y_i \leq 10^9
  • 給定的圖為簡單圖
  • 給定的圖為連通圖
  • 所有輸入皆為整數

輸入格式

N M
a_1 b_1
⋮
a_M b_M
Q
x_1 y_1
⋮
x_Q y_Q

輸出格式

請依序輸出各查詢的答案，共 QQ 行。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 4
1 2
1 3
1 4
2 3
5
4 2
3 3
2 4
4 5
1 6

輸出：

1
1
3
2
5

說明： 各查詢的處理過程如下：

  • 第 11 個查詢：輸出頂點 44 的顏色編號 11，並將頂點 1,41, 4 的顏色修改為 22。
  • 第 22 個查詢：輸出頂點 33 的顏色編號 11，並將頂點 1,2,31, 2, 3 的顏色修改為 33。
  • 第 33 個查詢：輸出頂點 22 的顏色編號 33，並將頂點 1,2,31, 2, 3 的顏色修改為 44。
  • 第 44 個查詢：輸出頂點 44 的顏色編號 22，並將頂點 1,41, 4 的顏色修改為 55。
  • 第 55 個查詢：輸出頂點 11 的顏色編號 55，並將頂點 1,2,3,41, 2, 3, 4 的顏色修改為 66。

❌ Unsupported block (heading_4)

輸入：

10 20
1 3
7 8
5 8
2 3
7 10
6 7
4 7
9 5
6 5
2 9
4 2
5 7
3 10
4 8
1 8
10 8
5 3
9 1
7 3
2 1
10
3 5
2 2
8 9
5 3
8 2
3 9
7 1
7 1
8 4
6 8

輸出：

1
5
1
9
3
3
9
1
1
1

084 - 包含兩種字元 / There are two types of characters（★3）

題目描述

給定一個由 o 和 x 組成且長度為 NN 的字串 SS。

請計算滿足以下所有條件的整數對 (l,r)(l, r) 的個數：

  • 1≤l≤r≤N1 \leq l \leq r \leq N
  • 在 SS 的第 ll 個字元到第 rr 個字元的區間中，同時包含 o 和 x。

數據範圍

  • 1≤N≤1061 \leq N \leq 10^6
  • SS 是由 o、x 組成長度為 NN 的字串

輸入格式

N
S

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

4
ooxo

輸出：

5

說明： 共有 (l,r)=(1,3),(1,4),(2,3),(2,4),(3,4)(l, r) = (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 這 55 組滿足條件。

❌ Unsupported block (heading_4)

輸入：

5
oxoxo

輸出：

10

❌ Unsupported block (heading_4)

輸入：

5
ooooo

輸出：

0

說明： 無論選擇哪一組 (l,r)(l, r) 都不滿足條件。

❌ Unsupported block (heading_4)

輸入：

7
xxoooxx

輸出：

16

085 - 乘法 085 / Multiplication 085（★4）

題目描述

給定一個正整數 KK。請計算滿足 abc=Kabc = K 的正整數三元組 (a,b,c) (a≤b≤c)(a, b, c) \ (a \le b \le c) 共有多少組。

數據範圍

  • 1≤K≤10121 \leq K \leq 10^{12}
  • 所有輸入皆為整數

輸入格式

K

輸出格式

請輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

42

輸出：

5

說明： 有以下 55 種表示為 33 個正整數之積的方法：

  • 令 (a,b,c)=(1,1,42)(a, b, c) = (1, 1, 42) [1×1×42=421 \times 1 \times 42 = 42]
  • 令 (a,b,c)=(1,2,21)(a, b, c) = (1, 2, 21) [1×2×21=421 \times 2 \times 21 = 42]
  • 令 (a,b,c)=(1,3,14)(a, b, c) = (1, 3, 14) [1×3×14=421 \times 3 \times 14 = 42]
  • 令 (a,b,c)=(1,6,7)(a, b, c) = (1, 6, 7) [1×6×7=421 \times 6 \times 7 = 42]
  • 令 (a,b,c)=(2,3,7)(a, b, c) = (2, 3, 7) [2×3×7=422 \times 3 \times 7 = 42]

❌ Unsupported block (heading_4)

輸入：

7

輸出：

1

說明： 有以下 11 種表示為 33 個正整數之積的方法：

  • 令 (a,b,c)=(1,1,7)(a, b, c) = (1, 1, 7) [1×1×7=71 \times 1 \times 7 = 7]

❌ Unsupported block (heading_4)

輸入：

192

輸出：

16

086 - Snuke 喜歡的數列 / Snuke’s Favorite Arrays（★5）

題目描述

Snuke 喜歡同時滿足以下 22 個條件且長度為 NN 的數列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)：

  • 條件 1：對所有 i (1≤i≤Q)i \ (1 \leq i \leq Q)，皆滿足 Axi OR Ayi OR Azi=wiA_{x_i} \ \mathrm{OR} \ A_{y_i} \ \mathrm{OR} \ A_{z_i} = w_i（此處 OR\mathrm{OR} 代表按位元或運算）
  • 條件 2：對所有 j (1≤j≤N)j \ (1 \leq j \leq N)，皆滿足 0≤Aj<2600 \leq A_j < 2^{60}

請輸出 Snuke 喜歡的數列 AA 的個數除以 10000000071000000007 的餘數。

數據範圍

  • 3≤N≤123 \leq N \leq 12
  • 1≤Q≤501 \leq Q \leq 50
  • 1≤xi<yi<zi≤N (1≤i≤Q)1 \leq x_i < y_i < z_i \leq N \ (1 \leq i \leq Q)
  • 0≤wi<260 (1≤i≤Q)0 \leq w_i < 2^{60} \ (1 \leq i \leq Q)
  • 所有輸入皆為整數

輸入格式

N Q
x_1 y_1 z_1 w_1
⋮
x_Q y_Q z_Q w_Q

輸出格式

請輸出 Snuke 喜歡的數列 AA 的個數除以 10000000071000000007 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 2
1 2 3 50
2 3 4 45

輸出：

13

說明： 例如 A=(50,32,0,13)A = (50, 32, 0, 13) 是 Snuke 喜歡的數列之一。可以確認它滿足所有給定的條件：

  • (A1 OR A2 OR A3)=(50 OR 32 OR 0)=50(A_1 \ \mathrm{OR} \ A_2 \ \mathrm{OR} \ A_3) = (50 \ \mathrm{OR} \ 32 \ \mathrm{OR} \ 0) = 50
  • (A2 OR A3 OR A4)=(32 OR 0 OR 13)=45(A_2 \ \mathrm{OR} \ A_3 \ \mathrm{OR} \ A_4) = (32 \ \mathrm{OR} \ 0 \ \mathrm{OR} \ 13) = 45
  • 數列 AA 的每個元素值皆在 00 以上且小於 2602^{60}

❌ Unsupported block (heading_4)

輸入：

8 2
2 3 6 1152886174205865983
1 2 8 1116611213275394047

輸出：

395781543

說明： 請輸出除以 10000000071000000007 的餘數。

087 - Chokudai 的要求 / Chokudai’s Demand（★5）

題目描述

AtCoder 國有 NN 座城鎮，編號分別為 1,2,…,N1, 2, \dots, N。任意兩座城鎮之間都有一條道路，支付交通費（單位：Snuke）即可從一座城鎮移動到另一座城鎮。

AtCoder 國的大臣在決定一個正整數 XX 之後，將每對 (i,j) (i≠j)(i, j) \ (i \neq j) 之間的交通費設定如下：

  • 當 Ai,j≠−1A_{i,j} \neq -1 時：連接城鎮 ii 與城鎮 jj 的道路交通費為 Ai,jA_{i,j} Snuke
  • 當 Ai,j=−1A_{i,j} = -1 時：連接城鎮 ii 與城鎮 jj 的道路交通費為 XX Snuke

此外，根據 Chokudai 國王的要求，必須滿足以下條件：

透過適當選擇路徑，使得從城鎮 ii 到城鎮 jj 的總交通費在 PP Snuke 以下即可到達的點對 (i,j) [1≤i<j≤N](i, j) \ [1 \leq i < j \leq N] 恰好有 KK 對。

請問有多少種 XX 的取法能滿足 Chokudai 國王的要求？若有無限多種，請回報此情況。

數據範圍

  • 2≤N≤402 \leq N \leq 40
  • 1≤P≤1091 \leq P \leq 10^9
  • 0≤K≤N(N−1)20 \leq K \leq \frac{N(N-1)}{2}
  • 若 i≠ji \neq j，則 1≤Ai,j≤1081 \leq A_{i,j} \leq 10^8 或 Ai,j=−1A_{i,j}=-1
  • 若 i=ji = j，則 Ai,j=0A_{i,j}=0
  • Ai,j=Aj,iA_{i,j}=A_{j,i}
  • 所有輸入皆為整數

輸入格式

N P K
A_{1,1} … A_{1,N}
⋮
A_{N,1} … A_{N,N}

輸出格式

若滿足 Chokudai 國王要求的正整數 XX 的個數為有限個，請輸出其數量；若為無限多個，請輸出 Infinity。

範例測資

❌ Unsupported block (heading_4)

輸入：

3 4 2
0 3 -1
3 0 5
-1 5 0

輸出：

3

說明： 例如取 X=3X=3 時，在 44 Snuke 以下即可到達的城鎮對數恰好為 22 對，滿足 Chokudai 國王的要求：

  • 從城鎮 11 到城鎮 22 可在 44 Snuke 以下到達
  • 從城鎮 11 到城鎮 33 可在 44 Snuke 以下到達
  • 從城鎮 22 到城鎮 33 無法在 44 Snuke 以下到達

另外，當 X=2,3,4X = 2, 3, 4 時滿足 Chokudai 國王的要求，其他情況則不滿足，因此答案為 33。

❌ Unsupported block (heading_4)

輸入：

3 10 2
0 -1 10
-1 0 1
10 1 0

輸出：

Infinity

說明： 對所有 X≥11X \geq 11 的正整數 XX，皆滿足 Chokudai 國王的要求。因此存在無限多個，應輸出 Infinity。

❌ Unsupported block (heading_4)

輸入：

13 777 77
0 425 886 764 736 -1 692 660 -1 316 424 490 423
425 0 -1 473 -1 311 -1 -1 903 941 386 521 486
886 -1 0 605 519 473 775 467 677 769 690 483 501
764 473 605 0 424 454 474 408 421 530 756 568 685
736 -1 519 424 0 -1 804 598 911 731 837 459 610
-1 311 473 454 -1 0 479 613 880 -1 393 875 334
692 -1 775 474 804 479 0 579 -1 -1 575 985 603
660 -1 467 408 598 613 579 0 456 378 887 -1 372
-1 903 677 421 911 880 -1 456 0 859 701 476 370
316 941 769 530 731 -1 -1 378 859 0 800 870 740
424 386 690 756 837 393 575 887 701 800 0 -1 304
490 521 483 568 459 875 985 -1 476 870 -1 0 716
423 486 501 685 610 334 603 372 370 740 304 716 0

輸出：

42

088 - 異曲同工 / Similar but Different Ways（★6）

題目描述

有 NN 張卡片，每張卡片的編號分別為 11 到 NN。卡片 ii 上寫有一個正整數 AiA_i。 E869120 與 square1001 各自從這些卡片中選出了 11 張以上的卡片。 已知兩人的選卡方式滿足以下所有條件：

  • 條件 1：E869120 選取的卡片上整數總和，與 square1001 選取的卡片上整數總和相等。
  • 條件 2：對於每個 i=1,2,…,Qi = 1, 2, \dots, Q，沒有人同時選取卡片 XiX_i 與卡片 YiY_i。
  • 條件 3：兩人選取的卡片集合不相同。

請輸出其中一種可能的卡片選法。但請注意：可能存在被 E869120 與 square1001 兩人都選取的卡片。

數據範圍

  • 2≤N≤882 \leq N \leq 88
  • 0≤Q≤N(N−1)20 \leq Q \leq \frac{N(N-1)}{2}
  • 1≤Ai1 \leq A_i
  • A1+A2+⋯+AN≤8888A_1 + A_2 + \dots + A_N \leq 8888
  • 1≤Xi<Yi≤N1 \leq X_i < Y_i \leq N
  • 若 i≠ji \neq j，則 (Xi,Yi)≠(Xj,Yj)(X_i, Y_i) \neq (X_j, Y_j)
  • 所有輸入皆為整數
  • 保證存在滿足條件的選法

輸入格式

N Q
A_1 A_2 … A_N
X_1 Y_1
X_2 Y_2
⋮
X_Q Y_Q

輸出格式

若 E869120 選取的卡片為 (B1,B2,…,Bx) [B1<B2<⋯<Bx](B_1, B_2, \dots, B_x) \ [B_1 < B_2 < \dots < B_x]，square1001 選取的卡片為 (C1,C2,…,Cy) [C1<C2<⋯<Cy](C_1, C_2, \dots, C_y) \ [C_1 < C_2 < \dots < C_y]，請依照以下格式輸出 44 行：

x
B_1 B_2 … B_x
y
C_1 C_2 … C_y

範例測資

❌ Unsupported block (heading_4)

輸入：

5 2
3 1 3 2 3
1 2
1 4

輸出：

4
2 3 4 5
3
1 3 5

說明：A2+A3+A4+A5=9,A1+A3+A5=9A_2 + A_3 + A_4 + A_5 = 9, A_1 + A_3 + A_5 = 9，兩人所選卡片上的整數總和相等。 由於其他條件也全部滿足，故此輸出為正確答案。 除此之外，例如以下輸出也被視為正確答案：

2
1 3
2
1 5

❌ Unsupported block (heading_4)

輸入：

10 10
2 5 7 8 11 10 1 88 86 50
1 2
1 3
1 4
1 5
1 6
5 10
6 10
2 3
9 10
7 8

輸出：

2
6 7
1
5

089 - 分割與逆序數 / Partitions and Inversions（★7）

題目描述

給定一個長度為 NN 的正整數數列 A=(A1,A2,A3,…,AN)A = (A_1, A_2, A_3, \dots, A_N)。

將這個數列分割為 11 個以上非空的連續區間的方法共有 2N−12^{N-1} 種，請計算在這些分割方法中滿足以下條件的方法數：

  • 對於所有分割出的區間，該區間內的氣泡排序交換次數皆不超過 KK。

由於答案可能非常大，請輸出除以 109+710^9+7 的餘數。

所謂氣泡排序的交換次數定義如下：將「若 Ai>Ai+1A_i > A_{i+1} 則交換這兩個數」的操作依序對 i=1,2,…,N−1i = 1, 2, \dots, N-1 執行一次稱為「一次掃描」。已知重複進行 N−1N-1 次掃描即可將數列升序排序。此處將套用該演算法時進行整數交換的總次數定義為氣泡排序的交換次數。例如當 A=(2,4,3,1)A = (2, 4, 3, 1) 時，氣泡排序的交換次數為 44。

數據範圍

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤K≤N(N−1)20 \leq K \leq \frac{N(N-1)}{2}
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 所有輸入皆為整數

輸入格式

N K
A_1 A_2 A_3 … A_N

輸出格式

請在 11 行中輸出滿足題目條件的分割方法數除以 109+710^9+7 的餘數。

範例測資

❌ Unsupported block (heading_4)

輸入：

4 0
3 1 4 2

輸出：

2

說明：{3},{1,4},{2}\{3\}, \{1,4\}, \{2\} 以及 {3},{1},{4},{2}\{3\}, \{1\}, \{4\}, \{2\} 這 22 種分割方法滿足條件。

❌ Unsupported block (heading_4)

輸入：

7 2
5 3 7 2 1 2 3

輸出：

44

❌ Unsupported block (heading_4)

輸入：

7 0
7 6 5 4 3 2 1

輸出：

1

090 - Typical90 的最後一道題 / Tenkei90’s Last Problem（★7）

題目描述

請計算滿足以下條件且長度為 NN 的非負整數數列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) 的個數除以 998244353998244353 的餘數：

  • 對於任意滿足 1≤l≤r≤N1 \leq l \leq r \leq N 的整數對 (l,r)(l, r)，皆成立 min⁡{Al,Al+1,…,Ar}×(r−l+1)≤K\min \lbrace A_l, A_{l+1}, \dots, A_r \rbrace \times (r-l+1) \leq K。

數據範圍

  • 1≤N≤10111 \leq N \leq 10^{11}
  • 1≤K≤1051 \leq K \leq 10^5
  • 所有輸入皆為整數

輸入格式

N K

輸出格式

請在 11 行中輸出答案。

範例測資

❌ Unsupported block (heading_4)

輸入：

2 2

輸出：

8

說明：A=(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1)A=(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1) 滿足條件。

A=(2,2)A=(2,2) 在 l=1,r=2l=1, r=2 時，min⁡{Al,Al+1,…,Ar}×(r−l+1)=min⁡{2,2}×(2−1+1)=4>K\min \lbrace A_l, A_{l+1}, \dots, A_r \rbrace \times (r-l+1) = \min \lbrace 2, 2 \rbrace \times (2-1+1) = 4 > K，因此不滿足條件。

❌ Unsupported block (heading_4)

輸入：

17 29

輸出：

263173793

說明： 此輸入滿足子任務 4, 5, 6, 7 的限制。

❌ Unsupported block (heading_4)

輸入：

2718 2818

輸出：

393799986

說明： 此輸入滿足子任務 5, 6, 7 的限制。

❌ Unsupported block (heading_4)

輸入：

28593 1

輸出：

365728740

說明： 此輸入滿足子任務 1, 2, 6, 7 的限制。

❌ Unsupported block (heading_4)

輸入：

869120 1001

輸出：

967393022

說明： 此輸入滿足子任務 7 的限制。