[ICPC 2020 WF] Trailing Digits

Luogu

IDLGP8140

Time1000ms

Memory256MB

DifficultyP6

2020O2优化ICPCWF

A large shipment of doodads has just arrived, and each doodad has a suggested retail price of $b$ cents. You've noticed that consumers are much more likely to purchase goods when most of the trailing digits are the same. For example, items are more likely to be priced at $99$ cents rather than $57$ cents. So to make your goods more appealing, you've decided to sell your goods in bundles. To make a bundle, you choose a positive integer $k$, and sell $k$ doodads for $k \times b$ cents. With an appropriate choice of $k$ you can have a more pleasing price. For example, selling $57$-cent doodads in bundles of size $7$ means that each bundle sells for $399$ cents, which has two trailing $9$s, rather than no trailing $9$s of $57$. This idea of trailing $9$s can be generalized to any other trailing digit: bundles of $692$ $57$-cent doodads sell for $39\,444$ cents (three trailing $4$s) and bundles of one million doodads sell for $57\,000\,000$ cents (six trailing $0$s). After a little thought, you realize that you do not want to make your bundles too large---not only can the price be excessive, but who really needs several million doodads? For any type of doodad, your marketing department has a maximum bundle price of $a$. Given the price of a doodad, the desired trailing digit, and the maximum price of a bundle, write a program that optimizes the trailing digits. ## Input Input consists of a single line containing three integers $b$, $d$, and $a$, where $b$ ($1 \leq b < 10^{6}$) is the price of a doodad in cents, $d$ ($0 \leq d \leq 9$) is the desired trailing digit, and $a$ ($b \leq a < 10^{10\,000}$) is the maximum price of a bundle. ## Output Output the maximum number of consecutive occurrences of $d$ that can appear at the end of a bundle price, given that the price of the bundle cannot exceed $a$. [samples] ## Background ICPC2020 WF M

Samples

Input #1

57 9 1000

Output #1

Input #2

57 4 40000

Output #2

Input #3

57 4 39000

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2020 WF] Trailing Digits",
    "description": {
      "content": "A large shipment of doodads has just arrived, and each doodad has a suggested retail price of $b$ cents. You've noticed that consumers are much more likely to purchase goods when most of the trailing ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8140"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A large shipment of doodads has just arrived, and each doodad has a suggested retail price of $b$ cents. You've noticed that consumers are much more likely to purchase goods when most of the trailing ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments