K. KazaQ's Socks

Codeforces

IDCF10225K

Time1000ms

Memory128MB

Difficulty—

English · Original

Formal · Original

_KazaQ_ wears socks every day. Before the first day, he has $n$ pairs of socks in his closet, labeled from $1$ to $n$. Every morning, he would put on a pair of socks with the smallest label in the closet. Every evening, he would take off socks and put them into a basket. After that, if there are $(n -1)$ pairs of old socks in the basket, lazy _KazaQ_ will have to wash them. These socks can be dried out on the next day and then will be put back to the closet in the evening. _KazaQ_ would like to know which pair of socks he would wear on the $k$-th day. The input contains multiple (about $2000$) test cases. Each test case in only one line contains two integers $n$, $k$ ($2 <= n <= 10^9$, $1 <= k <= 10^(18)$). For each test case, output "_Case #x: y_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case. ## Input The input contains multiple (about $2000$) test cases.Each test case in only one line contains two integers $n$, $k$ ($2 <= n <= 10^9$, $1 <= k <= 10^(18)$). ## Output For each test case, output "_Case #x: y_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y$ denotes the answer to the corresponding case. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the initial number of sock pairs, labeled $ 1 $ to $ n $. Let $ k \in \mathbb{Z} $ be the target day. **Constraints** 1. $ 2 \leq n \leq 10^9 $ 2. $ 1 \leq k \leq 10^{18} $ **Process** - Each morning, _KazaQ_ wears the sock pair with the smallest label in the closet. - Each evening, worn socks are placed in a basket. - When the basket contains $ n-1 $ pairs, they are washed and returned to the closet the next evening. - Socks are reused in increasing order of label, cycling after all $ n $ pairs have been used. **Objective** Find the label of the sock pair worn on day $ k $. **Pattern Analysis** The sock usage follows a periodic cycle: - Days $ 1 $ to $ n $: wear pairs $ 1, 2, \dots, n $ (first full cycle). - After day $ n $, every $ n-1 $ days, the set $ \{1, 2, \dots, n-1\} $ is reused (since pair $ n $ is held out until washed). Thus, after day $ n $, the cycle length is $ n-1 $, repeating the sequence $ 1, 2, \dots, n-1 $. **Formula** Let $ k' = k - n $. - If $ k \leq n $, answer is $ k $. - Else, answer is $ ((k' - 1) \bmod (n - 1)) + 1 $. **Final Expression** $$ y = \begin{cases} k & \text{if } k \leq n \\ ((k - n - 1) \bmod (n - 1)) + 1 & \text{if } k > n \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "K. KazaQ's Socks",
    "description": {
      "content": "_KazaQ_ wears socks every day. Before the first day, he has $n$ pairs of socks in his closet, labeled from $1$ to $n$. Every morning, he would put on a pair of socks with the smallest label in the c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10225K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_KazaQ_ wears socks every day.\n\nBefore the first day, he has $n$ pairs of socks in his closet, labeled from $1$ to $n$.\n\nEvery morning, he would put on a pair of socks with the smallest label in the c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the initial number of sock pairs, labeled $ 1 $ to $ n $.  \nLet $ k \\in \\mathbb{Z} $ be the target day.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^9 $  \n2...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments