C. Divide

Codeforces

IDCF10227C

Time3000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Đằng sau sự thành công của Bitcoin, không thể không kể đến công nghệ _Blockchain_. Blockchain hoạt động dựa trên các khối liên kết với nhau tạo thành một chuỗi. Điều đặc biệt ở đây chính là blockchain có độ bảo mật rất cao, không thể thay đổi. Hacker b21 đã gây chấn động toàn cầu khi đã tìm ra cách hack được Blockchain. Anh đã mã hóa toàn bộ các block trở thành một số N. Số N này phải thỏa mãn điều kiện sau: - Là một số tự nhiên. - Chia hết cho x. - thuộc khoảng [A, B]. - UCLN của chữ số thứ i tính từ phải qua trái và i phải bằng 1. (Ví dụ: 321 không thỏa mãn vì UCLN(1, 1) = 1, UCLN(2, 2) = 2, UCLN(3, 3) = 3 nhưng 231 thỏa mãn vì UCLN(1, 1) = 1, UCLN(3, 2) = 1, UCLN(2, 3) = 1) . - Bao gồm các chữ số cho trước Các bạn hãy giúp b21 tìm ra số lượng các số như thế nhé. Dòng đầu tiên chứa ba số nguyên A, B, X. Dòng thứ hai có xâu S chứa các chữ số 0..9 theo thứ tự tăng dần là các số có trong N Chứa duy nhất 1 số nguyên là phần dư của phép chia kết quả bài toán cho 109 + 7 B ≤ A 10% số test ứng với A, B, X ≤ 103 30% số test ứng với A, B ≤ 106, X ≤ 105 30% số test ứng với A, B, X ≤ 1011 30% số test ứng với A, B ≤ 10100, X ≤ 105 Giải thích test 1: 2, 4, 8, 12, 14, 18 Giải thích test 2: 3, 6, 12, 18 ## Input Dòng đầu tiên chứa ba số nguyên A, B, X.Dòng thứ hai có xâu S chứa các chữ số 0..9 theo thứ tự tăng dần là các số có trong N ## Output Chứa duy nhất 1 số nguyên là phần dư của phép chia kết quả bài toán cho 109 + 7 [samples] ## Scoring B ≤ A10% số test ứng với A, B, X ≤ 10330% số test ứng với A, B ≤ 106, X ≤ 10530% số test ứng với A, B, X ≤ 101130% số test ứng với A, B ≤ 10100, X ≤ 105 ## Note Giải thích test 1: 2, 4, 8, 12, 14, 18Giải thích test 2: 3, 6, 12, 18

**Definitions** Let $ n, P, Q \in \mathbb{Z} $ with $ 1 \le n \le 2000 $, $ 0 \le P, Q \le 10^5 $. Let $ X = \{x_1, x_2, \dots, x_n\} \subset \mathbb{Z} $ be the set of bomb locations, with $ 1 \le x_i \le 10^9 $, all distinct. **Constraints** - Use at most $ P $ type-1 tools, each covering a segment of length $ w $. - Use at most $ Q $ type-2 tools, each covering a segment of length $ 2w $. - Each tool covers a contiguous subsegment of the real line $[1, 10^9]$. - A tool destroys all bombs lying within its covered segment. - Each tool may be used at most once. **Objective** Find the minimum $ w \in \mathbb{Z}^+ $ such that all bombs in $ X $ can be covered by a combination of at most $ P $ type-1 intervals of length $ w $ and at most $ Q $ type-2 intervals of length $ 2w $.

API Response (JSON)

{
  "problem": {
    "name": "C. Divide",
    "description": {
      "content": "Đằng sau sự thành công của Bitcoin, không thể không kể đến công nghệ _Blockchain_. Blockchain hoạt động dựa trên các khối liên kết với nhau tạo thành một chuỗi. Điều đặc biệt ở đây chính là blockchain",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10227C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Đằng sau sự thành công của Bitcoin, không thể không kể đến công nghệ _Blockchain_. Blockchain hoạt động dựa trên các khối liên kết với nhau tạo thành một chuỗi. Điều đặc biệt ở đây chính là blockchain...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, P, Q \\in \\mathbb{Z} $ with $ 1 \\le n \\le 2000 $, $ 0 \\le P, Q \\le 10^5 $.  \nLet $ X = \\{x_1, x_2, \\dots, x_n\\} \\subset \\mathbb{Z} $ be the set of bomb locations, with $ 1 \\l...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments