At Most 3 (Contestant ver.)

AtCoder

IDabc251_d

Time2000ms

Memory256MB

Difficulty—

You are given an integer $W$. You are going to prepare some weights so that all of the conditions below are satisfied. * The number of weights is between $1$ and $300$, inclusive. * Each weight has a mass of positive integer not exceeding $10^6$. * Every integer between $1$ and $W$, inclusive, is a **good integer**. Here, a positive integer $n$ is said to be a good integer if the following condition is satisfied: * We can choose **at most $3$** different weights from the prepared weights with a total mass of $n$. Print a combination of weights that satisfies the conditions. ## Constraints * $1 \leq W \leq 10^6$ * $W$ is an integer. ## Input Input is given from Standard Input in the following format: $W$ [samples]

Samples

Input #1

Output #1

3
1 2 3

In the output above, $3$ weights with masses $1$, $2$, and $3$ are prepared.  
This output satisfies the conditions. Especially, regarding the $3$\-rd condition, we can confirm that every integer between $1$ and $W$, inclusive, is a good integer.

*   If we choose only the $1$\-st weight, it has a total mass of $1$.
*   If we choose only the $2$\-nd weight, it has a total mass of $2$.
*   If we choose only the $3$\-rd weight, it has a total mass of $3$.
*   If we choose the $1$\-st and the $3$\-rd weights, they have a total mass of $4$.
*   If we choose the $2$\-nd and the $3$\-rd weights, they have a total mass of $5$.
*   If we choose the $1$\-st, the $2$\-nd, and the $3$\-rd weights, they have a total mass of $6$.

Input #2

Output #2

6
2 5 1 2 5 1

You may prepare multiple weights with the same mass.

API Response (JSON)

{
  "problem": {
    "name": "At Most 3 (Contestant ver.)",
    "description": {
      "content": "You are given an integer $W$.   You are going to prepare some weights so that all of the conditions below are satisfied. *   The number of weights is between $1$ and $300$, inclusive. *   Each weight",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc251_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer $W$.  \nYou are going to prepare some weights so that all of the conditions below are satisfied.\n\n*   The number of weights is between $1$ and $300$, inclusive.\n*   Each weight...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments