B. Fake Coins

Codeforces

IDCF10053B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Cristiano, as a leader of his team, works in the Security Lab of Central Bank of Real Mars (SLCBRM). They want to improve security of coins that Central Bank makes. They want to use string codes that will be carved on coins to determine whether the coin is fake or original. Cris's team suggested him an amazing idea for managing security of coins. They have a base string called B and a sequence of numbers called S. They select some characters from the base string to generate the security codes. If the i-th element of sequence is Si Then the i-th element of generated code is the Si-th character of B i.e.(B[Si]). As you can clearly see the length of the generated security string code is equal to the number of elements in the sequence. Their sequences are very similar to fibonacci numbers but their first and second elements are not always 1! They select two different numbers as first and second element of sequence (first number is always less than the second number). Then the third number of sequence is the sum of first and second numbers, the forth number is the sum of third and second number and so on. This process stops when a new element is greater than the length of the sequence. All elements of the sequence must be less than or equal to length of the base string. Cris read the algorithm of generating string codes and realized that it can be some problems with same string codes. He wants to know how many different string codes can be generated using his team's algorithm. Because Criastiano is busy with scoring for Real Mars Football team he asked you to solve his problem! First and only line of input contains the base string B(3 ≤ len(B) ≤ 1000). Base string is composed of digits, lowercase and uppercase Latin letter. Print one line containing the number of different security string codes that can be generated using Criastiano's team algorithm. In the first sample the codes are: 1 2 3 -> "abb" 1 3 4 -> "aba" 1 4 -> "aa" 2 3 -> "bb" 3 4 -> "ba" ## Input First and only line of input contains the base string B(3 ≤ len(B) ≤ 1000). Base string is composed of digits, lowercase and uppercase Latin letter. ## Output Print one line containing the number of different security string codes that can be generated using Criastiano's team algorithm. [samples] ## Note In the first sample the codes are: 1 2 3 -> "abb" 1 3 4 -> "aba" 1 4 -> "aa" 2 3 -> "bb" 3 4 -> "ba"

**Definitions** Let $ B \in \Sigma^* $ be the base string, where $ \Sigma = \{ \text{digits} \} \cup \{ \text{lowercase Latin letters} \} \cup \{ \text{uppercase Latin letters} \} $, and $ n = |B| $, with $ 3 \leq n \leq 1000 $. Let $ S = (s_1, s_2, \dots, s_k) $ be a sequence generated by the following recurrence: - $ s_1 = a $, $ s_2 = b $, where $ a, b \in \mathbb{Z}^+ $, $ 1 \leq a < b \leq n $, - For $ i \geq 3 $, $ s_i = s_{i-1} + s_{i-2} $, - The sequence stops at the first $ s_k $ such that $ s_k > n $; thus, all elements satisfy $ s_i \leq n $. Let $ C(S) $ be the security code generated from sequence $ S $: $$ C(S) = B[s_1 - 1]B[s_2 - 1]\cdots B[s_k - 1] \in \Sigma^k $$ where indexing of $ B $ is 0-based. **Constraints** 1. $ 3 \leq n \leq 1000 $ 2. $ 1 \leq a < b \leq n $ 3. For all $ i $, $ s_i \leq n $ 4. The sequence $ S $ is strictly increasing and defined by Fibonacci-like recurrence. **Objective** Compute the number of distinct strings $ C(S) $ that can be generated over all valid initial pairs $ (a, b) $ and their generated sequences $ S $.

API Response (JSON)

{
  "problem": {
    "name": "B. Fake Coins",
    "description": {
      "content": "Cristiano, as a leader of his team, works in the Security Lab of Central Bank of Real Mars (SLCBRM). They want to improve security of coins that Central Bank makes. They want to use string codes that ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10053B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Cristiano, as a leader of his team, works in the Security Lab of Central Bank of Real Mars (SLCBRM). They want to improve security of coins that Central Bank makes. They want to use string codes that ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ B \\in \\Sigma^* $ be the base string, where $ \\Sigma = \\{ \\text{digits} \\} \\cup \\{ \\text{lowercase Latin letters} \\} \\cup \\{ \\text{uppercase Latin letters} \\} $, and $ n = |B| $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments