100463: [AtCoder]ABC046 D - AtCoDeer and Rock-Paper

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $300$ points

Problem Statement

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$

Output

Print the AtCoDeer's maximum possible score.


Sample Input 1

gpg

Sample 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.


Sample Input 2

ggppgggpgg

Sample 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.

Input

题意翻译

你和对手都只有两种出拳方式:石头($g$)和布($p$),规则一样,赢了得一分,平局不得分,输了减一分。 现给你对手的出拳方式,设你到 $i$ 位置共出了 $x_i$ 次石头,$y_i$ 次布,在对于任意位置 $i$ 满足 $x_i \geq y_i$ 的条件下,输出你能得到的最大分数。

加入题单

上一题 下一题 算法标签: