Đ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\) và \(a_i, b_i \leq 50\)
- Subtask \(2\) (\(20\%\) số điểm): \(m, n \leq 5000\) và \(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
ta sử dụng 1 mảng bool kt[1000001]={0} để kiểm tra xem gói kẹo ai đã bị bán chưa.
ở bài này chúng ta cần để ý đến giá trị của món quà bi<=1.000.000 nên khi xét từng khách hàng mua, nếu chỉ số gói kẹo >1.000.000 thì ta không cần quan tâm đến nữa.
Để tránh bị lặp lại nhiều lần, chúng ta sẽ tạo 1 mảng f[1000001] để đánh dấu vị trí túi kẹo gần nhất đã đc mua VD:với khách hàng mua 3 gói kẹo, giả sử f[3]=4 tức là túi kẹo thứ 3*4=12 đã mua, ta sẽ xét món 15 và tăng f[3] lên 1 đơn vị.
4.1.tạo 1 biến tmp=(f[a]+1)*a
4.2.kiểm tra xem tmp có lớn hơn 1.000.000 hay không, nếu có break. vì món
quà<=1.000.000
cho em hỏi chỗ 4.1 là tmp = (f[a[i]] + 1) * a[i] phải không ạ:>
chào tui là best friend của og đây
best friend
túi nay ông có xem VN đá khum
uk
thanks
còn oog 2k mấy
2k9
em sorry 2k9 mà láo quá :))
À ông ở Đà Nẵng hả. Tui thấy trên lqdoj có nhiều người pro ở Đà Nẵng ghê
ông thích emlia đúng không
làm sao đổi avatar z
wibu never die :))
thanks oog nha ở Bài toán balo 1 bình luận tui âm 66 thế mà oog lại cảm ơn tui :))
tui nhỏ quá
ông lớp 9 đúng ko
ông học trường nào vậy
ông thích emlia nhỉ :))
ở đà nẵng, Học trường Lê Độ
tuổi tác không quan trọng
:))
uk
ông nên qua vnoi wiki để học thuật toán, như vậy sẽ dễ xử lý bài tập cao hơn đó
tui 2k3 :))) cũng mới học 2 tháng rưỡi :V. tui vẫn còn non nhắm :V vẫn phải học mót nhìu
ơ em chào anh:) em 2k7:<<
:))) ông tui đi cho nó tự nhiên :V