JOI 2006/2007 - Vòng chung kết

Cho dãy gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) và số nguyên dương \(k\). Với mỗi \(i\) thỏa mãn \(1 \le i \le n-k+1\), gọi

là tổng của \(k\) phần tử liên tiếp bắt đầu tại vị trí \(i\).

Yêu cầu

Tìm giá trị lớn nhất trong các tổng \(S_i\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\), cách nhau bởi một dấu cách.
• Dòng thứ \(i+1\) (\(1 \le i \le n\)) chứa số nguyên \(a_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên duy nhất là giá trị lớn nhất của \(S_i\).

Ràng buộc

• \(1 \le n \le 100\,000\).
• \(1 \le k \le n\).
• \(-10\,000 \le a_i \le 10\,000\) với mọi \(1 \le i \le n\).

Phân nhóm

Bài có tổng cộng \(20\) điểm, gồm \(5\) test, mỗi test \(4\) điểm.

1. Nhóm 1 (\(12\) điểm, \(60\%\)): \(1 \le n \le 5\,000\), \(1 \le k \le \min(n,1\,000)\).
2. Nhóm 2 (\(8\) điểm, \(40\%\)): \(1 \le n \le 100\,000\), \(1 \le k \le n\).

Ví dụ

5 3
2
5
-4
10
3

11

Có \(n\) thẻ mang các số nguyên từ \(1\) đến \(n\), mỗi số xuất hiện trên đúng một thẻ, và một thẻ trắng. Bạn được cho \(k\) thẻ trong số \(n+1\) thẻ này, với \(1 \le k \le n\).

Nếu nhận được thẻ trắng, bạn có thể viết lên đó một số nguyên từ \(1\) đến \(n\). Bạn muốn chọn và sắp xếp các thẻ được cho để tạo thành một dãy số nguyên liên tiếp dài nhất có thể.

Yêu cầu

Tính độ dài lớn nhất của một dãy số nguyên liên tiếp có thể tạo ra chỉ bằng các thẻ được cho.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\), cách nhau bởi một dấu cách.
• Mỗi dòng trong \(k\) dòng tiếp theo chứa một số nguyên biểu diễn một thẻ được cho. Số \(0\) biểu diễn thẻ trắng; số khác \(0\) là số viết trên thẻ.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên duy nhất là độ dài lớn nhất tìm được.

Ràng buộc

• \(1 \le n \le 100\,000\).
• \(1 \le k \le n\).
• Mỗi giá trị biểu diễn thẻ nằm trong đoạn từ \(0\) đến \(n\).
• Các thẻ được cho là những thẻ khác nhau: mỗi số từ \(1\) đến \(n\) xuất hiện nhiều nhất một lần và có nhiều nhất một thẻ trắng.

Phân nhóm

Bài có tổng cộng \(20\) điểm, gồm \(5\) test, mỗi test \(4\) điểm. Có \(40\%\) số điểm ứng với \(n \le 1\,000\), \(k \le 500\) và tổng cộng \(60\%\) số điểm ứng với \(n \le 60\,000\), \(k \le 50\,000\).

1. Nhóm 1 (\(8\) điểm, \(40\%\)): \(1 \le n \le 1\,000\), \(1 \le k \le \min(n,500)\).
2. Nhóm 2 (\(4\) điểm, \(20\%\)): \(1 \le n \le 60\,000\), \(1 \le k \le \min(n,50\,000)\).
3. Nhóm 3 (\(8\) điểm, \(40\%\)): \(1 \le n \le 100\,000\), \(1 \le k \le n\).

Ví dụ

7 5
6
2
4
7
1

2

7 5
6
2
0
4
7

4

Ngày xưa, tại một khu định cư có rất nhiều người sinh sống. Họ xây dựng những công trình với đủ hình dạng và kích thước. Các công trình ấy nay đã biến mất; chỉ những tài liệu cổ và các cột tìm thấy trong di tích còn cho biết vị trí của chúng.

Tài liệu cổ có nhắc đến một ngôi đền. Nhìn từ trên xuống, ngôi đền có hình vuông chính xác và có một cột ở mỗi góc. Không ai biết ngôi đền quay theo hướng nào, cũng không biết trên cạnh hay bên trong ngôi đền có những cột khác hay không. Các nhà khảo cổ cho rằng hình vuông có diện tích lớn nhất được tạo bởi bốn cột tìm thấy chính là vị trí của ngôi đền.

Yêu cầu

