Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net
Đề thi IOI2009 - Bài 5: GARAGE
24/09/2009

Bãi đỗ xe có N chỗ đỗ xe, được đánh số từ 1 đến N. Buổi sáng, khi mở cửa chưa có xe nào trong bãi đỗ. Trong cả ngày, bãi đỗ được vận hành theo cách sau. Bất kì khi nào có một xe ô tô đến bãi đỗ, người gác sẽ kiểm tra xem có chỗ trống nào không. Nếu không có xê ô tô sẽ đợi cho đến khi có chỗ được phóng. Nếu có chỗ trống, hoặc ngay khi có một chỗ được giải phóng, xe sẽ được đưua vào chỗ đỗ trống này. Nếu có nhiều hơn một chỗ trống, xe sẽ được vào chỗ trống có hiệu số nhỏ nhất. Nếu có thêm xe ô tô đến trong khi có xe đang chờ, các xe sẽ xếp thành hàng đợi tại cửa bãi đỗ theo trình tự mà chúng đến. Sau đó, khi có chỗ đỗ được giải phóng, xe đầu tiên trong hàng đợi (nghĩa là xe đến sớm nhất) được đỗ vào chỗ trống này.


Chi phí tính theo đơn vị đô la bằng khối lượng xe(tính theo ki lô gam) nhân với một đơn giá tương ứng của chỗ đỗ xe cụ thể. Chi phí này không phụ thuộc vào thời gian xe đỗ trong bãi.

Người điều hành bãi đỗ xe biết trước ngày hôm nay sẽ có M xe ô tô đến dỗ tại bãi và anh ta biết trình tự các xe này đến và đi. Hãy giúp anh ta tính xem mình sẽ thu được bao nhiêu đô la trong ngày.

BÀI TOÁN

Hãy viết chương trình nhận vào đơn giá của các chỗ đỗ xe, khối lượng của các xe và trình tự mà các xe ô tô đến và đi, xác định doanh số thu được trong ngày của bãi đỗ xe tính bằng đô la.

GIỚI HẠN

1 ≤ N ≤ 100 Số lượng chỗ đỗ xe.

1 ≤ M ≤ 2000 Số lượng xe ô tô.

1 ≤ Rs ≤ 100 Đơn giá đỗ xe tại chỗ đỗ thứ s tính bằng đô la/ ki lô gam.

1 ≤ Wk ≤ 10000 Trọng lượng của xe thứ k tính bằng ki lô gam.

INPUT

Chương trình của bạn phải đọc từ standard input dữ liệu sau:

Dòng đầu tiên chứa các số nguyên N và M, cách nhau bởi một dấu cách.

N dòng tiếp theo mô tả đơn giá đỗ xe của các chỗ đỗ. Dòng thứ s trong số này chứa một số nguyên duy nhất Rs, đơn giá đỗ xe của chỗ đỗ thứ s tính bằng đô la / ki lo gam.

M dòng tiếp theo mô tả khối lượng của các xe. Các xe được đánh số từ 1 đến M không theo một thứ tự nào. Dòng thứ k trong số M dòng này chứa số nguyên duy nhất Wk, là khối lượng của xe thứ k tính bằng ki lo gam.

2 * M dòng tiếp theo mô tả việc đến và đi của tất cả các xe theo trình tự thời gian. Số nguyên dương i cho biết xe số i đến bãi đỗ. Số nguyên âm –i cho biết xe số i rời khỏi bãi đỗ. Không có xe nào rời khỏi bãi đỗ trước khi nó đến bãi, và tất cả các xe từ 1 đến M sẽ xuất hiện đúng 2 lần trong hàng chuỗi dữ liệu, một đến và một đi. Hơn nữa, không có xe nào rời khỏi bãi đỗ trước khi nó được đỗ tại bãi xe (nghĩa là sẽ không có xe nào rời khỏi bãi xe khi nó đang đứng trong hàng).

OUTPUT

Chương trình của bạn phải xuất ra standard output một dòng chứa số nguyên duy nhất: tổng số đô la người điều hành bãi đỗ thu được trong ngày.

CÁCH CHẤM ĐIỂM

Sẽ có một nhóm các test với tổng điểm là 40, trong đó luôn luôn có ít nhất một chỗ trống trong bãi đỗ khi một xe bất kì đến. Trong trường hợp này, không có xe nào phải đợi.

VÍ DỤ

Xe số 3 đỗ tại chỗ đỗ số 1 và trả 300 * 2 = 600 đô la.

Xe số 2 đỗ tại chỗ đỗ số 2 và trả 100 * 3 = 300 đô la.

Xe số 1 đỗ tại chỗ đỗ số 1 (được giải phóng bởi xe số 3) và trả 200 * 2 = 400 đo la.

Xe số 4 đỗ tại chỗ đỗ số 3 (chỗ trống cuối cùng) và trả 800 * 5 = 4000 đô la.

Xe số 3 đỗ tại chỗ đỗ số 1 và trả 1000 * 5= 5000 đô la.

Xe số 1 đỗ tại chỗ đỗ số 2 và trả 100 * 2 = 200 đô la.

Xe số 4 đến và phải chờ tại cửa sau xe số 2.

Khi xe số 1 giải phóng chỗ của mình, xe số 2 đỗ ở đây và trả 500 * 2= 1000 đô la.

Khi xe số 3 giải phóng chỗ của mình, xe số 4 đỗ ở đây và trả 2000 * 5 = 10000 đô la.
URL của bài viết này::http://www.vnschool.net/modules.php?name=News&file=article&sid=3537
© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn