B. Our Tanya is Crying Out Loud

Codeforces

IDCF940B

Time1000ms

Memory256MB

Difficulty—

dpgreedy

English · Original

Chinese · Translation

Formal · Original

_Right now she actually isn't. But she will be, if you don't solve this problem._ You are given integers _n_, _k_, _A_ and _B_. There is a number _x_, which is initially equal to _n_. You are allowed to perform two types of operations: 1. Subtract 1 from _x_. This operation costs you _A_ coins. 2. Divide _x_ by _k_. Can be performed only if _x_ is divisible by _k_. This operation costs you _B_ coins. What is the minimum amount of coins you have to pay to make _x_ equal to 1? ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 2·109). The second line contains a single integer _k_ (1 ≤ _k_ ≤ 2·109). The third line contains a single integer _A_ (1 ≤ _A_ ≤ 2·109). The fourth line contains a single integer _B_ (1 ≤ _B_ ≤ 2·109). ## Output Output a single integer — the minimum amount of coins you have to pay to make _x_ equal to 1. [samples] ## Note In the first testcase, the optimal strategy is as follows: * Subtract 1 from _x_ (9 → 8) paying 3 coins. * Divide _x_ by 2 (8 → 4) paying 1 coin. * Divide _x_ by 2 (4 → 2) paying 1 coin. * Divide _x_ by 2 (2 → 1) paying 1 coin. The total cost is 6 coins. In the second test case the optimal strategy is to subtract 1 from _x_ 4 times paying 8 coins in total.

_Right now she actually isn't. But she will be, if you don't solve this problem._ You are given integers $n$, $k$, $A$ and $B$. There is a number $x$, which is initially equal to $n$. You are allowed to perform two types of operations: The first line contains a single integer $n$ ($1 ≤ n ≤ 2·10^9$). The second line contains a single integer $k$ ($1 ≤ k ≤ 2·10^9$). The third line contains a single integer $A$ ($1 ≤ A ≤ 2·10^9$). The fourth line contains a single integer $B$ ($1 ≤ B ≤ 2·10^9$). Output a single integer — the minimum amount of coins you have to pay to make $x$ equal to $1$. In the first testcase, the optimal strategy is as follows: The total cost is $6$ coins. In the second test case the optimal strategy is to subtract 1 from $x$ $4$ times paying $8$ coins in total. ## Input The first line contains a single integer $n$ ($1 ≤ n ≤ 2·10^9$).The second line contains a single integer $k$ ($1 ≤ k ≤ 2·10^9$).The third line contains a single integer $A$ ($1 ≤ A ≤ 2·10^9$).The fourth line contains a single integer $B$ ($1 ≤ B ≤ 2·10^9$). ## Output Output a single integer — the minimum amount of coins you have to pay to make $x$ equal to $1$. [samples] ## Note In the first testcase, the optimal strategy is as follows: Subtract 1 from $x$ ($9 → 8$) paying 3 coins. Divide $x$ by 2 ($8 → 4$) paying 1 coin. Divide $x$ by 2 ($4 → 2$) paying 1 coin. Divide $x$ by 2 ($2 → 1$) paying 1 coin. The total cost is $6$ coins.In the second test case the optimal strategy is to subtract 1 from $x$ $4$ times paying $8$ coins in total.

**Definitions** Let $ n, k, A, B \in \mathbb{Z}^+ $ be given integers. Let $ x \in \mathbb{Z}^+ $ be a variable initially set to $ n $. **Operations** You may perform: 1. $ x \leftarrow x - 1 $, costing $ A $ coins (if $ x > 1 $). 2. $ x \leftarrow \left\lfloor \frac{x}{k} \right\rfloor $, costing $ B $ coins (if $ x \geq k $). **Objective** Find the minimum total cost to reduce $ x $ from $ n $ to $ 1 $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Our Tanya is Crying Out Loud",
    "description": {
      "content": "_Right now she actually isn't. But she will be, if you don't solve this problem._ You are given integers _n_, _k_, _A_ and _B_. There is a number _x_, which is initially equal to _n_. You are allowed",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF940B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Right now she actually isn't. But she will be, if you don't solve this problem._\n\nYou are given integers _n_, _k_, _A_ and _B_. There is a number _x_, which is initially equal to _n_. You are allowed...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_Right now she actually isn't. But she will be, if you don't solve this problem._\n\nYou are given integers $n$, $k$, $A$ and $B$. There is a number $x$, which is initially equal to $n$. You are allowed...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k, A, B \\in \\mathbb{Z}^+ $ be given integers.  \nLet $ x \\in \\mathbb{Z}^+ $ be a variable initially set to $ n $.  \n\n**Operations**  \nYou may perform:  \n1. $ x \\leftarrow x -...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments