← 返回题目列表

AtCoder · agc005_a

A. 字符串

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

分数: 300 点

问题陈述

我们有一个字符串 X,其字符数为偶数。一半的角色是 S,另一半是 T.

高桥,讨厌字符串 ST,将执行以下操作 10^{10000} 次:

  • 出现以下情况 ST in X 作为(连续)子字符串,删除最左边的一个。如果没有发生,则不执行任何操作。

找到最终的长度 X.

约束

  • 2 ≦ |X| ≦ 200,000
  • 的长度 X 是偶数。
  • 中的一半字符 X 是 S,另一半是 T.

部分分数

  • 在测试用例中值得 200 点, |X| ≦ 200.

输入

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

X

输出

打印最终长度 X.


示例输入 1

TSTTSS

示例输出 1

4

在 1-st 操作, 2-nd 和 3-rd 字符 TSTTSS 被删除。 X 变为 TTSS,并且由于它不包含 ST 不再了,剩下的时间里什么也没做 10^{10000}-1 操作。 因此,答案是 4.


示例输入 2

SSTTST

示例输出 2

0

X 最终会变成空字符串: SSTTST ⇒ STST ⇒ ST ⇒ ``.


示例输入 3

TSSTTTSS

示例输出 3

4

X 将变为: TSSTTTSS ⇒ TSTTSS ⇒ TTSS.