DÃY SỐ NGUYÊN LIÊN TIẾP

Cho dãy số nguyên A =(a₁, a₂,…,a_n) bạn được thay số 0 trong A bởi một số nguyên bất kỳ khác sau đó chọn ra trong dãy A một số nhiều nhất các số (không cần đúng thứ tự) sao cho các số đã chọn tạo thành một dãy số nguyên liên tiếp.

Yêu cầu: Tìm cách có được dãy số nguyên liên tiếp dài nhất theo cách trên.

Ví dụ với A=(1,0,3,8,5,9,0), ta có thể thay hai số 0 lần lượt bởi 6 và 7, khi đó có thể chọn trong A ra các số (5, 6, 7, 8, 9) để được dãy số nguyên liên tiếp dài nhất.

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

+ Dòng 1 chứa số nguyên dương n≤10⁶

+ Dòng 2 chứa n số nguyên a₁, a₂,…,a_n cách nhau bởi dấu cách ("i: |a_i|≤10⁶)

Kết quả: ghi ra file văn bản LSEQ.OUT một số nguyên duy nhất là độ dài dãy số nguyên liên tiếp thu được theo phương án của bạn.

Ví dụ:

LSEQ.INP	LSEQ.OUT
7 1 0 3 8 5 9 0	5

 TEST - CODE

KIẾN

Cho một đàn kiến gồm n con đang đi trên một sợi dây căng ngang có hai đầu là A và B chiều dài k cm. Trong đàn có một số con kiến đi về phía điểm A, những con còn lại đi về pháo điểm B, ban đầu không có hai con nào ở cùng vị trí.

Các con kiến đều di chuyển với tốc độ giống nhau: 1cm/s, khi hai con kiến gặp nhau, chúng chạm râu vào nhau rồi cùng quay lại để di chuyển theo hướng ngược lại. Khi một con kiến chạm vào điểm A hay điểm B, nó sẽ bị rơi xuống đất và không còn trên dây nữa.

Yêu cầu: Biết vị trí và hướng di chuyển của từng con kiến tại thời điểm xuất phát là thời điểm 0, tính thời điểm con kiến cuối cùng bị rơi xuống đất.

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

+ Dòng 1 chứa 2 số nguyên dương n ≤10⁵ và k≤10¹⁸

+ Dòng 2 chứa n số nguyên x₁, x₂,…,x_n trong đó |x_i­| là khoảng cách từ con kiến thứ i tới điểm A, x_i<0 có nghĩa là ban đầu con kiến thứ i di chuyển về phái điểm A, x_i>0 có nghĩa  là ban đầu con kiến thứ i di chuyển về phía điểm B. (0<|x_i|< k)

Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách

Kết qủa: Ghi ra file văn bản ANTS.OUT một số nguyên duy nhất là phần nguyên của thời điểm con kiến cuối cùng bị rơi xuống đất.

Ví dụ:

ANTS.INP	ANTS.OUT
2 6 1 -5	5

 TEST - CODE - SOLUTION

XẾP ĐÁ

Cuội rất thích chơi một trò chơi với bộ sưu tập gồm n viên đá của mình: xếp n viên đá lên một bảng hình chữ nhật chia thành lưới ô vuông đơn vị, sao cho mỗi ô có không quá một viên đá.

Ví dụ với n=5, Cuội có thể xếp chúng vào bảng kích thước 1 x 5, 2 x 3, hay 4 x 2

Yêu cầu: Xác định kích thước của bảng có chu vi nhỏ nhất mà Cuội có thể thực hiện được trò chơi.

Dữ liệu: Vào từ file văn bản TABLE.INP gồm một dòng chứa số tự nhiên n<2³¹

Kết quả: Ghi ra file văn bản TABLE.OUT hai số cách nhau một dấu cách là độ dài hai cạnh của bảng tìm được.

Ví dụ:

TABLE.INP	TABLE.OUT		TABLE.INP	TABLE.OUT		TABLE.INP	TABLE.OUT
2	1 2		5	3 2		14	4 4

TEST

TRÁO BÀI

Cho bộ bài gồm n lá bài được xếp thành dãy thứ tự từ 1 tới n, đầu tiên người ta ghi vào mỗi lá bài một số nguyên là số thứ tự ban đầu của lá bài đó. Xét phép tráo S(i,m,j): lấy ra khỏi bộ bài m lá liên tiếp bắt đầu từ lá bài thứ i, sau đó chèn m lá bài này vào trước lá bài thứ j trong số n – m lá bài còn lại 1≤i, j≤n – m +1. Quy ước rằng nếu j=n-m+1 thì m lá bài này sẽ đưa vào cuối dãy.

Ví dụ với n=9:

Bộ bài ban đầu: (1, 2, 3, 4, 5, 6, 7, 8, 9)

Thực hiện S(1,5,2): (1, 2, 3, 4, 5, 6, 7, 8,9) ® (6, 1, 2, 3, 4, 5, 7, 8, 9)

Thực hiện tiếp S(5,4,6): (6, 1, 2, 3, 4, 5, 7, 8, 9) ® (6,1,2,3,9,4,5,7,8)

Thực hiện tiếp S(8,2,1): (6,1,2,3,9,4,5,7,8)  ® (7,8,6,1,2,3,9,4,5)

Yêu cầu: Hãy cho biết số ghi trên k lá bài đầu tiên của bộ bài (k≤n) sau khi thực hiện x phép tráo bài cho trước.

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

+ Dòng 1: Chứa 3 số nguyên dương n, k, x (n≤10⁵, k≤32, x≤10⁵)

+ x dòng tiếp theo, mỗi dòng ghi ba số nguyên i, m, j tương ứng với một phép tráo S(i,m,j)

Kết quả: ghi ra file văn bản CARDS.OUT một dòng chứa k số nguyên, số thứ i là số ghi trên lá bài thứ i sau khi thực hiện x phép tráo đã cho.

Các số trên một dòng của Input/Output files được/phải ghi cách nhau một dấu cách.

Ví dụ:

CARDS.INP	CARDS.OUT
9 2 3 1 5 2 5 4 6 8 2 1	7 8

 TEST - CODE

TRUNG BÌNH CỘNG

Cho dãy số nguyên B=(b₁, b₂,…,b_n), hãy tìm dãy số nguyên A=(a₁, a₂,…,a_n) sao cho "i:1≤i≤n trung bình cộng của I phần tử đầu tiên trong dãy A đúng bằng b_i:

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

+ Dòng đầu tiên chứa số nguyên dương n≤10⁵

+ Dòng 2 chứa n số nguyên b₁, b₂,…,b_n cách nhau bởi dấu cách ("i: |b_i|≤10⁹

Kết quả: Ghi vào tệp văn bản SUMAVR.OUT n số a₁, a₂,…,a_n theo đúng thứ tự cách nhau bởi 1 dấu cách.

Ví dụ:

SUMAVR.INP	SUMAVR.OUT
5 1 2 2 3 4	1 3 2 6 8

TEST - CODE

MÃ HÓA BURROWS-WHEELER

Mã hóa Burrows-Wheeler là một thuật toán sử dụng trong nén dữ liệu được phát minh bởi Micheal Burrows and David Wheeler (1994). Xét từ W gồm n chữ cái tiếng Anh in hoa. Thuật toán mã hóa có thể mô tả như sau (Ví dụ với từ BANANA):

Bước 1: Viết thêm vào cuối từ W một ký tự @, xét n+1 hoán vị vòng quanh: BANANA@ ANANA@B NANA@BA ANA@BAN NA@BANA A@BANAN @BANANA

Bước 2: Sắp xếp n+1 hoán vị vòng quanh đó theo thứ tự từ điển: @BANANA A@BANAN ANA@BAN ANANA@B BANANA@ NA@BANA NANA@BA

Bước 3: Viết ra các ký tự cuối của các hoán vị vòng quanh theo đúng thứ tự sau khi đã sắp xếp tạo thành từ mã của W: ANNB@AA

Với một danh sách các từ, mỗi từ chỉ gồm các chữ cái tiếng Anh in hoa, người ta đã mã hóa chúng bằng phương pháp Burrows-Wheeler để được danh sách các từ mã. Nhiệm vụ của bạn là phải giải mã toàn bộ danh sách các từ mã để phục hồi lại danh sách các từ ban đầu.

Dữ liệu: Vào từ file văn bản BWT.INP gồm nhiều dòng, mỗi dòng chứa một từ mã trong danh sách

Kết quả: Ghi ra file văn bản BWT.OUT có cùng số dòng với file dữ liêụ. Trên mỗi dòng ghi kết quả giải mã của từ trên dòng tương ứng với file dữ liệu.

Ràng buộc dữ liệu: Dữ liệu luôn được cho đúng đắn. Các từ trogn file dữ liệu dài không quá 10⁵ ký tự.

File dữ liệu có không quá 20 từ.

BWT.INP	BWT.OUT
YDRTYEESA@ L@LA Y@M SULBRTE@0 DEMSEE@ OS@ RF@A Y@AA	YESTERDAY ALL MY TROUBLES SEEMED SO FAR AWAY

 TEST - CODE

MUA K TẶNG 1

Cu Tí được phân công mua bút chì cho cả lớp nhân dịp đầu năm học mới. Số bút chì cần mua là n. Trong cửa hàng, giá mua lẻ mỗi cây bút chì là p. Tuy nhiên cu Tí là học sinh nên được cửa hàng cho hưởng chính sách ưu đãi đầu năm học mới. Cụ thể là cứ mỗi k chiếc bút chì mà cu Tí mua thì cậu ta sẽ được cửa hàng tặng thêm cho 1 chiếc bút nữa.

Yêu cầu: Xác định số tiền tối thiểu mà cu Tí cần mang theo để có thể tới cửa hàng mang về ít nhất n chiếc bút chì.

Dữ liệu: Vào từ tệp văn bản SALE.INP ba số nguyên dương n, k,p ≤10⁹ cách nhau bởi dấu cách.

Kết quả: ghi ra file văn bản SALE.OUT số tiền cần mang theo

SALE.INP	SALE.OUT
36 5 5	150

 TEST - code

CỤ RÙA

Cụ Rùa đã sống gần 400 năm trong hồ Hoàn Kiếm, ngoài việc thỉnh thoảng nổi lên cho có ý nghĩa tâm linh cụ không có việc gì để làm. Vì vậy cụ Rùa thường bày ra một vài trò chơi cho lũ cá trong hồ để giải trí. Một trong những trò chơi yêu thích của cụ Rùa là “Vẽ hình chữ nhật”. Trò chơi diễn ra như sau:

Cụ Rùa đưa ra 4 số nguyên dương (A, B, C, D). Mỗi chú cá tham gia trò chơi được tùy ý hoán vị 4 số nguyên này để được một dãy số (X, Y, Z, T). Đầu tiên chú cá bơi theo đường thắng X đơn vị độ dài, sau đó rẽ phải và bơi thẳng tiếp Y đơn vị độ dài, lại rẽ phải tiếp và bơi thẳng X đơn vị độ dài, cuối cùng lại rẻ phải và bơi thẳng T đơn vị độ dài.

Một lượt chơi của chú cá vạch ra một quãng đường hợp lệ nếu quãng đường đó quây kín một hình chữ nhật. Cụ Rùa sẽ có phần thưởng cho chú cá có lượt chơi hợp lệ mà quãng đường này quây kín một hình chữ nhật có diện tích lớn nhất.

Yêu cầu: Cho 4 số nguyên dương A, B, C, D, xác định diện tích hình chữ nhật lớn nhất mà quãng đường trong một lượt chơi của chú cá có thể quây kín được.

Dữ liệu: Vào từ tệp văn bản TURTLE.INP gồm 1 dòng chứa 4 số nguyên dương A, B, C, D ≤10⁹ cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản TURTLE.OUT một số nguyên duy nhất là diện tích tìm được.

Ví dụ:

TURTLE.INP	TURTLE.OUT
1 2 3 4	3

Giải thích: Cách chơi của chú cá là chọn hoán vị (4,1,3,2) như hình vẽ:

TEST

TÁO QUÂN

Có m ông táo và n bà táo được Ngọc Hoàng phân công nhiệm vụ trong năm mới. Đầu tiên Ngọc Hoàng chọn k táo (ông hoặc bà) làm những nhiệm vụ đặc biệt tại các Bộ/Ngành, sau đó Ngọc Hoàng sẽ chọn ra các nhóm, mỗi nhóm gồm đúng 2 ông táo và 1 bà táo để phân công xuống các gia đình dưới hạ giới.

Yêu cầu: Hãy giúp Ngọc Hoàng xác định số nhóm nhiều nhất để phân công xuống các gia đình dưới hạ giới.

Ví dụ có m=12 ông táo và n=7 bà táo, có k=5 táo phải làm nhiệm vụ đặc biệt. Ngọc Hoàng có thể chọn tối đa 4 nhóm phân xuống các gia đình (8 ông táo và 4 bà táo). Trong 7 tào còn lại (4 ông và 3 bà) có 5 táo làm nhiệm vụ đặc biệt, còn 2 táo không được phân việc.

Dữ liệu: vào từ tệp văn bản LARES.INP gồm 1 dòng chứa 3 số nguyên dương m, n, k ≤ 10⁹ cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra tệp văn bản LARES.OUT một số nguyên duy nhất là số nhóm nhiều nhất chọn được để phân xuống các gia đình dưới hạ giới.

Ví dụ:

LARES.INP	LARES.OUT
12 7 5	4

 TEST

CHIA QUÀ

Bờm được tặng một miếng Chocolate cực lớn hình chữ nhật kích thước m xn được chia thành lưới ô vuông đơn vị (m hàng và n cột). Muốn muốn cắt miếng chocolate ra làm nhiều mảnh để chia cho các bạn. Biết rằng Bờm được sử dụng không quá k nhát cắt thuộc 1 trong 2 loại sau:

+ Cắt ngang miếng chocolate từ trái qua phải theo rãnh giữa hai hàng ô liên tiếp.

+ Cắt dọc miếng chocolate từ trên xuống dưới theo rãnh giữa hai cột ô liên tiếp.

Yêu cầu: Giúp Bờm tìm cách cắt để chia miếng chocolate ra làm nhiều phần nhất.

Dữ liệu: vào từ file văn bản CUT.INP gồm một dòng chứa 3 số nguyên dương m, n, k ≤ 10⁹ cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản CUT.OUT một số nguyên duy nhất là số phần chocolate rời nhau sau khi cắt theo phương án tìm được.

Ví dụ:

CUT.INP	CUT.OUT
4 5 3	6

TEST

QUAY BẢNG

Cho 4 số nguyên a, b, c, d được viết vào bảng vuông kích thước 2 x 2 theo thứ tự sau:

a	b
c	d

Ta gọi giá trị của bảng trên là

Yêu cầu: xác định số lượt quay 90 độ theo chiều kim đồng hồ để được  bảng có giá trị lớn nhất. Nếu có nhiều cách quay bảng để có được giá trị lớn nhất thì chỉ ra số lượt quay ít nhất.

41	99	sau 1 lần quay	100	41
100	13		13	99

Dữ liệu: vào từ file văn bản ROTATE.INP gồm một dòng chứa 4 số nguyên a, b, c, d ≤100 cách nhau ít nhất 1 dấu cách.

Kết quả: Ghi ra file văn bản ROTATE.OUT một số nguyên duy nhất là số lượt quay tối thiểu tìm được.

Ví dụ:

ROTATE.INP	ROTATE.OUT
1 2 3 4	3
5 9 7 2	1
41 99 100 13	1

TEST

BELLMAN-FORD

Cho đồ thị G=(V, E, W) gồm N đỉnh, các đỉnh được đánh số từ 1 đến N,  và 2 đỉnh s, t thuộc V.
Tìm đường đi ngắn nhất từ s đến t.

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

+ Dòng đầu tiên ghi 4 số nguyên n, m, s, t lần lượt là số đỉnh, số cung, đỉnh xuất phát và đỉnh đích

+ m dòng tiếp theo mỗi dòng gồm 3 số u, v, w cho biết w (w≠0) là trọng số của cung (u,v).

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

+ Dòng đầu ghi một số nguyên cho biết độ dài đường đi ngắn nhất từ s đến t, nếu không có đường đi ngắn nhất thì ghi ‘NO’.

+ Nếu dòng đầu ghi một số nguyên thì dòng thứ 2 ghi một đường đi ngắn nhất từ s đến t.

Ví dụ:

BELLMAN.INP	BELLMAN.OUT
6 7 1 4 1 2 1 1 6 10 2 3 2 3 4 20 3 6 3 5 4 5 6 5 4	15 1 2 3 6 5 4

Giới hạn:

+ N<=2000_; M<=20000_; |w|<=20000     

TEST