A. QAQ

Codeforces
IDCF894A
Time1000ms
Memory256MB
Difficulty
brute forcedp
English · Original
Chinese · Translation
Formal · Original
"QAQ" is a word to denote an expression of crying. Imagine "Q" as eyes with tears and "A" as a mouth. Now Diamond has given Bort a string consisting of only uppercase English letters of length _n_. There is a great number of "QAQ" in the string (Diamond is so cute!). <center>![image](https://espresso.codeforces.com/e2ee63ac64a28b997d0d327ee841cea43f8fc0ed.png) illustration by 猫屋 https://twitter.com/nekoyaliu</center>Bort wants to know how many subsequences "_QAQ_" are in the string Diamond has given. Note that the letters "_QAQ_" don't have to be consecutive, but the order of letters should be exact. ## Input The only line contains a string of length _n_ (1 ≤ _n_ ≤ 100). It's guaranteed that the string only contains uppercase English letters. ## Output Print a single integer — the number of subsequences "_QAQ_" in the string. [samples] ## Note In the first example there are 4 subsequences "_QAQ_": "_**QAQ**AQYSYIOIWIN_", "_**QA**QA**Q**YSYIOIWIN_", "_**Q**AQ**AQ**YSYIOIWIN_", "_QA**QAQ**YSYIOIWIN_".
"QAQ" 是一个表示哭泣的词语。想象 "Q" 是流着泪的眼睛,"A" 是嘴巴。 现在,Diamond 给了 Bort 一个仅由大写英文字母组成的、长度为 #cf_span[n] 的字符串。这个字符串中包含大量 "QAQ"(Diamond 真可爱!)。 Bort 想知道,在 Diamond 给出的字符串中有多少个子序列 "_QAQ_"。注意,字母 "_QAQ_" 不必连续,但字母的顺序必须完全一致。 仅有一行,包含一个长度为 #cf_span[n] 的字符串(#cf_span[1 ≤ n ≤ 100])。保证该字符串仅包含大写英文字母。 请输出一个整数 —— 字符串中 "_QAQ_" 子序列的个数。 在第一个例子中,有 #cf_span[4] 个 "_QAQ_" 子序列:"_*QAQ*AQYSYIOIWIN_"、"_*QA*QA*Q*YSYIOIWIN_"、"_*Q*AQ*AQ*YSYIOIWIN_"、"_QA*QAQ*YSYIOIWIN_"。 ## Input 仅有一行,包含一个长度为 #cf_span[n] 的字符串(#cf_span[1 ≤ n ≤ 100])。保证该字符串仅包含大写英文字母。 ## Output 请输出一个整数 —— 字符串中 "_QAQ_" 子序列的个数。 [samples] ## Note 在第一个例子中,有 #cf_span[4] 个 "_QAQ_" 子序列:"_*QAQ*AQYSYIOIWIN_"、"_*QA*QA*Q*YSYIOIWIN_"、"_*Q*AQ*AQ*YSYIOIWIN_"、"_QA*QAQ*YSYIOIWIN_".
Let $ s $ be a string of length $ n $, where $ s[i] \in \{ \text{A}, \text{Q}, \dots \} $ for $ 0 \leq i < n $. Define a subsequence "QAQ" as a triplet of indices $ (i, j, k) $ such that: - $ 0 \leq i < j < k < n $, - $ s[i] = \text{Q} $, - $ s[j] = \text{A} $, - $ s[k] = \text{Q} $. Let $ \text{count} = \sum_{\substack{0 \leq i < j < k < n \\ s[i] = \text{Q},\, s[j] = \text{A},\, s[k] = \text{Q}}} 1 $. Output $ \text{count} $.
Samples
Input #1
QAQAQYSYIOIWIN
Output #1
4
Input #2
QAQQQZZYNOIWIN
Output #2
3
API Response (JSON)
{
  "problem": {
    "name": "A. QAQ",
    "description": {
      "content": "\"QAQ\" is a word to denote an expression of crying. Imagine \"Q\" as eyes with tears and \"A\" as a mouth. Now Diamond has given Bort a string consisting of only uppercase English letters of length _n_. T",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF894A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "\"QAQ\" is a word to denote an expression of crying. Imagine \"Q\" as eyes with tears and \"A\" as a mouth.\n\nNow Diamond has given Bort a string consisting of only uppercase English letters of length _n_. T...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "\"QAQ\" 是一个表示哭泣的词语。想象 \"Q\" 是流着泪的眼睛,\"A\" 是嘴巴。\n\n现在,Diamond 给了 Bort 一个仅由大写英文字母组成的、长度为 #cf_span[n] 的字符串。这个字符串中包含大量 \"QAQ\"(Diamond 真可爱!)。\n\nBort 想知道,在 Diamond 给出的字符串中有多少个子序列 \"_QAQ_\"。注意,字母 \"_QAQ_\" 不必连续,但字母的顺序必须完全...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s $ be a string of length $ n $, where $ s[i] \\in \\{ \\text{A}, \\text{Q}, \\dots \\} $ for $ 0 \\leq i < n $.\n\nDefine a subsequence \"QAQ\" as a triplet of indices $ (i, j, k) $ such that:\n- $ 0 \\leq ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments