AtCoDeer and Rock-Paper

AtCoder

IDarc062_b

Time2000ms

Memory256MB

Difficulty—

AtCoDeer the deer and his friend TopCoDeer is playing a game. The game consists of $N$ turns. In each turn, each player plays one of the two _gestures_, _Rock_ and _Paper_, as in Rock-paper-scissors, under the following condition: (※) After each turn, (the number of times the player has played Paper)$≦$(the number of times the player has played Rock). Each player's score is calculated by (the number of turns where the player wins) $-$ (the number of turns where the player loses), where the outcome of each turn is determined by the rules of Rock-paper-scissors. _(For those who are not familiar with Rock-paper-scissors: If one player plays Rock and the other plays Paper, the latter player will win and the former player will lose. If both players play the same gesture, the round is a tie and neither player will win nor lose.)_ With his supernatural power, AtCoDeer was able to foresee the gesture that TopCoDeer will play in each of the $N$ turns, before the game starts. Plan AtCoDeer's gesture in each turn to maximize AtCoDeer's score. The gesture that TopCoDeer will play in each turn is given by a string $s$. If the $i$\-th $(1≦i≦N)$ character in $s$ is `g`, TopCoDeer will play Rock in the $i$\-th turn. Similarly, if the $i$\-th $(1≦i≦N)$ character of $s$ in `p`, TopCoDeer will play Paper in the $i$\-th turn. ## Constraints * $1≦N≦10^5$ * $N=|s|$ * Each character in $s$ is `g` or `p`. * The gestures represented by $s$ satisfy the condition (※). ## Input The input is given from Standard Input in the following format: $s$ [samples]

Samples

Input #1

gpg

Output #1

0

Playing the same gesture as the opponent in each turn results in the score of $0$, which is the maximum possible score.

Input #2

ggppgggpgg

Output #2

2

For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy earns three victories and suffers one defeat, resulting in the score of $2$, which is the maximum possible score.

API Response (JSON)

{
  "problem": {
    "name": "AtCoDeer and Rock-Paper",
    "description": {
      "content": "AtCoDeer the deer and his friend TopCoDeer is playing a game. The game consists of $N$ turns. In each turn, each player plays one of the two _gestures_, _Rock_ and _Paper_, as in Rock-paper-scissors, ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc062_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "AtCoDeer the deer and his friend TopCoDeer is playing a game. The game consists of $N$ turns. In each turn, each player plays one of the two _gestures_, _Rock_ and _Paper_, as in Rock-paper-scissors, ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments