Problem E
Guillaume
Languages
en
is
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 |