Cho tọa độ các cột, tìm diện tích lớn nhất của một hình vuông có bốn đỉnh là bốn cột. Các cạnh của hình vuông không nhất thiết song song với các trục tọa độ. Nếu không tồn tại hình vuông nào như vậy, in ra \(0\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(n\), là số cột tìm thấy trong di tích.
• Mỗi dòng trong \(n\) dòng tiếp theo chứa hai số nguyên \(x,y\) cách nhau bởi một dấu cách, là tọa độ của một cột.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên: diện tích lớn nhất tìm được, hoặc \(0\) nếu không có bốn cột tạo thành một hình vuông.

Ràng buộc

• \(1 \le n \le 3\,000\).
• \(0 \le x,y \le 5\,000\).
• Tọa độ của các cột là các số nguyên.
• Không có hai cột ở cùng một vị trí.

Phân nhóm

Bài có tổng cộng \(20\) điểm, gồm \(10\) test, mỗi test \(2\) điểm. Có \(30\%\) số điểm ứng với \(n \le 100\) và tổng cộng \(60\%\) số điểm ứng với \(n \le 500\).

1. Nhóm 1 (\(6\) điểm, \(30\%\)): \(1 \le n \le 100\).
2. Nhóm 2 (\(6\) điểm, \(30\%\)): \(1 \le n \le 500\).
3. Nhóm 3 (\(8\) điểm, \(40\%\)): \(1 \le n \le 3\,000\).

Ví dụ

10
9 4
4 3
1 1
4 2
2 4
5 8
4 0
5 3
0 5
5 2

10

Bạn là phóng viên phụ trách thể thao của tòa soạn JOI. Một giải bóng đá vòng tròn giữa \(n\) đội ở Croatia vừa kết thúc hôm qua; mỗi cặp đội đã thi đấu với nhau. Ban tổ chức đã xếp các đội từ hạng \(1\) đến hạng \(n\) dựa trên kết quả thi đấu và điều lệ giải.

Bạn chỉ được biết kết quả thắng thua của một số trận đấu, cùng các thông tin sau:

1. Không có trận hòa.
2. Mỗi đội có một thứ hạng khác nhau.
3. Với mọi \(1 \le a < b \le n\), trong trận đấu giữa đội hạng \(a\) và đội hạng \(b\), đội hạng \(a\) luôn thắng.

Để viết bài báo, bạn phải suy đoán bảng xếp hạng từ những thông tin này. Một bảng xếp hạng là thứ tự các đội từ hạng \(1\) đến hạng \(n\).

Yêu cầu

Xuất một bảng xếp hạng phù hợp với tất cả thông tin được cho. Đồng thời, xác định xem có bảng xếp hạng phù hợp nào khác với bảng bạn xuất ra hay không.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(n\). Các đội được đánh số từ \(1\) đến \(n\).
• Dòng thứ hai chứa số nguyên \(m\), là số trận đấu đã biết kết quả.
• Dòng thứ \(i+2\) (\(1 \le i \le m\)) chứa hai số nguyên \(x_i,y_i\) cách nhau bởi một dấu cách, cho biết đội \(x_i\) đã thắng đội \(y_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(n+1\) dòng:

• Dòng thứ \(i\) (\(1 \le i \le n\)) chứa số hiệu đội xếp hạng \(i\) trong một bảng xếp hạng phù hợp.
• Dòng thứ \(n+1\) chứa \(0\) nếu không có bảng xếp hạng phù hợp nào khác, hoặc \(1\) nếu có ít nhất một bảng xếp hạng phù hợp khác.

Nếu có nhiều bảng xếp hạng phù hợp, bạn được phép xuất bất kỳ bảng nào trong số đó.

Ràng buộc

• \(1 \le n \le 5\,000\).
• \(1 \le m \le 100\,000\).
• Các số hiệu đội trong kết quả thi đấu nằm trong đoạn từ \(1\) đến \(n\); hai đội trong một trận là khác nhau.
• Dữ liệu phù hợp với các thông tin đã nêu; luôn tồn tại ít nhất một bảng xếp hạng hợp lệ.

Phân nhóm

Bài có tổng cộng \(20\) điểm, gồm \(10\) test, mỗi test \(2\) điểm. Có \(30\%\) số điểm ứng với \(n \le 7\), \(m \le 15\) và tổng cộng \(60\%\) số điểm ứng với \(n \le 100\), \(m \le 2\,000\).

1. Nhóm 1 (\(6\) điểm, \(30\%\)): \(1 \le n \le 7\), \(1 \le m \le 15\).
2. Nhóm 2 (\(6\) điểm, \(30\%\)): \(1 \le n \le 100\), \(1 \le m \le 2\,000\).
3. Nhóm 3 (\(8\) điểm, \(40\%\)): \(1 \le n \le 5\,000\), \(1 \le m \le 100\,000\).

Ví dụ

4
5
1 2
3 1
3 2
3 4
4 1

3
4
1
2
0

3
2
2 1
2 3

2
1
3
1

2
3
1
1

Một tác phẩm treo chuyển động (mobile) là một vật trang trí phổ biến có các bộ phận có thể chuyển động. Ủy ban Olympic Tin học Nhật Bản muốn làm một tác phẩm như vậy để quảng bá JOI.

Tác phẩm được tạo bởi các thanh, dây và quả nặng theo những quy tắc sau:

• Mỗi thanh có một đầu màu đỏ và một đầu màu xanh lam.
• Mỗi thanh được treo bằng một sợi dây tại một điểm tựa nằm giữa hai đầu thanh, không trùng với đầu nào.
• Khoảng cách từ điểm tựa đến đầu đỏ và từ điểm tựa đến đầu xanh lam đều là số nguyên dương.
• Tại mỗi đầu thanh, một sợi dây treo một quả nặng hoặc một thanh khác.
• Mỗi quả nặng được treo bằng dây vào một đầu của một thanh; không có gì được treo bên dưới quả nặng.
• Khối lượng của mỗi quả nặng là một số nguyên dương.
• Có đúng một sợi dây có một đầu buộc vào điểm tựa của một thanh và đầu còn lại không buộc vào bộ phận nào khác. Mọi sợi dây còn lại đều nối một đầu thanh với điểm tựa của một thanh khác, hoặc nối một đầu thanh với một quả nặng.

Mọi thanh đều phải cân bằng. Bỏ qua khối lượng của thanh và dây, tức coi chúng có khối lượng bằng \(0\). Với một thanh, gọi \(W_{\text{đỏ}}\) và \(W_{\text{xanh lam}}\) lần lượt là tổng khối lượng của tất cả các quả nặng treo bên dưới đầu đỏ và đầu xanh lam; gọi \(L_{\text{đỏ}}\) và \(L_{\text{xanh lam}}\) là khoảng cách từ điểm tựa đến hai đầu tương ứng. Thanh cân bằng khi và chỉ khi

Cấu trúc nối các thanh và tỉ lệ độ dài hai phía của mỗi thanh đã được xác định, nhưng khối lượng các quả nặng chưa được chọn. Tác phẩm càng nhẹ thì càng dễ thao tác.

Chẳng hạn, với một thanh có hai cánh tay đòn theo tỉ lệ \(6:9\), treo quả nặng khối lượng \(3\) ở đầu đỏ và quả nặng khối lượng \(2\) ở đầu xanh lam thì thanh cân bằng vì \(3 \times 6 = 2 \times 9\). Đây là cách tạo tác phẩm nhẹ nhất với cấu trúc này, có tổng khối lượng \(5\).

Nếu hai khối lượng lần lượt là \(2\) và \(3\), thanh không cân bằng nên không tạo thành một tác phẩm hợp lệ. Nếu hai khối lượng lần lượt là \(9\) và \(6\), thanh vẫn cân bằng nhưng tổng khối lượng là \(15\), không phải nhỏ nhất.

Yêu cầu

Chọn khối lượng nguyên dương cho các quả nặng sao cho mọi thanh đều cân bằng và tổng khối lượng của tác phẩm là nhỏ nhất. In ra tổng khối lượng nhỏ nhất đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(n\), là số thanh. Các thanh được đánh số từ \(1\) đến \(n\).
• Dòng thứ \(i+1\) (\(1 \le i \le n\)) chứa bốn số nguyên \(p,q,r,b\), cách nhau bởi dấu cách, mô tả thanh \(i\).
• Tỉ lệ giữa khoảng cách từ điểm tựa đến đầu đỏ và khoảng cách từ điểm tựa đến đầu xanh lam là \(p:q\).
• \(r\) là số hiệu thanh treo ở đầu đỏ; \(b\) là số hiệu thanh treo ở đầu xanh lam. Giá trị \(0\) cho biết tại đầu tương ứng treo một quả nặng thay vì một thanh.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là tổng khối lượng nhỏ nhất của tác phẩm.

Ràng buộc

• \(1 \le n \le 100\).
• \(p,q\) là các số nguyên dương.
• \(0 \le r,b \le n\).
• Dữ liệu mô tả cấu trúc của một tác phẩm theo đúng các quy tắc đã nêu. Thanh trên cùng không nhất thiết là thanh số \(1\).
• Gọi \(w\) là tổng khối lượng nhỏ nhất và \(L\) là giá trị lớn nhất trong tất cả các số \(p,q\) xuất hiện trong đầu vào. Luôn có \(wL < 2^{31}\).

Phân nhóm

Bài có tổng cộng \(20\) điểm, gồm \(15\) test chia thành \(10\) nhóm. Mỗi nhóm được \(2\) điểm khi tất cả test trong nhóm đều đúng, ngược lại được \(0\) điểm. Mọi nhóm đều dùng các ràng buộc chung ở trên.

1. Nhóm 1 (\(2\) điểm): test \(1\) và \(2\).
2. Nhóm 2 (\(2\) điểm): test \(3\) và \(4\).
3. Nhóm 3 (\(2\) điểm): test \(5\) và \(6\).
4. Nhóm 4 (\(2\) điểm): test \(7\) và \(8\).
5. Nhóm 5 (\(2\) điểm): test \(9\) và \(10\).
6. Nhóm 6 (\(2\) điểm): test \(11\).
7. Nhóm 7 (\(2\) điểm): test \(12\).
8. Nhóm 8 (\(2\) điểm): test \(13\).
9. Nhóm 9 (\(2\) điểm): test \(14\).
10. Nhóm 10 (\(2\) điểm): test \(15\).

Ví dụ

4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0

40