1726 . Dice Wars

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.5% (38/42)

Submission's AC Ratio

27.3% (98/359)

Tags

Description

Dice Wars是一款兼具謀略和運氣的遊戲。
（Flash版本已停止支援）

遊戲中你扮演紫色的骰子，要攻下其他顏色的骰子的城池，進而統一全地圖。

如今你選到了一張看起來不錯的地圖－－整張地圖呈一條直線，每個位置都有一個顏色勢力佔領。

由於每次移動到相鄰異色的城池都必須經歷一場鏖戰，你想先經過程式計算後再進行遊戲。

你想要每次詢問一個顏色對(S, T)，問從任何一個S的城池到任一個T的城池至少要經過幾場戰鬥。

如果S或T已經滅亡(地圖中沒有任何一個該勢力)，就輸出-1。

Input Format

輸入第一行有兩個數字N, M。表示地圖共有N格、接下來有M個詢問。

接下來一行有N個以空白隔開的數字Ci表示佔領第i個位置的顏色勢力。

接下來會有M行，每行兩個正整數S, T，表示每次詢問。

1 <= N, M <= 60000
1 <= Ci, S, T <= N

Output Format

輸出會有M行，每行包含一個整數Ai表示對第i個詢問的回答。

Sample Input 1

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

Sample Output 1

1
3
0
-1

Hints

第一個詢問是問從勢力1到勢力2要經過幾次戰鬥。
最近的就是從位置3的勢力1到位置2的勢力2，經過1場戰鬥(打下位置2)

第二個詢問是問從1到3要經過幾次戰鬥。
最近的就是從位置4的勢力1到位置7的勢力3，經過3場戰鬥(打下位置5、6、7)

第三個詢問是問從1到1要經過幾次戰鬥。
所以是0場。

第四個詢問中，因為地圖上沒有4所以輸出-1。

Problem Source

原TIOJ1726 / Problem Setter : ATP

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10
Submit
Back to Top