g111: B.復仇之戰(revenge)
Tags :
Accepted rate : 10人/14人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-18 14:30

Content

以下是西元6666年發生在成功星的一段經典故事:

    自從成功星開放地球人移居後,同樣位於此星球的極野國郁壯元國馬上以精湛的廚藝聞名全宇宙,且視彼此為勁敵。某天,號稱天下第一廚神的極野國使者大麥想精進自身的廚藝,自行跨越兩國中的大漠,前往郁壯元國與當地的廚師交流,不料遭間諜暗殺。

    極野國錯失了這位能撐起國家顏面的大麥廚神,立馬整頓軍隊,抱著必勝的決心向郁壯元國報仇。極野國的陸軍總司令認為兵力充足,故將士兵分成許多兵團,下令分開且等速平行前進,而士兵們行進到一半的距離時,極野國接獲消息表示郁壯元國的士兵總數與極野國不相上下,甚至還多出了一些,此時陸軍總司令下達新指令,要求相鄰的兩兵團集體行動,但新的難題降臨了,由於兵團總數剛好是奇數,故各個兵團無法分辨要往左還是往右合併

    經過了十分鐘,極野國國王想到了一個不錯的方法,道:「為求合併迅速,我們可以先無視一個可以讓其他兵團之間的距離達到最小的兵團,並要求該兵團的士兵們平均分配到其他兵團中」,大部分人不太懂這句話的意思,所以國王又道:「若現在有甲、乙、丙三個兵團,甲與乙相隔300公尺,乙與丙相隔800公尺,則我們無視丙兵團,可以讓甲、乙兵團較迅速地合併,而丙兵團的士兵之後再依人數平均移至甲、乙兵團內即可」。

    但實際上可不像只有三個兵團這麼簡單,在成功星上的極野國幅員遼闊,人民營養豐富,人口高達70億人,能派出的兵團數以萬計,相信身為極野國資訊大臣的你,絕對能幫助國王找出需要被平均分配至其他兵團的兵團編號。

    由於極野國的兵團們是等速平行前進在荒漠上,為了簡化問題,可以把各兵團想像在一條數線上,並依兵團所在位置由左至右,由1開始編號,詳見範例說明

 

Input

第一行為一個正整數,表示荒漠的寬度(兩單位間相隔100公尺)。

第二行有一個長度為,由o與p組成的字串(o表示該點沒有兵團,p點表示該點有兵團)。

 

測資限制

1. 3<=n<=2e6。

2. 保證p次出現的次數必為奇數,且大於或等於3。

Output

請輸出一個正整數,表示需要被平均移至其他兵團的兵團編號。

若有多種符合題意的答案,請輸出編號最小的

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

 

範例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%)

Tags:
出處:
2021成功高中校內賽 [管理者:
CGSH (快加油吧~~)
]


ID User Problem Subject Hit Post Date
27694
r1cky (木叢欉木叢)
g111
Java 解題心得
10 2021-10-23 21:38
27307
linlincaleb@... (臨末之頌)
g111
好難...
113 2021-09-23 22:13