以下是西元6666年發生在成功星的一段經典故事:
自從成功星開放地球人移居後,同樣位於此星球的極野國與郁壯元國馬上以精湛的廚藝聞名全宇宙,且視彼此為勁敵。某天,號稱天下第一廚神的極野國使者大麥想精進自身的廚藝,自行跨越兩國中的大漠,前往郁壯元國與當地的廚師交流,不料遭間諜暗殺。
極野國錯失了這位能撐起國家顏面的大麥廚神,立馬整頓軍隊,抱著必勝的決心向郁壯元國報仇。極野國的陸軍總司令認為兵力充足,故將士兵分成許多兵團,下令分開且等速平行前進,而士兵們行進到一半的距離時,極野國接獲消息表示郁壯元國的士兵總數與極野國不相上下,甚至還多出了一些,此時陸軍總司令下達新指令,要求相鄰的兩兵團集體行動,但新的難題降臨了,由於兵團總數剛好是奇數,故各個兵團無法分辨要往左還是往右合併。
經過了十分鐘,極野國國王想到了一個不錯的方法,道:「為求合併迅速,我們可以先無視一個可以讓其他兵團之間的距離達到最小的兵團,並要求該兵團的士兵們平均分配到其他兵團中」,大部分人不太懂這句話的意思,所以國王又道:「若現在有甲、乙、丙三個兵團,甲與乙相隔300公尺,乙與丙相隔800公尺,則我們無視丙兵團,可以讓甲、乙兵團較迅速地合併,而丙兵團的士兵之後再依人數平均移至甲、乙兵團內即可」。
但實際上可不像只有三個兵團這麼簡單,在成功星上的極野國幅員遼闊,人民營養豐富,人口高達70億人,能派出的兵團數以萬計,相信身為極野國資訊大臣的你,絕對能幫助國王找出需要被平均分配至其他兵團的兵團編號。
由於極野國的兵團們是等速平行前進在荒漠上,為了簡化問題,可以把各兵團想像在一條數線上,並依兵團所在位置由左至右,由1開始編號,詳見範例說明。
第一行為一個正整數,表示荒漠的寬度(兩單位間相隔100公尺)。
第二行有一個長度為,由o與p組成的字串(o表示該點沒有兵團,p點表示該點有兵團)。
測資限制
1. 3<=n<=2e6。
2. 保證p次出現的次數必為奇數,且大於或等於3。
請輸出一個正整數,表示需要被平均移至其他兵團的兵團編號。
若有多種符合題意的答案,請輸出編號最小的
8 oppopopp
3
10 pooopopppo
1
範例1說明
可看出以下關係:
100m 200m 200m 100m
兵團1 ----- 兵團2 ---------- 兵團3 ---------- 兵團4 ----- 兵團5
若先無視兵團3來合併軍隊,即可最小化各兵團合併所需距離
(兵團1與兵團2相距100m,兵團4與兵團5相距100m,加總為200m)
範例2說明
可看出以下關係:
400m 200m 100m 100m
兵團1 ---------------- 兵團2 -------- 兵團3 ---- 兵團4 ---- 兵團5
若先無視兵團1來合併軍隊,即可最小化各兵團合併所需距離
(兵團2與兵團3相距200m,兵團4與兵團5相距100m,加總為300m)
評分說明
本題共有三組子任務,每一組有多筆測試資料,條件如下所示:
1. 只會有三個兵團,且 3<=n<=100。(10%)
2. 4<=n<=2000。(45%)
3. 無額外限制。(45%)