Hide

Problem B
Guillaume

Languages en is
/problems/guillaume/file/statement/is/img-0001.jpg
Mynd fengin af flickr.com

Guillaume hefur einstakan hæfileika til að gleyma atburðum sem gerðust fyrir sérstakan tímapunkt, til að líta betur út í minningu sinni. Guillaume og Arnar spila oft pool og ert þú með skrá af niðurstöðum leikja þeirra. Guillaume telur alltaf bara síðustu $k$ leikina sem hámarka sigurprósentu hans og hunsar alla aðra leiki á undan þeim. Guillaume getur samt ekki hunsað alla söguna því Arnar man alltaf niðurstöðu síðasta leiks. Sigurprósenta er skilgreind sem fjöldi sigra deildur með fjölda gildra leikja. Ef tvö gildi á $k$ koma til greina þá skal velja $k$ þannig það sé lágmarkað, því það er auðveldara fyrir Guillaume að muna.

Í pool er jafntefli ef báðir leikmenn ákveða að leikurinn sé ógildur og vilja byrja uppá nýtt. Ef leikur endar í jafntefli að þá er enginn sigurvegari í þeim leik.

Hver er staðan samkvæmt Guillaume?

Inntak

Inntak samanstendur af tveim línum. Fyrri línan inniheldur eina heiltölu $n$, fjöldi leikja sem voru skráðir. Seinni línan inniheldur runu af stöfum sem tákna niðurstöðu leikjanna sem Arnar og Guillaume hafa spilað. Stafur númer $i$ táknar niðurstöðu leiks $i$ og er A ef Arnar vann, G ef Guillaume vann eða D ef það var jafntefli.

Úttak

Skrifaðu út eina línu á forminu g-a þar sem $g$ er heiltala sem táknar fjölda sigra hans Guillaume og $a$ er heiltala sem táknar fjölda sigra Arnars, samkvæmt Guillaume.

Stigagjöf

Hópur

Stig

Takmarkanir

1

10

$n = 1$

2

30

$1 \leq n \leq 100$

3

20

$1 \leq n \leq 3 \cdot 10^5$, samanlagður fjöldi A og G er í mesta lagi $1\, 000$

4

40

$1 \leq n \leq 3 \cdot 10^5$

Sample Input 1 Sample Output 1
1
G
1-0
Sample Input 2 Sample Output 2
29
AAAGAGAGAAGAAAGADGAAAGGGGGGGA
7-1
Sample Input 3 Sample Output 3
12
AGAGDDDDGAGA
3-2
Sample Input 4 Sample Output 4
55
GGAAAAAGAAGGAAGGGGAAGGGDDAGGGGGGGGAAGAAAGGGGGGGGGAGGGAA
12-3