C. Check The Text

Codeforces

IDCF10226C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Roze has a special keyboard which consists only of 29 keys: -26 alphabetic a-z keys, which prints the 26 lowercase Latin letters. -"Space" key, which prints a single space. -"CapsLock" key, which converts the status of the letters keys from lowercase to uppercase and vice versa. The status initially is lowercase. -"Backspace" key, which deletes the last letter/space that was written on the screen. If Roze presses "Backspace" and there is nothing to delete on the screen, nothing will happen. Given the text that Roze had to print and the order of the keys she has pressed on the keyboard, check if Roze has printed the text correctly (including exactly one space between every two words). The first line contains an integer $n$ ($1 < n < 2000$), which is the number of the words in the text Roze has to print. Then n strings represent the text Roze has to print separated by exactly one space. Each string consists only of uppercase and lowercase Latin letters, and the total length of all strings less than 2000 The following line contains an integer $m$ ($1 < m < 2000$), which is the number of the keys Roze has pressed. Then m lines, each line contains a string that represents the key was pressed. It's guaranteed that the last key pressed is a letter and the first key is not a space key. Print a single line containing the result of checking. If Roze has printed the text correctly, print "Correct". Otherwise, print "Incorrect". ## Input The first line contains an integer $n$ ($1 < n < 2000$), which is the number of the words in the text Roze has to print.Then n strings represent the text Roze has to print separated by exactly one space.Each string consists only of uppercase and lowercase Latin letters, and the total length of all strings less than 2000The following line contains an integer $m$ ($1 < m < 2000$), which is the number of the keys Roze has pressed.Then m lines, each line contains a string that represents the key was pressed.It's guaranteed that the last key pressed is a letter and the first key is not a space key. ## Output Print a single line containing the result of checking.If Roze has printed the text correctly, print "Correct". Otherwise, print "Incorrect". [samples]

**Definitions** Let $ S \in \mathbb{Z}^+ $ be the size of the largest doll. Let $ X \in \mathbb{Z}^+ $ with $ X \geq 2 $ be the size reduction factor. **Constraints** $ 1 \leq S \leq 10^9 $, $ 2 \leq X \leq 10^9 $. **Objective** Find the maximum integer $ k $ such that there exists a sequence of doll sizes $ s_1 > s_2 > \dots > s_k $, where: - $ s_1 = S $, - $ s_{i+1} \leq \left\lfloor \frac{s_i}{X} \right\rfloor $ for all $ i \in \{1, 2, \dots, k-1\} $, - $ s_k \geq 1 $. Equivalently, compute the largest $ k $ satisfying: $$ S \cdot X^{-(k-1)} \geq 1 $$ or $$ k = \max \left\{ m \in \mathbb{Z}^+ \,\middle|\, \left\lfloor \frac{S}{X^{m-1}} \right\rfloor \geq 1 \right\} $$

API Response (JSON)

{
  "problem": {
    "name": "C. Check The Text",
    "description": {
      "content": "Roze has a special keyboard which consists only of 29 keys:  -26 alphabetic a-z keys, which prints the 26 lowercase Latin letters. -\"Space\" key, which prints a single space. -\"CapsLock\" key, which ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10226C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Roze has a special keyboard which consists only of 29 keys: \n\n-26 alphabetic a-z keys, which prints the 26 lowercase Latin letters.\n\n-\"Space\" key, which prints a single space.\n\n-\"CapsLock\" key, which ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S \\in \\mathbb{Z}^+ $ be the size of the largest doll.  \nLet $ X \\in \\mathbb{Z}^+ $ with $ X \\geq 2 $ be the size reduction factor.  \n\n**Constraints**  \n$ 1 \\leq S \\leq 10^9 $, ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments