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

EXPLORE

Bessie đang dạo chơi trên 1 con đường với những thắng cảnh hấp dẫn. Con đường có thể được coi như 1 trục tọa độ, với vị trí của Bessie nằm tại x = 0, và các thắng cảnh nằm ở vị trí x₁, x₂,…,x_n. Bessie muốn tham quan càng nhiều thắng cảnh càng tốt nhưng cô chỉ có tối đa T phút, sau đó đêm sẽ đến và cô không nhìn thấy gì cả.

Thêm vào đó thứ tự tham quan của các thắng cảnh cũng bị ràng buộc. Theo đó cô sẽ thăm quan các thắng cảnh lần lượt theo khoảng cách của nó đến trại của Bessie (tất cả khoảng cách này là đôi một phân biệt). Thời gian để Bessie di chuyển 1 đơn vị trên trục tọa độ là 1 phút, thời gian tham quan một thắng cảnh là không đáng kể.

Tính số lượng thắng cảnh tối đa mà Bessie có thể tham quan.

Dữ liệu vào: Từ tệp văn bản EXPLORE.INP

+ Dòng đầu tiên chứa 2 số nguyen T và N (1≤T≤10⁹, 1≤N≤5.10⁴)

+ N dòng tiếp theo: dòng thứ k chứa số nguyên dương x_k (|x_k|≤ 10⁵) .

 Dữ liệu ra: ghi vào tệp văn bản: EXPLORE.OUT

Một số nguyên duy nhất là số thắng cảnh mà Bessie tham quan

 Ví dụ:

EXPLORE.INP	EXPLORE .OUT
25 5 10 -3 8 -7 1	4

Test - code - solution - đề (word)

DPBASIC

Cho dãy số nguyên dương a₁, a₂,…,a­_n. Giá trị của dãy số được xác định bằng tổng các tính của tất cả cặp số trong dãy.

Ví dụ dãy 3 1 2 5 có giá trị 3x1 + 3x2 + 3x5 + 1x2 + 1x5 + 2x5 = 41

Tương tự giá trị của 1 đoạn con trong dãy là tổng các tích của tất cả các cặp số trong đoạn con đó

Yêu cầu: Hãy tính giá trị của tất cả các đoạn con liên tiếp trong dãy

Dữ liệu vào: Từ tệp văn bản DPBASIC.INP

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

+ Dòng tiếp theo chứa n số nguyên dương, số thứ i mang giá trị a_i (a_i≤5)

Dữ liệu ra: ghi vào tệp văn bản DPBASIC.OUT gồm n dòng, mỗi dòng n cột trong đó số ghi ở dòng i cột j tương ứng là giá trị của đoạn con từ i đến j trong dãy số. Quy ước nếu j≤i thì ghi 0

Ví dụ:

DPBASIC.INP	DPBASIC.OUT
4 4 5 1 2	0 20 29 49 0 0 5 17 0 0 0 2 0 0 0 0

 Test - solution - code - word 
next

HỘI CHỢ

Khu hội chợ Đông Bắc Bắc Giang có  m x n gian hàng được bố trí trong một khu hình chữ nhật kích thước m x n. Các hàng của hình chữ nhật được đánh số 1,2,3,...,m  từ trên xuống dưới, còn các cột – đánh số 1,2,3,...,n  từ trái sang phải, ô nằm giao của hàng i và cột j là gian hàng (i,j)  trưng bày mặt hàng a_ij. Khách tham quan đi vào khu hội chợ từ một gian hàng bất kỳ bên trái (i  bất kỳ, j=1) và mất 1 đồng, không nhất thiết phải tham quan tất cả các gian hàng, khách chỉ có thể đi ra khỏi khu hội chợ từ các gian hàng bên phải (i bất kỳ, j=n), tại mỗi gian hàng khách có thể di chuyển qua các gian hàng chung cạnh với nó. Khi đi vào gian hàng trưng bày mặt hàng khác với mặt hàng của gian hàng hiện tại thì khách tham quan phải mua vé giá là 1 đồng.

Yêu cầu: Cho biết mặt hàng trưng bày tại các gian hàng, tính chi phí ít nhất mà khách tham quan phải trả khi tham quan khu hội chợ.

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

-     Dòng đầu tiên ghi hai số m và n;

-  m dòng sau, mỗi dòng n số nguyên không âm, cho mã mặt hàng được trưng bày tại các gian hàng của khu hội chợ. Mã mặt hàng tại gian hàng (i,j)  là  a_ij thỏa mãn 0≤a_ij≤100

      Hai số liên tiếp trên một dòng cách nhau một dấu cách.

Kết quả: Ghi ra file văn bản FAIR.OUT gồm một số duy nhất là chi phí ít nhất tìm được.

Ví dụ:

FAIR.INP	FAIR.OUT
2 3 0 1 1 1 1 2	1

Ràng buộc:

·  Có 30% số test ứng với 30% số điểm của bài có m, n≤5

·  Có 30% số test ứng với 30% số điểm của bài có m, n≤50

·  Có 40% số test khác ứng với 40% số điểm còn lại của bài có  m, n≤1000

Test - solution - đề bài (word) - code