b916: 旅行者_九國遊歷記<11> 農場 (Farm)
Tags : 旅行者
Accepted rate : 4人/6人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-01-21 12:26

Content

經過一番精彩的對決,支持者隊打敗了酸民隊,酸民隊答應會收斂一點,不會有事沒事酸小玉了。

  過了幾天,小赤在圖書館的工作結束了,他們決定去小澄去過的猿國,要前往時支持者隊的人前來送別,並送上禮物袋。

  「裡面是什麼?」小赤問著。

  「之後就知道了」一個人回應。

  過了幾天,他們到了猿國,因為有小澄的幫助,他們的點名事務減輕了許多, 讓他們有更多的人力去找失蹤的人,最後發現大部分的失蹤者都掉進結界,經過一些努力後,將那些人帶回國內。不過現在他們遇到了農業問題,農場中最近出現一些魔法菜蟲,魔法的問題必須用魔法來解決,猿國的魔法師老爹負責管理這些菜蟲,但是不知道菜蟲的正確位置,往往浪費法力在根本不會有菜蟲的位置上。一看到小澄又回來,便想求助他。

  經過研究,小赤了解到菜蟲有多節身體,每節高度不一樣,並且可以隨時替換身體的相鄰兩節,農場每一區的作物也各有其高度,菜蟲可以交換身體順序,使得其高度所形成的序列,正好和某連續區間的高度序列完全相同,並隱身在其中,為了不被人發現,他只會在沒人時才會現身,否則會一直隱藏,此外,不知道為什麼,菜蟲只會在一直線的作物區上移動。

  魔法師老爹施法擊中菜蟲的任一節身體就可以將其消滅,現有的技術可以知道菜蟲的長度及每一節的高度、他活動的範圍,以及每一區作物的高度,小澄只要幫忙判斷菜蟲可能在的區間就可以了。

  「請交給我!」小澄自信地說。

Input

首行輸入一個整數 M,N(1≤M≤N≤10^6 ) ,代表菜蟲的長度以及其活動作物區個數,第二行 M 個整數 a_i (0<a_i≤10^6 ) 以空格隔開,代表菜蟲每一節身體的高度,第三行 N 個整數 b_i (0< b_i≤10^6 ) 以空格隔開,代表作物區高度。

Output

對輸出所有菜蟲能隱身的區間,若有多組區間,請輸出多行,並以左界由小至大的順序輸出;如果沒有菜蟲能隱身的區間,請輸出-1。

Sample Input #1
2 7 
1 2
1 2 3 1 2 3 1
Sample Output #1
1 2
4 5
Sample Input #2
2 7
1 2
1 2 1 2 3 2 1
Sample Output #2
1 2
2 3
3 4
6 7
Sample Input #3
3 7
1 2 9
1 2 1 2 3 2 1
Sample Output #3
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (1%): 1.0s , <1M
公開 測資點#1 (1%): 1.0s , <1M
公開 測資點#2 (1%): 1.0s , <1M
公開 測資點#3 (1%): 1.0s , <10M
公開 測資點#4 (1%): 1.0s , <1K
公開 測資點#5 (1%): 1.0s , <1K
公開 測資點#6 (1%): 1.0s , <1K
公開 測資點#7 (9%): 1.0s , <1K
公開 測資點#8 (1%): 1.0s , <1M
公開 測資點#9 (1%): 1.0s , <1M
公開 測資點#10 (17%): 1.0s , <1M
公開 測資點#11 (1%): 1.0s , <1K
公開 測資點#12 (1%): 1.0s , <1M
公開 測資點#13 (1%): 1.0s , <1M
公開 測資點#14 (1%): 1.0s , <10M
公開 測資點#15 (19%): 1.0s , <10M
公開 測資點#16 (1%): 1.5s , <1K
公開 測資點#17 (1%): 1.5s , <1M
公開 測資點#18 (1%): 1.5s , <1M
公開 測資點#19 (1%): 1.5s , <1M
公開 測資點#20 (1%): 1.5s , <10M
公開 測資點#21 (12%): 1.5s , <10M
公開 測資點#22 (1%): 1.5s , <50M
公開 測資點#23 (1%): 1.5s , <10M
公開 測資點#24 (23%): 1.5s , <10M
Hint :

本題共有六組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

(註:因為系統配分限制,所以第一子任務改為 4 分,第二子任務改為 12 分)

Tags:
旅行者
出處:
108學年度板橋高中校內資訊學科能力競賽 [管理者:
99st60107 (林子傑)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」