K. Might and Magic

Codeforces

IDCF10081K

Time4000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

I was walking upstairs directly to the tower of Dragon, and step by step skies became closer and closer. I entered into a small room lighted by dozens of candles. Dragon sat at a big wooden table. The blood of his men was still flowing from my drawn sword right onto the parquet floor, answering all possible questions in advance. Dragon made a bet on magic. He grabbed a scroll and started to write a spell on it. A spell was a string consisting of only lowercase Latin letters «_a_», «_b_» and «_c_», which should have been written on a special magic scroll consequently, one letter after another, from left to right. Whenever the written string ended with two non-empty identical consecutive substrings, the spell corresponding to that string immediately triggered and the scroll collapsed. It should be noted that not every string, even if it ended with two non-empty identical consecutive substrings, was a spell. For example, a string «_bacabacbacabacabcab_» is not a spell, because at the moment when its prefix «_bacabacbac_» is written on a scroll, the corresponding spell triggers and the scroll disappears, leaving no way to add something else. It was known that the longer spells were stronger. Dragon was nervously writing one symbol after another, trying to create a spell strong enough to destroy me. Through the mask of indifference I saw fear and confusion in his eyes. What string are you trying to write down, Dragon? You'd better hurry. It's impolite to make a guest wait. There is only one test in this problem. In its only line the only integer 100000 is written. Output a string of length 105 that is not a spell and that can be written on a scroll to the very end. In the sample a correct string of length 7 is presented, even though there is no such test in the judging system. ## Input There is only one test in this problem. In its only line the only integer 100000 is written. ## Output Output a string of length 105 that is not a spell and that can be written on a scroll to the very end. [samples] ## Note In the sample a correct string of length 7 is presented, even though there is no such test in the judging system.

**Definitions** Let $ T \in \mathbb{Z}^+ $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ a_k, b_k \in \mathbb{Z} $ with $ 1 \leq a_k < b_k \leq 10^{18} $. - Let $ n_k \in \mathbb{Z} $ with $ 1 \leq n_k \leq 10^6 $. - Let $ p_k \in \mathbb{Z} $ be a prime with $ 2 \leq p_k < 200 $. - Let $ s_k \in \{0,1,\dots,9\}^{n_k} $ be the string of the first $ n_k $ decimal digits of $ \frac{a_k}{b_k} $ (after the decimal point, including leading zeros if necessary). **Constraints** 1. $ 1 \leq T \leq \text{unknown (but input-bound)} $ 2. $ 1 \leq a_k < b_k \leq 10^{18} $ 3. $ 1 \leq n_k \leq 10^6 $ 4. $ 2 \leq p_k < 200 $, $ p_k $ prime 5. $ s_k $ is the first $ n_k $ digits of the decimal expansion of $ \frac{a_k}{b_k} $, interpreted as a string of digits (no leading integer part; fractional part only, padded with zeros if needed to reach length $ n_k $). **Objective** For each test case $ k $, compute the number of contiguous substrings of $ s_k $ that represent integers divisible by $ p_k $. That is, count the number of pairs $ (i,j) $ with $ 1 \leq i \leq j \leq n_k $ such that the integer value of substring $ s_k[i:j] $ is divisible by $ p_k $.

API Response (JSON)

{
  "problem": {
    "name": "K. Might and Magic",
    "description": {
      "content": "I was walking upstairs directly to the tower of Dragon, and step by step skies became closer and closer. I entered into a small room lighted by dozens of candles. Dragon sat at a big wooden table. The",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10081K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "I was walking upstairs directly to the tower of Dragon, and step by step skies became closer and closer. I entered into a small room lighted by dozens of candles. Dragon sat at a big wooden table. The...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ a_k, b_k \\in \\mathbb{Z} $ with $ 1 \\leq a_k < b_k \\leq 10^{18} $.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments