Đề HSG QG TIN HỌC 2005

Bài 1: Phân đoạn 

Cho dãy số nguyên a1, a2, …, an và số nguyên dương k. Ta gọi k-phân đoạn của dãy số đã cho là cách chia dãy số đã cho ra thành k đoạn, mỗi đoạn là một dãy con gồm các phần tử liên tiếp của dãy. Chính xác hơn, một k-phân đoạn được xác định bởi dãy chỉ số  

1 <= n1 < n2 < n3 < ... < nk = n  

Đoạn thứ i là dãy con ani-1+1, ani-1+2, ..., ani, i=1, 2, ..k. Ở đây quy ước n0=0  

Yêu cầu: Hãy xác định số M nhỏ nhất để tồn tại k-phân đoạn sao cho tổng các phần tử trong mỗi đoạn đều không vượt quá M.  

Input 

Dòng đầu tiên chứa hai số nguyên n và k (1≤ k ≤ n ≤ 15000).  

Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ai (|ai| ≤ 30000), i =1, 2, …, n.  

Các số cạnh nhau trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách.  

Output 

Gồm một số nguyên duy nhất là giá trị M tìm được.  

Example 

Input: 

9 4 

1 

1 

1 

3 

2 

2 

1 

3 

1 

Output: 

5 

Bài 2: Pháo hoa  

Nhằm chào mừng các ngày lễ lớn trong năm 2005 người ta đã chế tạo một loại đạn pháo hoa mới, khi bắn, đạn nổ thành bông hoa 2n cánh màu ( 1 ≤ n ≤ 30). Nguyên vật liệu cho phép tạo được m màu khác nhau, đánh số từ 1 đến m (2 ≤ m ≤ 32). 

Để đảm bảo tính mỹ thuật, việc chuyển tiếp màu giữa 2 cánh hoa kề nhau phải tuân theo quy tắc chuyển màu cầu vồng sau đây: 

- Bên cạnh cánh hoa màu i phải là cánh hoa màu i-1 hoặc i+1, với 1 < i < m. 

- Bên cạnh cánh hoa màu 1 chỉ có thể là cánh hoa màu 2. 

- Bên cạnh cánh hoa màu m chỉ có thể là cánh hoa màu m-1. 

Một bông hoa không nhất thiết phải có đầy đủ m màu. Mỗi bông hoa tương ứng với một vòng tròn 2n số thể hiện màu của các cánh hoa. Ví dụ, hình 1 là bông hoa 24 cánh (n = 12) và hình 2 là vòng tròn số tương ứng với nó. Mỗi bông hoa được mô tả bằng dãy 2n số nguyên liệt kê các chỉ số màu của các cánh hoa theo chiều kim đồng hồ. Ví dụ, bông hoa ở hình 1 có thể được mô tả bằng dãy số 

3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2. 

Dãy có thứ tự từ điển nhỏ nhất trong các dãy có thể dùng để mô tả hoa được gọi là mã hoa. Khi đó, mã hoa của bông hoa ở hình 1 sẽ là 

1 2 3 4 3 2 1 2 3 4 3 2 1 2 3 4 3 4 3 2 3 4 3 2. 

Trong các ngày lễ, Ban tổ chức yêu cầu bắn các đạn pháo hoa 2n cánh có đúng k cánh màu C (0 ≤ k ≤ 2). Các mã hoa thỏa mãn yêu cầu vừa nêu cũng được sắp xếp theo thứ tự từ điển và đánh số bắt đầu từ 1. Hơn nữa, nhằm tạo ra các hoa không giống nhau, đội bắn pháo hoa cần đảm bảo hai viên đạn pháo hoa bắn liên tiếp phải có mã khác nhau. Do vậy, người ta đã thiết kế một Hệ thống chụp ảnh và phân tích tự động để báo cho đội bắn pháo hoa biết số thứ tự của viên đạn pháo hoa vừa nổ trên trời. Em được giao viết chương trình giải quyết nhiệm vụ chính trong phần mềm phân tích tự động này. 

Yêu cầu: Cho biết n, m, k và C. Gọi X là tập tất cả các mã hoa 2n cánh có đúng k cánh màu C. 

- Hãy xác định số lượng p các phần tử của X. 

- Cho một mã hoa nào đó trong tập X. Hãy xác định số thứ tự từ điển của nó trong X. 

Input 

Dòng đầu tiên chứa 4 số nguyên n, m, k, C. 

Dòng tiếp theo chứa 2n số nguyên mô tả một mã hoa. 

Các số trên một dòng của file dữ liệu cách nhau ít nhất một dấu cách. 

Output 

Dòng đầu tiên ghi số nguyên p. 

Dòng tiếp theo ghi số thứ tự tìm được của mã hoa. 

Example 

Input: 

3 4 0 1 

2 3 4 3 4 3  

Output: 

4 

3  

Bài 3: Bộ sưu tập 

Một bộ sưu tập tiền xu cổ được coi là có giá trị phải gồm không ít hơn Z0 đồng tiền vàng, S0 đồng tiền bạc và M0 đồng tiền đồng. Bộ sưu tập ban đầu của Alibaba có một số lượng nhất định các đồng tiền vàng, bạc và đồng nhưng chưa phải là một bộ sưu tập có giá trị.  

Tại Trụ sở của Hiệp hội những người sưu tầm tiền cổ có đặt một máy đổi tiền để giúp hội viên đổi được các bộ sưu tập có giá trị.  

Tuy nhiên, máy đổi chỉ hỗ trợ việc đổi tiền trọn gói theo quy tắc đổi gói (Z1, S1, M1) lấy gói (Z2, S2, M2) đồng tiền. Các quy tắc đổi tiền khác nhau từng đôi một, được gán số hiệu tuần tự 1,2,3, . . . và được công bố trước. Hội viên có thể tạo gói tiền thích hợp từ bộ sưu tập của mình để thực hiện việc đổi tiền. Các đồng tiền nhận được sau mỗi lần đổi được gộp lại với các đồng tiền mà hội viên đang có để thành một bộ sưu tập mới và có thể được sử dụng để đổi trong những lần sau nếu cần. Số lần đổi không hạn chế, tuy nhiên, là người thực dụng, Alibaba luôn cố gắng giảm tới mức tối đa số lần đổi tiền. Mặt khác, để ngăn chặn việc đầu cơ, Hiệp hội quy định, trong mọi thời điểm, mỗi hội viên không được giữ quá 4 đồng tiền mỗi loại và không được phép đổi tiếp khi đã đổi được một bộ sưu tập có giá trị.  

Yêu cầu: Cho biết số lượng các đồng tiền vàng, bạc, đồng mà Alibaba có ban đầu và các quy tắc đổi tiền. Hãy chỉ ra tất cả các bộ sưu tập tiền cổ có giá trị mà Alibaba có thể có được sau một số lần đổi không vượt quá k cho trước.  

Input 

Dòng đầu ghi số nguyên dương K ( K <= 1000 )  

Dòng thứ 2 ghi 6 số nguyên không âm Z, S, M, Z0, S0, M0 ( 0 <= Z, S, M, Z0, S0, M0 <= 4 )  

Các dòng tiếp theo mỗi dòng ghi 6 số nguyên không âm Z1, S1, M1, Z2, S2, M2 xác định một quy tắc đổi tiền (0 <= Z1, S1, M1, Z2, S2, M2 <= 4 )  

Output 

Nếu không tồn tại cách đổi để có được bộ sưu tập có giá trị, file kết quả chỉ gồm một số -1.  

Trong trường hợp ngược lại, dòng đầu ghi số v là số các bộ tiền cổ có giá trị mà Alibaba có thể đổi được.  

Dòng thứ i trong v dòng tiếp theo ghi 4 số nguyên Zi, Si, Mi, ki mô tả bộ sưu tập có giá trị thứ i và số lần đổi ki ít nhất không vượt quá k cần thực hiện để có được bộ sưu tập ấy. ( Các bộ Zi, Si, Mi phải đưa ra theo thứ tự từ điển )  

Example 

Input: 

2 

4 0 1 3 3 3 

1 0 1 1 1 1 

2 0 1 1 3 3 

Output: 

1 

3 3 3 1