Olympic 11 Thành phố 2016 - 2017¶
Bài 3: Làm gốm¶
Đề bài¶
Một nhà máy sản xuất gốm sứ có hai phân xưởng. Phân xưởng nặn và phân xưởng vẽ.
Đầu tiên, tất cả sản phẩm được hình thành từ phân xưởng nặn, sau đó chúng được chuyển sang phân xưởng vẽ để vẽ các hoa văn trước khi nung.
Do hai phân xưởng này ở cách xa nhau nên trong một ngày tất cả đồ gốm sản xuất trong ngày chỉ được vận chuyển một lần duy nhất từ phân xưởng nặn sang phân xưởng vẽ bằng một ô tô chuyên dụng. May mắn là nó chạy rất nhanh nên thời gian vận chuyển xem như bằng 0. Sau khi hoàn thành vẽ xong, toàn bộ sản phẩm sẽ ngay lập tức đem đi nung.
Phân xưởng nặn có \(N\) thợ thủ công. Thợ thủ công thứ \(i\) nặn một sản phẩm mất \(a_i\) đơn vị thời gian. Phân xưởng vẽ có \(M\) thợ thủ công. Thợ thủ công thứ \(j\) vẽ một sản phẩm mất \(b_j\) đơn vị thời gian.
Ngày làm việc kéo dài \(T\) đơn vị thời gian và hi bắt đầu cả trong phân xưởng nặn và phân xưởng vẽ đều không có sản phẩm nào. Ngoài ra, sau khi kết thúc ngày làm việc, trong cả hai phân xưởng này cũng không còn sản phẩm nào (tức là tất cả sản phẩm đã hoàn thành cả hai phần việc nặn và vẽ).
Yêu cầu: tính số lượng sản phẩm tối đa mà hai phân xưởng này sản xuất trong một ngày.
Dữ liệu vào: POTTERY.INP
- Dòng đầu tiên ghi số nguyên dương \(T (1 \le T \le 10^9\)
- Dòng thứ hai ghi số nguyên dương \(N (1 \le N \le 10^5)\)
- Dòng thứ ba ghi \(N\) số nguyên \(a_1, a_2, \ldots, a_N (a_i \le 10^9)\)
- Dòng thứ tư ghi số nguyên dương \(M (1 \le M \le 10^5)\)
- Dòng thứ năm ghi \(M\) số nguyên \(b_1, b_2, \ldots, b_M (b_j \le 10^9)\)
Kết quả: POTTERY.OUT
Một số nguyên duy nhất là số lượng sản phẩm tối đa có thể hoàn thành trong ngày của hai phân xưởng.
Ví dụ:
| POTTERY.INP | POTTERY.OUT |
|---|---|
| 20 2 4 6 3 2 3 5 |
5 |
Bài giải đề xuất¶
Ý tưởng chính¶
Mã nguồn¶
Code đầy đủ được đặt tại GitHub.