Bán hàng

Xem PDF

Điểm: 450 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Chíp quyết định mở một cửa hàng bán kẹo và lập ra kế hoạch bán hàng đặc biệt. Giá hàng của Chip có vô hạn gói kẹo đánh số bằng các số nguyên dương từ \(1\) trở đi. Chíp đã bí mật giấu \(𝑚\) quà tặng vào các gói kẹo mang số hiệu \(𝑏_1,𝑏_2,...,𝑏_𝑚\).

Trong ngày, có \(𝑛\) khách hàng đánh số từ \(1\) tới \(𝑛\) theo thứ tự đến mua hàng. Khi một khách hàng thứ \(𝑖\) vào cửa hàng, Chip hỏi số gói kẹo người đó muốn mua \((𝑎_𝑖)\) sau đó chọn đúng \(𝑎_𝑖\) gói kẹo còn lại trên giá có số hiệu nhỏ nhất chia hết cho \(𝑎_𝑖\) để bán cho người khách đó.

Ví dụ:

  • Khách hàng thứ nhất đến mua \(𝑎_1=4\) gói kẹo, Chip sẽ bán cho các gói số hiệu 4, 8, 12 và 16 vì đây là 4 số nguyên dương nhỏ nhất chia hết cho 4.
  • Khách hàng thứ hai đến mua \(𝑎_2=2\) gói kẹo, Chip sẽ bán tiếp các gói số hiệu 2 và 6 (số hiệu 4 đã được bán nên đây là 2 số nguyên dương nhỏ nhất còn lại chia hết cho 2).

Cuối ngày, Chip muốn biết có bao nhiêu gói kẹo chứa quà tặng đã được bán.

Input

  • Dòng 1 chứa số nguyên dương \(m \ (𝑚\le 10^6)\) là số quà tặng
  • Dòng 2 chứa \(𝑚\) số nguyên dương \(𝑏_1,𝑏_2,...,𝑏_𝑚 \ (b_i \leq 10^6)\) hoàn toàn phân biệt là số hiệu những gói kẹo chứa quà tặng.
  • Dòng 3 chứa số nguyên dương \(n \ (𝑛\le 10^6)\) là số khách hàng
  • Dòng 4 chứa \(𝑛\) số nguyên dương \(𝑎_1,𝑎_2,...,𝑎_𝑛 \ (a_i \leq 10^6)\) là số kẹo muốn mua của các khách hàng.

Output

  • Ghi ra một số nguyên duy nhất là số gói kẹo chứa quà tặng đã được bán

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(m, n \leq 10\)\(a_i, b_i \leq 50\)
  • Subtask \(2\) (\(20\%\) số điểm): \(m, n \leq 5000\)\(a_i, b_i \leq 5000\)
  • Subtask \(3\) (\(50\%\) số điểm): không có điều kiện gì thêm.

Example

Test 1

Input
4
1 6 8 16
3
4 2 4
Output
3
Note
  • Khách hàng thứ nhất nhận các gói 4, 8, 12, 16
  • Khách hàng thứ hai nhận các gói 2, 6
  • Khách hàng thứ ba nhận các gói 20, 24, 28, 32
  • Như vậy có 3 gói chứa quà tặng được bán là 6, 8, 16

Bình luận (43)

Sắp xếp theo
Tải bình luận...