A. Gotta Catch Em' All!

Codeforces

IDCF757A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Bash wants to become a Pokemon master one day. Although he liked a lot of Pokemon, he has always been fascinated by Bulbasaur the most. Soon, things started getting serious and his fascination turned into an obsession. Since he is too young to go out and catch Bulbasaur, he came up with his own way of catching a Bulbasaur. Each day, he takes the front page of the newspaper. He cuts out the letters one at a time, from anywhere on the front page of the newspaper to form the word _"Bulbasaur"_ (without quotes) and sticks it on his wall. Bash is very particular about case — the first letter of _"Bulbasaur"_ must be upper case and the rest must be lower case. By doing this he thinks he has caught one Bulbasaur. He then repeats this step on the left over part of the newspaper. He keeps doing this until it is not possible to form the word _"Bulbasaur"_ from the newspaper. Given the text on the front page of the newspaper, can you tell how many Bulbasaurs he will catch today? Note: **uppercase and lowercase letters are considered different.** ## Input Input contains a single line containing a string _s_ (1 ≤ |_s_| ≤ 105) — the text on the front page of the newspaper without spaces and punctuation marks. |_s_| is the length of the string _s_. The string _s_ contains lowercase and uppercase English letters, i.e. . ## Output Output a single integer, the answer to the problem. [samples] ## Note In the first case, you could pick: _**Bulb**b**asaur**_. In the second case, there is no way to pick even a single Bulbasaur. In the third case, you can rearrange the string to _**BulbasaurBulbasaur**addrgndgddgargndbb_ to get two words "_Bulbasaur_".

Bash 希望有一天成为宝可梦大师。虽然他喜欢很多宝可梦，但他一直最着迷于妙蛙种子。很快，事情变得严肃起来，他的着迷变成了痴迷。由于他太年轻，无法外出捕捉妙蛙种子，他想出了自己捕捉妙蛙种子的方法。每天，他取出报纸的头版。他逐个从头版的任何位置剪下字母，拼出单词 _"Bulbasaur"_（不含引号），并贴在墙上。Bash 对大小写非常讲究 —— _"Bulbasaur"_ 的第一个字母必须是大写，其余字母必须是小写。通过这样做，他认为自己捕捉到了一只妙蛙种子。然后他在报纸剩余的部分重复这一过程。他持续这样做，直到无法再从报纸中拼出单词 _"Bulbasaur"_。给定报纸头版上的文本，你能告诉他今天能捕捉到多少只妙蛙种子吗？注意：*大写字母和小写字母被视为不同*。输入包含一行，包含一个字符串 #cf_span[s] (#cf_span[1 ≤ |s| ≤ 105]) —— 报纸头版上的文本，不含空格和标点符号。#cf_span[|s|] 是字符串 #cf_span[s] 的长度。字符串 #cf_span[s] 包含小写和大写的英文字母，即。输出一个整数，表示问题的答案。在第一个例子中，你可以选择： _*Bulb*b*asaur*_. 在第二个例子中，无法拼出哪怕一只妙蛙种子。在第三个例子中，你可以将字符串重新排列为 _*BulbasaurBulbasaur*addrgndgddgargndbb_，从而得到两个 "_Bulbasaur"_。 ## Input 输入包含一行，包含一个字符串 #cf_span[s] (#cf_span[1 ≤ |s| ≤ 105]) —— 报纸头版上的文本，不含空格和标点符号。#cf_span[|s|] 是字符串 #cf_span[s] 的长度。字符串 #cf_span[s] 包含小写和大写的英文字母，即。 ## Output 输出一个整数，表示问题的答案。 [samples] ## Note 在第一个例子中，你可以选择： _*Bulb*b*asaur*_.在第二个例子中，无法拼出哪怕一只妙蛙种子。在第三个例子中，你可以将字符串重新排列为 _*BulbasaurBulbasaur*addrgndgddgargndbb_，从而得到两个 "_Bulbasaur"_。

**Definitions** Let $ s $ be a string of length $ |s| $, composed of uppercase and lowercase English letters. Let $ w = \text{"Bulbasaur"} $ be the target word, with character multiset $ M_w $: - $ B: 1 $, $ u: 2 $, $ l: 1 $, $ b: 1 $, $ a: 2 $, $ s: 1 $, $ r: 1 $ Let $ M_s $ be the multiset of characters in $ s $. **Constraints** $ 1 \leq |s| \leq 10^5 $ Characters in $ s $ are from the set $ \{A,\dots,Z\} \cup \{a,\dots,z\} $ **Objective** Compute the maximum integer $ k $ such that $ M_s $ contains at least $ k \cdot M_w $, i.e., for each character $ c $ in $ w $: $$ \text{count}_s(c) \geq k \cdot \text{count}_w(c) $$ Then: $$ k = \min_{c \in \{B,u,l,b,a,s,r\}} \left\lfloor \frac{\text{count}_s(c)}{\text{count}_w(c)} \right\rfloor $$

Samples

Input #1

Bulbbasaur

Output #1

Input #2

Output #2

Input #3

aBddulbasaurrgndgbualdBdsagaurrgndbb

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Gotta Catch Em' All!",
    "description": {
      "content": "Bash wants to become a Pokemon master one day. Although he liked a lot of Pokemon, he has always been fascinated by Bulbasaur the most. Soon, things started getting serious and his fascination turned ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF757A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bash wants to become a Pokemon master one day. Although he liked a lot of Pokemon, he has always been fascinated by Bulbasaur the most. Soon, things started getting serious and his fascination turned ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Bash 希望有一天成为宝可梦大师。虽然他喜欢很多宝可梦，但他一直最着迷于妙蛙种子。很快，事情变得严肃起来，他的着迷变成了痴迷。由于他太年轻，无法外出捕捉妙蛙种子，他想出了自己捕捉妙蛙种子的方法。\n\n每天，他取出报纸的头版。他逐个从头版的任何位置剪下字母，拼出单词 _\"Bulbasaur\"_（不含引号），并贴在墙上。Bash 对大小写非常讲究 —— _\"Bulbasaur\"_ 的第一个字母必须是大...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s $ be a string of length $ |s| $, composed of uppercase and lowercase English letters.  \nLet $ w = \\text{\"Bulbasaur\"} $ be the target word, with character multiset $ M_w $:  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments