THANG MÁY

Để vận chuyển hòm báu vật lên phòng làm việc của mình ở tầng N trong toà nhà chọc trời, Cuội phải thuê công nhân bốc vác để vận chuyển hòm. Biết các chi phí liên quan đến thuê công nhân là: để di chuyển theo thang bộ lên trên một tầng là U, xuống dưới một tầng là D, khênh hòm vào thang máy là I, khênh hòm ra khỏi thang máy là J.

Trong toà nhà có L thang máy, mỗi thang chỉ dừng ở những tầng nhất định. Việc di chuyển theo thang máy là miễn phí.

Yêu cầu: Hãy giúp Bờm tìm đường vận chuyển hòm báu từ tầng 1 lên tầng N với chi phí phải trả là ít nhất.

Dữ liệu: Vào từ file văn bản LIFT.INP:

·    Dòng đầu tiên chứa các số nguyên N, U, D, I, J, L.

·            Dòng thứ i trong số L dòng tiếp theo mô tả hoạt động của thang máy thứ i (i=1,2,...,L): Đầu tiên là số nguyên Ki là số lượng tầng mà thang máy thứ i sẽ dừng, tiếp đến là Ki số nguyên là chỉ số của các tầng mà thang máy i sẽ dừng (các tầng được sắp xếp theo thứ tự tăng dần của chỉ số).

Hạn  chế:  0≤U≤1000,  0≤D≤1000,  0≤I≤1000,  0≤J≤1000,  0≤L≤500,  1≤N≤1000000,  2≤Ki≤1000,

K1+K2+…+KL≤1000.

Kết quả: Ghi ra file văn bản LIFT.OUT một số nguyên là chi phí nhỏ nhất tìm được.

Ví dụ:

LIFT.INP	LIFT.OUT
10 1 1 1 1 1 2 3 7	7

LIFT.INP	LIFT.OUT
10 1 1 3 2 1 2 3 7	9

LIFT.INP	LIFT.OUT
20 100 0 1 1 2 2 5 7 2 8 17	804

Max 2 -Bờm chọn quà

Tên file bài làm: MAX2.*

Sau một thời gian ngắn Phú ông nhanh chóng thăng quan tiến chức lên làm Lý trưởng rồi Chi phủ và bây giờ đã là quan Thượng Thư và được giao nhiệm vụ tổ chức cuộc thi chọn nhân tài cho đất nước.

Người thắng cuộc lần này lại là Bờm khiến cho quan Thượng Thư rất tức giận. Trước khi trao quà cho Bờm thì ông ta lại đánh tráo 1 số phần quà nào đó thành đá tảng nếu Bờm chọn lấy hết quà thì phải tốn tiền thuê xe mang về trong khi mấy tảng đá lại không có ý nghĩa gì cả mà nếu để lại thì bị khép vào tội coi thường triều đình.

Lần này quan Thượng Thư bố trí các phần quà trên một hình chữ nhật mà mỗi ô vuông đơn vị của hình chữ nhật chứa một phần quà. Bờm có thể chọn hết tất cả các phần quà mang về hoặc có thể chọn một số phần quà nào đó sao cho các phần quà Bờm chọn tạo thành một hình chữ nhật bên trong hình chữ nhật ban đầu.

Cũng nhờ bảo bối của Đô-rê-mon mà Bờm biết được giá trị các phần quà có thể nhận là một số nguyên. Trước khi  nhận quà Bờm mô tả các phần quà thành một bảng có n dòng m cột, ô ở dòng i cột j chứa số nguyên a_ij có thể là quà có giá trị hoặc đá, nếu đó là đá thì a_ij≤0 và phải mất |a_ij| tiền để chở về nhà.

Hãy giúp Bờm chọn quà sao cho tổng giá trị mang về nhà là lớn nhất.

Dữ liệu vào: từ tệp MAX2.INP

+ Dòng đầu tiên ghi hai số nguyên dương n và m (n, m ≤ 400)

+ Dòng thứ i  trong n dòng tiếp theo chứa các số a_i1, a_i2, a_i3,…,a_im  (|a_ij| ≤10⁴)

Dữ liệu ra: ghi vào tệp MAX2.OUT một số nguyên duy nhất là giá trị của bài toán

Ví dụ:

MAX2.INP	MAX2.OUT
4 5  2  3  1 -10  1  2  0 -1  -5 -2 -1  0  2   1 -1  2 -1 -2  -4  3	8

 Giải thích: Các phần quà Bờm chọn được in đậm.

 Test - Code - Solution

back <----> next

Con Diệc

Tên chương trình: HERONS.???

Lần đầu tiên được đi tới vườn bách thú Jimmy thích nhất các con diệc vì nhiều con trong số chúng đứng một chân trông rất ngộ nghĩnh, khi đó chân kia không thấy đâu như vốn sinh ra chúng đã chỉ có một chân. Jimmy đếm được tất cả có a chân.

Sau khi đi xem các con thú khác Jimmy lại quay về chổ chuồng diệc. Một số con đã thay đổi vị trí và cách đứng, Jimmy đếm lại một lần nữa và có số chân là b.

Qua số chân thì không thể xác định chính xác có tất cả bao nhiêu con diệc trong chuồng nhưng Gimmy vẫn muốn biết có ít nhất và nhiều nhất là bao nhiêu con.

Hãy xác định số lượng diệc tối thiểu và tối đa.

Dữ liệu: Vào từ file văn bản HERONS.INP gồm một dòng chứa 2 số nguyên a và b (1 ≤ a, b ≤ 10⁹).

Kết quả: Đưa ra file văn bản HERONS.OUT trên một dòng 2 số nguyên xác định số lượng diệc tối thiểu và tối đa.

Ví dụ:

HERONS INP		HERONS.OUT
3 4		2 3

Test - code

Quà của Phú ông

Tên file bài làm: MAX1.*

Bờm vừa dành chiến thắng trong cuộc thi đặc biệt của Phú ông. Với tính keo kiệt của mình Phú ông chỉ cho Bờm chọn 1 số phần quà liên tục nhau được đặt sẵn trên bàn. Thật may với bảo bối của Đô-rê-mon Bờm nhanh chóng nhận ra giá trị các phần quà.

Giá trị n phần quà của Phú ông có thể xem là một dãy các số nguyên a₁, a₂,…,a_n trong đó a_i là giá trị của phần quà thứ i. Nếu a_i  âm thì phần quà đó không có ý nghĩa với Bờm mà ngược lại Bờm lại thấy thật khó chịu vì phải tốn |a_i | tiền thuê xe mang nó về nhà rồi cũng chẳng biết làm gì với nó.

Hãy giúp Bờm chọn được một dãy liên tục các phần quà sao cho tổng giá trị là lớn nhất.

Dữ liệu vào: từ tệp MAX1.INP

+ Dòng đầu tiên ghi số nguyên dương n (n≤10⁶)

+ Dòng thứ 2 chứa n số nguyên a_i tương ứng với giá trị của phần quà thứ i (|a_i|≤10⁹)

Dữ liệu ra: ghi vào tệp MAX1.OUT một số nguyên duy nhất là giá trị của bài toán

Ví dụ:

MAX1.INP	MAX1.OUT
4 1 3 -2 4	6

 Giải thích: Bờm có thể chọn tất cả các phần quà của Phú ông.

Test - Solution - code - đề (word)

next