K. Word order

Codeforces

IDCF10070K

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

— It is not about games, — Dragon decided that he should not tell Princess about trainings. — It is necessary to make him want to leave the Castles Valley forever. Princess sank into reverie again. Every day Prince goes into the world outside the Valley and comes back. What if he just does not see that many things in the big world which could change his life? — It is better say that nothing will change for him if he leaves the Valley, — Dragon broke off Princess' thoughts. Princess thought out long before, that she would tell Prince. But Dragon, after he listened to her narration, was sure it could not make Prince want to leave the Valley. He knew Prince quite well and realized that not all of Princess' arguments be treat by Prince as "pro"s. Let's consider that Princess' narrative is a sequence of arguments. For each argument Dragon knew, if it is "pro", "contra" or neutral. Dragon offered Princess to modify a sequence of arguments so that the last position of "contra" precedes the first position of "pro". Dragon was quite considerate and understood that it is difficult to Princess to significantly modify a sequence of arguments at once. For this reason he proposed her to modify a sequence step by step. In each step Princess can swap any two consecutive arguments. Of course, there was still plenty of time until evening (when Prince comes back from his work), but Dragon wants to modify a sequence with minimum number of steps. Your task is to compute the minimum number of the steps. The first line contains integer n (2 ≤ n ≤ 100) — number of Princess' arguments. The second line contains string of n symbols F, A and N, where F corresponds to argument "pro", A corresponds to argument "contra", and N corresponds to the neutral argument. It is guaranteed that the sequence contains at least one argument "pro" and at least one argument "contra". In the first line print the only integer — minimum number of steps, which are needed to put an original sequence in the suitable form. ## Input The first line contains integer n (2 ≤ n ≤ 100) — number of Princess' arguments.The second line contains string of n symbols F, A and N, where F corresponds to argument "pro", A corresponds to argument "contra", and N corresponds to the neutral argument.It is guaranteed that the sequence contains at least one argument "pro" and at least one argument "contra". ## Output In the first line print the only integer — minimum number of steps, which are needed to put an original sequence in the suitable form. [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 100 $, be the length of the sequence. Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence over $ \{F, A, N\} $, where: - $ F $ denotes "pro", - $ A $ denotes "contra", - $ N $ denotes neutral. Assume $ S $ contains at least one $ F $ and at least one $ A $. **Constraints** The goal is to rearrange $ S $ via adjacent swaps so that the last occurrence of $ A $ precedes the first occurrence of $ F $. **Objective** Compute the minimum number of adjacent swaps required to achieve a sequence $ S' $ such that: $$ \max\{ i \mid s'_i = A \} < \min\{ j \mid s'_j = F \} $$

API Response (JSON)

{
  "problem": {
    "name": "K. Word order",
    "description": {
      "content": "— It is not about games, — Dragon decided that he should not tell Princess about trainings. — It is necessary to make him want to leave the Castles Valley forever. Princess sank into reverie again. E",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10070K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "— It is not about games, — Dragon decided that he should not tell Princess about trainings. — It is necessary to make him want to leave the Castles Valley forever.\n\nPrincess sank into reverie again. E...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 100 $, be the length of the sequence.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence over $ \\{F, A, N\\} $, where:  \n- $ F $ denotes \"pro...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments