J. Deciphering Oracles

Codeforces

IDCF10149J

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

China is considered a forefather of math in Asia. Chinese mathematicians developed the binary system, and they had notions of algebra, trigonometry, and geometry. The most ancient records of Chinese math go back to the Shang dynasty (1,600-1,050 BC). Mathematicians at that time recorded their findings in animal bones and turtle plastrons. These texts were known as "Oracle Bones". The office of the Investigators of Extraordinary Mysteries (IME, in Portuguese) is located in Anyang, capital of the Shang dynasty, and they have with them one of these oracles. The challenge to decipher this oracle was accepted by Marcio "the Indispensable" Himura. Marcio found that the oracle refers to a decimal system a bit different than the one we use. Working out on deciphering the oracle, he found that: Marcio was surprised by the last part of the oracle. He concluded that the Chinese had an algorithm that, given a number K, finds the position of K in the number system. Besides, they know how to find the number that occupies position K. Unfortunately, the investigators at IME have not yet found the oracles where such algorithms are described. Marcio is very curious to know how this can be done. He knows you wish to qualify for the ACM ICPC World Finals next year, and so he challenged you to solve this problem. The input has two integers, N and K. The output has two integers separated by a space. The first integer is the position of K in the number system. The second is the number that occurs at position K. ## Input The input has two integers, N and K. 1 ≤ N < 1018 1 ≤ K ≤ N ## Output The output has two integers separated by a space. The first integer is the position of K in the number system. The second is the number that occurs at position K. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ s $ be a non-empty string over lowercase English letters and single spaces, with no leading/trailing spaces and exactly one space between words. Let $ W = [w_1, w_2, \dots, w_m] $ be the list of words obtained by splitting $ s $ by spaces. Let $ \ell_i = |w_i| $ be the length of word $ w_i $, and define $ L = \sum_{i=1}^m \ell_i + (m - 1) $ as the total number of characters in $ s $ (including spaces). **Constraints** 1. $ 1 \le T \le 250 $ 2. $ 1 \le |s| \le 10^5 $ 3. Words are separated by exactly one space; no leading/trailing spaces. **Objective** Determine whether there exists an integer $ k \ge 1 $ such that $ s $ can be partitioned into $ r \ge 2 $ contiguous lines, each of identical *visual length* $ k $, satisfying: - Words cannot be split across lines. - Each line consists of one or more consecutive words from $ W $, separated by single spaces. - The total length of each line (i.e., sum of word lengths plus number of internal spaces in the line) equals $ k $. - Leading and trailing spaces in each line are ignored (but internal spaces between words are counted). Output "YES" if such a $ k $ exists; otherwise, output "NO".

API Response (JSON)

{
  "problem": {
    "name": "J. Deciphering Oracles",
    "description": {
      "content": "China is considered a forefather of math in Asia. Chinese mathematicians developed the binary system, and they had notions of algebra, trigonometry, and geometry. The most ancient records of Chinese m",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10149J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "China is considered a forefather of math in Asia. Chinese mathematicians developed the binary system, and they had notions of algebra, trigonometry, and geometry. The most ancient records of Chinese m...",
      "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, let $ s $ be a non-empty string over lowercase English letters and single spaces, with no leading/trailing...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments