{"problem":{"name":"C. Slava and tanks","description":{"content":"Slava plays his favorite game \"Peace Lightning\". Now he is flying a bomber on a very specific map. Formally, map is a checkered field of size 1 × _n_, the cells of which are numbered from 1 to _n_, i","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF877C"},"statements":[{"statement_type":"Markdown","content":"Slava plays his favorite game \"Peace Lightning\". Now he is flying a bomber on a very specific map.\n\nFormally, map is a checkered field of size 1 × _n_, the cells of which are numbered from 1 to _n_, in each cell there can be one or several tanks. Slava doesn't know the number of tanks and their positions, because he flies very high, but he can drop a bomb in any cell. All tanks in this cell will be damaged.\n\nIf a tank takes damage for the first time, it instantly moves to one of the neighboring cells (a tank in the cell _n_ can only move to the cell _n_ - 1, a tank in the cell 1 can only move to the cell 2). If a tank takes damage for the second time, it's counted as destroyed and never moves again. The tanks move only when they are damaged for the first time, they do not move by themselves.\n\nHelp Slava to destroy all tanks using as few bombs as possible.\n\n## Input\n\nThe first line contains a single integer _n_ (2 ≤ _n_ ≤ 100 000) — the size of the map.\n\n## Output\n\nIn the first line print _m_ — the minimum number of bombs Slava needs to destroy all tanks.\n\nIn the second line print _m_ integers _k_1, _k_2, ..., _k__m_. The number _k__i_ means that the _i_\\-th bomb should be dropped at the cell _k__i_.\n\nIf there are multiple answers, you can print any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Slava 正在玩他最喜欢的游戏《和平闪电》。现在他正在一个非常特殊的地图上驾驶轰炸机。\\n\\n形式上，地图是一个大小为 $1 × n$ 的棋盘格，单元格从 $1$ 到 $n$ 编号，每个单元格中可能有一个或多个坦克。Slava 不知道坦克的数量和位置，因为他飞得很高，但他可以在任意单元格投放炸弹，该单元格中的所有坦克都会受到伤害。\\n\\n如果一个坦克第一次受到伤害，它会立即移动到一个相邻的单元格（位于单元格 $n$ 的坦克只能移动到单元格 $n - 1$，位于单元格 $1$ 的坦克只能移动到单元格 $2$）。如果一个坦克第二次受到伤害，则它被算作被摧毁，且不再移动。坦克仅在第一次受到伤害时移动，不会自行移动。\\n\\n帮助 Slava 使用尽可能少的炸弹摧毁所有坦克。\\n\\n第一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$) —— 地图的大小。\\n\\n第一行输出 $m$ —— Slava 摧毁所有坦克所需的最少炸弹数量。\\n\\n第二行输出 $m$ 个整数 $k_1, k_2, ..., k_m$。数字 $k_i$ 表示第 $i$ 枚炸弹应投放到单元格 $k_i$。\\n\\n如果有多个答案，你可以输出任意一个。\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$) —— 地图的大小。\"},{\"iden\":\"output\",\"content\":\"第一行输出 $m$ —— Slava 摧毁所有坦克所需的最少炸弹数量。\\n\\n第二行输出 $m$ 个整数 $k_1, k_2, ..., k_m$。数字 $k_i$ 表示第 $i$ 枚炸弹应投放到单元格 $k_i$。\\n\\n如果有多个答案，你可以输出任意一个。\"},{\"iden\":\"examples\",\"content\":\"输入\\n2\\n输出\\n3\\n2 1 2 \\n\\n输入\\n3\\n输出\\n4\\n2 1 3 2 \"}]\n\n```json\n[{\"iden\":\"statement\",\"content\":\"Slava 正在玩他最喜欢的游戏《和平闪电》。现在他正在一个非常特殊的地图上驾驶轰炸机。\\n\\n形式上，地图是一个大小为 $1 × n$ 的棋盘格，单元格从 $1$ 到 $n$ 编号，每个单元格中可能有一个或多个坦克。Slava 不知道坦克的数量和位置，因为他飞得很高，但他可以在任意单元格投放炸弹，该单元格中的所有坦克都会受到伤害。\\n\\n如果一个坦克第一次受到伤害，它会立即移动到一个相邻的单元格（位于单元格 $n$ 的坦克只能移动到单元格 $n - 1$，位于单元格 $1$ 的坦克只能移动到单元格 $2$）。如果一个坦克第二次受到伤害，则它被算作被摧毁，且不再移动。坦克仅在第一次受到伤害时移动，不会自行移动。\\n\\n帮助 Slava 使用尽可能少的炸弹摧毁所有坦克。\\n\\n第一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$) —— 地图的大小。\\n\\n第一行输出 $m$ —— Slava 摧毁所有坦克所需的最少炸弹数量。\\n\\n第二行输出 $m$ 个整数 $k_1, k_2, ..., k_m$。数字 $k_i$ 表示第 $i$ 枚炸弹应投放到单元格 $k_i$。\\n\\n如果有多个答案，你可以输出任意一个。\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数 $n$ ($2 ≤ n ≤ 100 000$) —— 地图的大小。\"},{\"iden\":\"output\",\"content\":\"第一行输出 $m$ —— Slava 摧毁所有坦克所需的最少炸弹数量。\\n\\n第二行输出 $m$ 个整数 $k_1, k_2, ..., k_m$。数字 $k_i$ 表示第 $i$ 枚炸弹应投放到单元格 $k_i$。\\n\\n如果有多个答案，你可以输出任意一个。\"},{\"iden\":\"examples\",\"content\":\"输入\\n2\\n输出\\n3\\n2 1 2 \\n\\n输入\\n3\\n输出\\n4\\n2 1 3 2 \"}]\n```","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 100{,}000 $ be the length of the 1D grid.  \nLet $ T = \\{t_1, t_2, \\dots, t_m\\} $ be the set of tanks, each initially located in some cell $ c \\in \\{1, 2, \\dots, n\\} $.  \nEach tank is in one of two states: *undamaged* or *damaged (once)*.  \nA tank in cell $ i $, when damaged for the first time, moves to:  \n- $ i+1 $ if $ 1 \\leq i < n $,  \n- $ i-1 $ if $ i = n $.  \n\nA tank is destroyed upon the second damage.  \n\n**Constraints**  \n- Tanks are initially placed arbitrarily in cells $ 1 $ to $ n $.  \n- The adversary may place any number of tanks in any cell.  \n- Movement is deterministic upon first damage.  \n\n**Objective**  \nFind a sequence $ B = (b_1, b_2, \\dots, b_m) $, $ b_i \\in \\{1, 2, \\dots, n\\} $, minimizing $ m $, such that **regardless of initial tank positions and movement choices**, all tanks are destroyed (i.e., each tank is bombed exactly twice).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF877C","tags":["constructive algorithms"],"sample_group":[["2","3\n2 1 2"],["3","4\n2 1 3 2"]],"created_at":"2026-03-03 11:00:39"}}