A. Toy Army

Codeforces

IDCF84A

Time2000ms

Memory256MB

Difficulty—

mathnumber theory

English · Original

Chinese · Translation

Formal · Original

The hero of our story, Valera, and his best friend Arcady are still in school, and therefore they spend all the free time playing turn-based strategy "GAGA: Go And Go Again". The gameplay is as follows. There are two armies on the playing field each of which consists of _n_ men (_n_ is always even). The current player specifies for each of her soldiers an enemy's soldier he will shoot (a target) and then all the player's soldiers shot simultaneously. This is a game world, and so each soldier shoots perfectly, that is he absolutely always hits the specified target. If an enemy soldier is hit, he will surely die. It may happen that several soldiers had been indicated the same target. Killed soldiers do not participate in the game anymore. The game "GAGA" consists of three steps: first Valera makes a move, then Arcady, then Valera again and the game ends. You are asked to calculate the maximum total number of soldiers that may be killed during the game. ## Input The input data consist of a single integer _n_ (2 ≤ _n_ ≤ 108, _n_ is even). Please note that before the game starts there are 2_n_ soldiers on the fields. ## Output Print a single number — a maximum total number of soldiers that could be killed in the course of the game in three turns. [samples] ## Note The first sample test: 1) Valera's soldiers 1 and 2 shoot at Arcady's soldier 1. 2) Arcady's soldier 2 shoots at Valera's soldier 1. 3) Valera's soldier 1 shoots at Arcady's soldier 2. There are 3 soldiers killed in total: Valera's soldier 1 and Arcady's soldiers 1 and 2.

我们故事的主角瓦莱拉和他的最好的朋友阿尔卡迪仍在上学，因此他们把所有空闲时间都花在了回合制策略游戏《GAGA：去而又去》上。游戏规则如下：游戏场上各有两支军队，每支军队由 #cf_span[n] 名士兵组成（#cf_span[n] 始终为偶数）。当前玩家为自己的每名士兵指定一名敌方士兵作为射击目标，然后所有玩家的士兵同时开火。这是一个游戏世界，因此每名士兵射击精准，即绝对总是击中指定的目标。如果一名敌方士兵被击中，他一定会死亡。可能多个士兵被指定攻击同一个目标。被杀死的士兵不再参与游戏。游戏《GAGA》共进行三步：首先瓦莱拉行动，然后是阿尔卡迪，接着是瓦莱拉再次行动，之后游戏结束。你需要计算在游戏中可能被杀死的士兵总数的最大值。输入数据仅包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 108]，#cf_span[n] 为偶数）。请注意，在游戏开始前，场上共有 #cf_span[2n] 名士兵。请输出一个数字——在三轮行动中可能被杀死的士兵总数的最大值。 ## Input 输入数据仅包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 108]，#cf_span[n] 为偶数）。请注意，在游戏开始前，场上共有 #cf_span[2n] 名士兵。 ## Output 请输出一个数字——在三轮行动中可能被杀死的士兵总数的最大值。 [samples] ## Note 第一个样例测试： 1) 瓦莱拉的士兵 1 和 2 射击阿尔卡迪的士兵 1。 2) 阿尔卡迪的士兵 2 射击瓦莱拉的士兵 1。 3) 瓦莱拉的士兵 1 射击阿尔卡迪的士兵 2。总共死亡了 3 名士兵：瓦莱拉的士兵 1 和阿尔卡迪的士兵 1 和 2。

**Definitions** Let $ n \in \mathbb{Z} $ be a given even integer ($ 2 \leq n \leq 10^8 $). Let $ V_0 = n $ be the initial number of Valera’s soldiers. Let $ A_0 = n $ be the initial number of Arcady’s soldiers. The game proceeds in three turns: 1. **Turn 1 (Valera)**: Valera selects targets for each of his $ V_0 $ soldiers among Arcady’s $ A_0 $ soldiers. 2. **Turn 2 (Arcady)**: Arcady selects targets for each of his remaining $ A_1 $ soldiers among Valera’s remaining $ V_1 $ soldiers. 3. **Turn 3 (Valera)**: Valera selects targets for each of his remaining $ V_2 $ soldiers among Arcady’s remaining $ A_2 $ soldiers. After each turn, all targeted enemy soldiers are killed simultaneously. Let $ K $ be the total number of soldiers killed over the three turns. **Constraints** - $ n $ is even. - At each turn, each living soldier must shoot exactly one enemy soldier (possibly targeting the same soldier as others). - A soldier can only shoot if alive at the start of their turn. - Killed soldiers are removed and do not participate in subsequent turns. **Objective** Maximize the total number of soldiers killed: $$ K = k_1 + k_2 + k_3 $$ where: - $ k_1 $: number of Arcady’s soldiers killed in Turn 1, - $ k_2 $: number of Valera’s soldiers killed in Turn 2, - $ k_3 $: number of Arcady’s soldiers killed in Turn 3. Subject to: - $ 0 \leq k_1 \leq \min(n, n) = n $, - $ 0 \leq k_2 \leq \min(n - k_1, n) = n - k_1 $, - $ 0 \leq k_3 \leq \min(n - k_1, n - k_2) $. **Goal**: Find $ \max K = \max(k_1 + k_2 + k_3) $.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Toy Army",
    "description": {
      "content": "The hero of our story, Valera, and his best friend Arcady are still in school, and therefore they spend all the free time playing turn-based strategy \"GAGA: Go And Go Again\". The gameplay is as follow",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF84A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The hero of our story, Valera, and his best friend Arcady are still in school, and therefore they spend all the free time playing turn-based strategy \"GAGA: Go And Go Again\". The gameplay is as follow...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们故事的主角瓦莱拉和他的最好的朋友阿尔卡迪仍在上学，因此他们把所有空闲时间都花在了回合制策略游戏《GAGA：去而又去》上。游戏规则如下：\n\n游戏场上各有两支军队，每支军队由 #cf_span[n] 名士兵组成（#cf_span[n] 始终为偶数）。当前玩家为自己的每名士兵指定一名敌方士兵作为射击目标，然后所有玩家的士兵同时开火。这是一个游戏世界，因此每名士兵射击精准，即绝对总是击中指定的目标。如...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be a given even integer ($ 2 \\leq n \\leq 10^8 $).  \nLet $ V_0 = n $ be the initial number of Valera’s soldiers.  \nLet $ A_0 = n $ be the initial number of Ar...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments