[USACO23OPEN] FEB B

Luogu

IDLGP9183

Time2000ms

Memory256MB

DifficultyP4

数学贪心USACO2023分类讨论

Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out over $N$ text messages. Their conversation can be represented by a string $S$ of length $N$ where $S_i$ is either `B` or `E`, meaning the $i$ th message was sent by Bessie or Elsie, respectively. However, Farmer John hears of the plan and attempts to intercept their conversation. Thus, some letters of $S$ are `F`, meaning Farmer John obfuscated the message and the sender is unknown. The **excitement level** of a non-obfuscated conversation is the number of times a cow double-sends - that is, the number of occurrences of substring `BB` or `EE` in $S$. You want to find the excitement level of the original message, but you don’t know which of Farmer John’s messages were actually Bessie’s / Elsie’s. Over all possibilities, output all possible excitement levels of $S$. ## Input The first line will consist of one integer $N$. The next line contains $S$. ## Output First output $K$, the number of distinct excitement levels possible. On the next $K$ lines, output the excitement levels, in increasing order. [samples] ## Note $1\le N\le 2\cdot 10^5$. - Inputs 4-8: $N\le 10$. - Inputs 9-20: No additional constraints.

Samples

Input #1

4
BEEF

Output #1

2
1
2

Input #2

9
FEBFEBFEB

Output #2

2
2
3

Input #3

10
BFFFFFEBFE

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO23OPEN] FEB B",
    "description": {
      "content": "Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out over $N$ text messages. Their conversation can be represented by a string $S$ of length $N$ where $S_i$ is either `B` o",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9183"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bessie and Elsie are plotting to overthrow Farmer John at last! They plan it out\nover $N$ text messages. Their conversation can be\nrepresented by a string $S$ of length $N$ where $S_i$ is either `B` o...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments