← 返回题目列表

AtCoder · arc062_b

D. AtCoDeer 和 Rock-Paper

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

AtCoDeer 鹿和他的朋友 TopCoDeer 正在玩游戏。 游戏由 N 转。 在每一回合中,每个玩家都扮演两个角色中的一个 手势, 摇滚 和 纸,如石头剪刀布,在以下条件下:

(※) 每回合后,(玩家玩纸的次数)≦(玩家玩摇滚的次数)。

每个玩家的得分计算方式为(玩家获胜的回合数) - (玩家失败的回合数),每回合的结果由剪刀石头布的规则决定。

(对于那些不熟悉剪刀石头布的人来说:如果一个玩家玩石头,另一个玩家玩布,则后一个玩家获胜,前一个玩家输。如果两个玩家都做出相同的手势,则该回合为平局,没有玩家获胜或失败。)

AtCoDeer凭借他的超能力,能够预见到TopCoDeer在每场比赛中会做出的手势。 N 回合,游戏开始前。 规划 AtCoDeer 在每个回合中的手势,以最大化 AtCoDeer 的得分。

TopCoDeer 每回合将播放的手势由字符串给出 s。如果 i-th (1≦i≦N) 中的字符 s is g, TopCoDeer 将在 i第回合。同样,如果 i-th (1≦i≦N) 的性格 s in p, TopCoDeer 将在 i第回合。

约束

  • 1≦N≦10^5
  • N=|s|
  • 中的每个字符 s is g or p.
  • 代表的手势 s 满足条件(※)。

输入

输入由标准输入按以下格式给出:

s

输出

打印 AtCoDeer 的最大可能分数。


示例输入 1

gpg

示例输出 1

0

每回合与对手做出相同的手势,得分为 0,这是可能的最大分数。


示例输入 2

ggppgggpgg

示例输出 2

2

例如,考虑按以下顺序播放手势:石头、纸、石头、纸、石头、石头、纸、纸、石头、纸。此策略取得三胜一负,得分为 2,这是可能的最大分数。