B. Pen Pineapple Apple Pen

Codeforces

IDCF10113B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

PPAP, which stands for Pen Pineapple Apple Pen, is an unusual song and dance that went viral in the Internet recently. It's about merging a pen with either an apple or a pineapple, and then merging those together into more complicated structures. A _structure_ is either one of mentioned items (a pen, an apple or a pineapple) or a result of combining two structures. In the former case we say a structure is _basic_. The size of a basic structure is 1. The size of any other structure is equal to the sum of sizes of two structures merged into this one. Two structures can be merged if one of the following conditions holds true: A structure can be represented by a string of length equal to the size of the structure. A basic structure is represented by _"A"_ (if it's an apple) or by _"P"_ (if it's a pen or a pineapple). When a structure represented by a string w1 and a structure represented by a string w2 are merged together, they create a structure represented by a string w1w2 (strings are concatenated). The order of two merged structures matters because w1w2 may be different that w2w1. You are given T test cases, each with one string si consisting of characters _'A'_ and _'P'_. Your task is to check whether it's possible to get a structure represented by such a string. Print _"YES"_ or _"NO"_ in a separate line, without the quotes. The first line of the input contains an integer T (1 ≤ T ≤ 10) — the number of test cases. Each of the next T lines contains one string si (1 ≤ |si| ≤ 100), describing one test case. A string si consists of characters _'A'_ and _'P'_ only. For each test case in a separate line print _"YES"_ (without the quotes) if it's possible to get a structure represented by the given string, and _"NO"_ otherwise (without the quotes). In the first test case, one valid way is to merge a pen and a pineapple to get _"PP"_, then merge an apple and a pen to get _"AP"_, and finally merge two created structured in the order (_"PP"_, _"AP"_). The final structure is represented by _"PPAP"_, as required. ## Input The first line of the input contains an integer T (1 ≤ T ≤ 10) — the number of test cases.Each of the next T lines contains one string si (1 ≤ |si| ≤ 100), describing one test case. A string si consists of characters _'A'_ and _'P'_ only. ## Output For each test case in a separate line print _"YES"_ (without the quotes) if it's possible to get a structure represented by the given string, and _"NO"_ otherwise (without the quotes). [samples] ## Note In the first test case, one valid way is to merge a pen and a pineapple to get _"PP"_, then merge an apple and a pen to get _"AP"_, and finally merge two created structured in the order (_"PP"_, _"AP"_). The final structure is represented by _"PPAP"_, as required.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. Let $ S = \{s_1, s_2, \dots, s_T\} $ be the set of input strings, where each $ s_i \in \{A, P\}^* $. A *structure* is recursively defined as: - A *basic structure* is either "A" (apple) or "P" (pen or pineapple). - A *composite structure* is formed by concatenating two structures $ w_1 $ and $ w_2 $, resulting in $ w_1w_2 $. The *size* of a structure is the length of its string representation. Basic structures have size 1. Composite structures have size equal to the sum of the sizes of their components. **Constraints** 1. $ 1 \le T \le 10 $ 2. For each $ s_i \in S $: $ 1 \le |s_i| \le 100 $ and $ s_i \in \{A, P\}^* $ **Objective** For each string $ s_i $, determine whether it can be generated by a valid sequence of merges starting from basic structures ("A" or "P"). Output "YES" if possible, "NO" otherwise.

API Response (JSON)

{
  "problem": {
    "name": "B. Pen Pineapple Apple Pen",
    "description": {
      "content": "PPAP, which stands for Pen Pineapple Apple Pen, is an unusual song and dance that went viral in the Internet recently. It's about merging a pen with either an apple or a pineapple, and then merging th",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10113B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "PPAP, which stands for Pen Pineapple Apple Pen, is an unusual song and dance that went viral in the Internet recently. It's about merging a pen with either an apple or a pineapple, and then merging th...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ S = \\{s_1, s_2, \\dots, s_T\\} $ be the set of input strings, where each $ s_i \\in \\{A, P\\}^* $.  \n\nA *structure* is recur...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments