D. Walking Between Houses

Codeforces

IDCF1015D

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgreedy

English · Original

Chinese · Translation

Formal · Original

There are $n$ houses in a row. They are numbered from $1$ to $n$ in order from left to right. Initially you are in the house $1$. You have to perform $k$ moves to other house. In one move you go from your current house to some other house. You can't stay where you are (i.e., in each move the new house differs from the current house). If you go from the house $x$ to the house $y$, the total distance you walked increases by $|x-y|$ units of distance, where $|a|$ is the absolute value of $a$. It is possible to visit the same house multiple times (but you can't visit the same house in sequence). Your goal is to walk exactly $s$ units of distance in total. If it is impossible, print "_NO_". Otherwise print "_YES_" and any of the ways to do that. Remember that you should do exactly $k$ moves. ## Input The first line of the input contains three integers $n$, $k$, $s$ ($2 \le n \le 10^9$, $1 \le k \le 2 \cdot 10^5$, $1 \le s \le 10^{18}$) — the number of houses, the number of moves and the total distance you want to walk. ## Output If you cannot perform $k$ moves with total walking distance equal to $s$, print "_NO_". Otherwise print "_YES_" on the first line and then print exactly $k$ integers $h_i$ ($1 \le h_i \le n$) on the second line, where $h_i$ is the house you visit on the $i$\-th move. For each $j$ from $1$ to $k-1$ the following condition should be satisfied: $h_j \ne h_{j + 1}$. Also $h_1 \ne 1$ should be satisfied. [samples]

有一排 $n$ 座房子，从左到右编号为 $1$ 到 $n$。最初你位于房子 $1$。你需要进行 $k$ 次移动到其他房子。每次移动，你从当前房子移动到另一个房子。你不能停留在原地（即每次移动后的新房子必须与当前房子不同）。如果你从房子 $x$ 移动到房子 $y$，你行走的总距离增加 $| x -y |$ 单位，其中 $| a |$ 表示 $a$ 的绝对值。你可以多次访问同一座房子（但不能连续两次访问同一座房子）。你的目标是恰好行走 $s$ 单位的总距离。如果不可能，输出 "_NO_"。否则输出 "_YES_" 以及一种可行的方案。请记住，你必须恰好进行 $k$ 次移动。输入的第一行包含三个整数 $n$, $k$, $s$ ($2 lt.eq n lt.eq 10^9$, $1 lt.eq k lt.eq 2 dot.op 10^5$, $1 lt.eq s lt.eq 10^(18)$) —— 分别表示房子数量、移动次数和希望行走的总距离。如果你无法进行 $k$ 次移动且总行走距离恰好为 $s$，请输出 "_NO_"。否则，第一行输出 "_YES_"，第二行输出恰好 $k$ 个整数 $h_i$ ($1 lt.eq h_i lt.eq n$)，其中 $h_i$ 表示第 $i$ 次移动所访问的房子。对于每个 $j$ 从 $1$ 到 $k -1$，需满足 $h_j != h_{j + 1}$。同时需满足 $h_1 != 1$。 ## Input 输入的第一行包含三个整数 $n$, $k$, $s$ ($2 lt.eq n lt.eq 10^9$, $1 lt.eq k lt.eq 2 dot.op 10^5$, $1 lt.eq s lt.eq 10^(18)$) —— 分别表示房子数量、移动次数和希望行走的总距离。 ## Output 如果你无法进行 $k$ 次移动且总行走距离恰好为 $s$，请输出 "_NO_"。否则，第一行输出 "_YES_"，第二行输出恰好 $k$ 个整数 $h_i$ ($1 lt.eq h_i lt.eq n$)，其中 $h_i$ 表示第 $i$ 次移动所访问的房子。对于每个 $j$ 从 $1$ 到 $k -1$，需满足 $h_j != h_{j + 1}$。同时需满足 $h_1 != 1$。 [samples]

**Definitions** Let $ n, k, s \in \mathbb{Z}^+ $ with $ n \geq 2 $, $ k \geq 1 $, $ s \geq 1 $. Let $ H = (h_1, h_2, \dots, h_k) $ be a sequence of house indices, where $ h_i \in \{1, 2, \dots, n\} $. Initial position: $ h_0 = 1 $. **Constraints** 1. $ \forall i \in \{1, \dots, k\} $, $ h_i \ne h_{i-1} $ (no staying in place). 2. $ \sum_{i=1}^k |h_i - h_{i-1}| = s $ (total distance equals $ s $). 3. $ \forall i \in \{1, \dots, k\} $, $ 1 \leq h_i \leq n $. **Objective** Determine whether there exists a sequence $ H $ satisfying the above constraints. If yes, output "YES" and any such sequence $ H $. If no, output "NO".

Samples

Input #1

10 2 15

Output #1

YES
10 4

Input #2

10 9 45

Output #2

YES
10 1 10 1 2 1 2 1 6

Input #3

10 9 81

Output #3

YES
10 1 10 1 10 1 10 1 10

Input #4

10 9 82

Output #4

NO

API Response (JSON)

{
  "problem": {
    "name": "D. Walking Between Houses",
    "description": {
      "content": "There are $n$ houses in a row. They are numbered from $1$ to $n$ in order from left to right. Initially you are in the house $1$. You have to perform $k$ moves to other house. In one move you go from",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1015D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $n$ houses in a row. They are numbered from $1$ to $n$ in order from left to right. Initially you are in the house $1$.\n\nYou have to perform $k$ moves to other house. In one move you go from...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有一排 $n$ 座房子，从左到右编号为 $1$ 到 $n$。最初你位于房子 $1$。\n\n你需要进行 $k$ 次移动到其他房子。每次移动，你从当前房子移动到另一个房子。你不能停留在原地（即每次移动后的新房子必须与当前房子不同）。如果你从房子 $x$ 移动到房子 $y$，你行走的总距离增加 $| x -y |$ 单位，其中 $| a |$ 表示 $a$ 的绝对值。你可以多次访问同一座房子（但不能连续两...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k, s \\in \\mathbb{Z}^+ $ with $ n \\geq 2 $, $ k \\geq 1 $, $ s \\geq 1 $.  \nLet $ H = (h_1, h_2, \\dots, h_k) $ be a sequence of house indices, where $ h_i \\in \\{1, 2, \\dots, n\\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments