JOI 2011 Representative Selection - Ngày 4

Trang trại JOI nhập và xuất táo. Táo được nhập từng quả một. Khi có yêu cầu xuất hàng, trang trại phải xử lý ngay, không đợi lần nhập táo tiếp theo. Mỗi yêu cầu xuất hàng chỉ định số táo cần xuất. Nếu có thể chọn đúng số táo đó theo quy định của trang trại, trang trại lập tức xuất những quả táo đã chọn. Nếu không thể, trang trại thông báo rằng không thể xuất hàng và không xuất quả táo nào.

Năm nay, trang trại JOI dự kiến sẽ nhập rất nhiều táo và nhận rất nhiều yêu cầu xuất hàng. Bạn được nhờ viết chương trình quản lý táo cho trang trại.

Yêu cầu

Mỗi quả táo có một độ đậm màu là số nguyên. Độ chênh lệch màu của một lần xuất hàng là hiệu giữa độ đậm màu lớn nhất và nhỏ nhất trong số táo được xuất. Quy định của trang trại yêu cầu độ chênh lệch này không vượt quá \(B\).

Chương trình nhận tổng cộng \(M\) yêu cầu. Yêu cầu thứ \(i\) thuộc một trong ba loại sau:

• Nhập táo: nhận thông tin rằng một quả táo có độ đậm màu \(D_i\) vừa được nhập và ghi nhận quả táo đó.
• Xuất hàng: nhận yêu cầu xuất \(N_i\) quả táo. Nếu có thể xuất hàng, in độ đậm màu của từng quả táo được xuất theo thứ tự tăng dần. Nếu không thể, in NO. Khi có nhiều cách chọn hợp lệ, phải chọn cách có tổng độ đậm màu lớn nhất. Những quả đã xuất không còn ở trang trại.
• Kết thúc chương trình: kết thúc chương trình khi nhận lệnh này.

Giao thức tương tác

Đây là bài tương tác (Reactive task) qua đầu vào chuẩn và đầu ra chuẩn. Nếu yêu cầu thứ \(i\) là yêu cầu xuất hàng, dữ liệu của yêu cầu thứ \(i+1\) chỉ được cung cấp sau khi chương trình đã xuất câu trả lời cho yêu cầu thứ \(i\).

Cần bảo đảm dữ liệu xuất không bị giữ trong bộ đệm, khiến thao tác đọc tiếp theo bị chặn. Gọi fflush(stdout); hoặc thực hiện thao tác tương đương trước khi đọc dữ liệu tiếp theo.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo giao thức trên:

• Dòng đầu chứa hai số nguyên \(M,B\), cách nhau bởi một dấu cách: tổng số yêu cầu và giới hạn độ chênh lệch màu của mỗi lần xuất hàng.
• Dòng thứ \(i+1\) \((1\le i\le M-1)\) chứa một yêu cầu nhập táo hoặc xuất hàng. Yêu cầu nhập táo có dạng A D_i, trong đó \(D_i\) là độ đậm màu của quả táo vừa nhập. Yêu cầu xuất hàng có dạng R N_i, trong đó \(N_i\) là số táo cần xuất. Chữ cái và số nguyên được ngăn cách bằng một dấu cách.
• Dòng thứ \(M+1\) chỉ chứa ký tự E, là yêu cầu kết thúc chương trình. Lệnh này được tính trong tổng số \(M\) yêu cầu.

Dữ liệu ra

Mỗi khi nhận yêu cầu xuất hàng, nếu không thể đáp ứng thì in một dòng chứa NO. Nếu có thể, in một dòng chứa độ đậm màu của tất cả các quả táo được xuất theo thứ tự tăng dần, cách nhau bởi dấu cách. Phải chọn cách xuất có tổng độ đậm màu lớn nhất trong các cách đáp ứng quy định.

Ràng buộc

• \(1\le M\le100\,000\).
• \(0\le B\le1\,000\,000\,000\).
• \(0\le D_i\le1\,000\,000\,000\) với các yêu cầu nhập táo, \(1\le i\le M\).
• \(1\le N_i\le100\,000\) với các yêu cầu xuất hàng, \(1\le i\le M\).

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(4\) giây, bộ nhớ \(256\) MB. Riêng bài này, thời gian được tính bằng tổng thời gian chạy của chương trình thí sinh và chương trình chấm. Nếu chương trình thí sinh sử dụng từ \(1\) giây trở lên, bài nộp có thể bị quá thời gian.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn đồng thời \(B\le10\,000\) và \(D_i\le10\,000\) với mọi yêu cầu nhập táo.

Ví dụ giao tiếp

Bảng sau giữ thứ tự nhận dữ liệu và xuất câu trả lời trong ví dụ. Cột Dữ liệu vào là dữ liệu hệ thống gửi cho chương trình; cột Dữ liệu ra là câu trả lời của chương trình. Ô trống nghĩa là không có dữ liệu ở phía đó trong bước tương ứng.

Năm 20XX, IOI sẽ được tổ chức tại đất nước nơi JOI sinh sống. Nghe tin này, JOI vội lao ra khỏi phòng để báo cho bạn bè. Vì quá hấp tấp, cậu va vào giá sách khiến toàn bộ sách rơi xuống. Đang rất vội, cậu nhặt tất cả sách đặt lại lên giá mà không quan tâm đến thứ tự rồi ra khỏi nhà. Khi trở về, JOI phải sắp xếp những cuốn sách đang lộn xộn về thứ tự ban đầu.

Giá sách trong phòng JOI rộng \(N\) xentimét, chứa \(N\) cuốn sách, mỗi cuốn rộng \(1\) xentimét. Các cuốn sách được đánh số từ \(1\) đến \(N\) và ban đầu được xếp từ trái sang phải theo thứ tự \(1,\ldots,N\). Cuốn sách \(i\) nặng \(A_i\) gam.

JOI đang mệt và không muốn cầm nhiều sách cùng lúc, nên cậu quyết định sắp xếp giá sách bằng cách lặp lại thao tác sau:

1. Chọn một cuốn sách trên giá và lấy nó ra.
2. Dịch chuyển các cuốn sách nằm cạnh chỗ trống vừa tạo ra vào chỗ trống; có thể thực hiện việc này nhiều lần.
3. Đặt cuốn sách đã lấy ra vào chỗ trống trên giá.

Không được lấy từ hai cuốn sách trở lên ra khỏi giá cùng một lúc.

Ví dụ, nếu sách đang được xếp từ trái sang phải theo thứ tự \(5,3,4,1,2\), JOI có thể lấy cuốn \(1\) ra, lần lượt dịch cuốn \(4\) rồi cuốn \(3\) sang phải và đặt cuốn \(1\) lại lên giá. Khi đó thứ tự sách từ trái sang phải trở thành \(5,1,3,4,2\), như hình dưới.

Khi lấy một cuốn sách nặng \(w\) gam ra khỏi giá, JOI tiêu hao đúng \(w\) calo. Khi đặt cuốn sách nặng \(w\) gam trở lại giá, cậu cũng tiêu hao đúng \(w\) calo. Giá sách được làm bằng vật liệu nhẵn, nên có thể coi việc dịch chuyển sách trong giá không tiêu hao calo.

Vì đang mệt, JOI muốn đưa sách về thứ tự ban đầu với lượng calo tiêu hao ít nhất.

Yêu cầu

Cho số cuốn sách, khối lượng của từng cuốn và thứ tự hiện tại trên giá, hãy tính tổng số calo ít nhất mà JOI cần tiêu hao để đưa sách về thứ tự ban đầu.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo mô tả khối lượng sách. Dòng thứ \(i+1\) \((1\le i\le N)\) chứa số nguyên \(A_i\), là khối lượng tính bằng gam của cuốn sách \(i\).
• \(N\) dòng tiếp theo mô tả thứ tự sách hiện tại. Dòng thứ \(j+N+1\) \((1\le j\le N)\) chứa số hiệu của cuốn sách đang ở vị trí thứ \(j\) từ trái sang.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số nguyên là tổng số calo ít nhất mà JOI phải tiêu hao.

Ràng buộc

• \(1\le N\le100\,000\).
• \(1\le A_i\le1\,000\,000\,000\) với mọi \(1\le i\le N\).
• Thứ tự hiện tại chứa mỗi cuốn sách từ \(1\) đến \(N\) đúng một lần.

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(1\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các tỷ lệ dưới đây mô tả các tập dữ liệu có phần giao nhau:

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(N\le5\,000\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(A_i=1\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn đồng thời \(N\le5\,000\) và \(A_i=1\) với mọi \(1\le i\le N\).
• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: \(N\le5\,000\); hoặc \(A_i=1\) với mọi \(1\le i\le N\).

Ví dụ

4
1
6
4
3
3
4
2
1

14

Năm 20XX, IOI cuối cùng cũng được tổ chức tại nước JOI. Có \(K\) thí sinh tham gia, được đánh số từ \(1\) đến \(K\). Kỳ thi có tổng cộng \(N\) bài; ở mỗi bài, mỗi thí sinh nhận một số điểm nguyên từ \(0\) đến \(100\).

Huy chương được trao dựa trên tổng điểm của \(N\) bài. Cụ thể, quy tắc trao huy chương vàng như sau: gọi \(G\) là giá trị lớn nhất sao cho số thí sinh có tổng điểm ít nhất \(G\) chiếm ít nhất \(\frac{1}{12}\) tổng số thí sinh. Một thí sinh nhận huy chương vàng khi và chỉ khi tổng điểm của mình trong \(N\) bài ít nhất là \(G\).

Hiện tại đã thi xong \(M\) bài và điểm của các bài này đã được xác định. Khi xem tổng điểm hiện tại của mỗi thí sinh trên trang web IOI, bạn muốn biết ai chắc chắn nhận huy chương vàng và ai còn có khả năng nhận huy chương vàng.

Yêu cầu

Cho tổng điểm hiện tại của từng thí sinh, hãy liệt kê theo thứ tự số hiệu tăng dần những thí sinh chắc chắn nhận huy chương vàng, rồi những thí sinh có khả năng nhận huy chương vàng.

Dữ liệu vào

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

• Dòng đầu chứa ba số nguyên \(K,N,M\), cách nhau bởi dấu cách: số thí sinh, tổng số bài và số bài đã thi xong.
• \(K\) dòng tiếp theo chứa điểm của các thí sinh. Dòng thứ \(i+1\) \((1\le i\le K)\) chứa số nguyên \(P_i\), là tổng điểm hiện tại của thí sinh \(i\).

Dữ liệu ra

In ra đầu ra chuẩn theo định dạng sau:

• \(a\) dòng đầu liệt kê số hiệu của những thí sinh chắc chắn nhận huy chương vàng, mỗi dòng một số, theo thứ tự tăng dần. Ở đây \(a\) là số thí sinh chắc chắn nhận huy chương vàng.
• Dòng tiếp theo chứa chuỗi --------, gồm đúng tám dấu gạch nối.
• \(b\) dòng tiếp theo liệt kê số hiệu của những thí sinh có khả năng nhận huy chương vàng, mỗi dòng một số, theo thứ tự tăng dần. Ở đây \(b\) là số thí sinh có khả năng nhận huy chương vàng.

Ràng buộc

• \(1\le K\le100\,000\).
• \(1\le N\le10\,000\,000\).
• \(0\le M\le N\).
• \(0\le P_i\le100\times M\) với mọi \(1\le i\le K\).

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(1\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn \(K\le3\,000\).

Ví dụ

15 3 2
0
30
50
100
0
190
10
50
100
80
90
200
50
100
0

12
--------
4
6
9
11
12
14

5 4 2
0
50
100
150
200

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

Trường trung học JOI mà bạn theo học tổ chức một cuộc thi định hướng mỗi năm một lần, với sự tham gia của toàn bộ học sinh. Thi định hướng là môn thi trong đó người tham gia dùng bản đồ và la bàn để đi qua các điểm kiểm tra được bố trí trên địa hình đồi núi.

Đặc điểm của cuộc thi ở trường JOI là học sinh tham gia theo đội hai người. Hai người trong mỗi đội cùng xuất phát từ điểm xuất phát được chỉ định, sau đó có thể di chuyển riêng để đến đích. Khi cả hai đã đến đích, mỗi điểm kiểm tra phải được ít nhất một người trong đội ghé qua. Hai người được phép ghé cùng một địa điểm và đi cùng một con đường trên hành trình.

Cuộc thi diễn ra trên núi JOI, nơi có \(N\) địa điểm và \(M\) con đường nối các địa điểm. Các địa điểm được đánh số từ \(1\) đến \(N\). Điểm xuất phát là địa điểm \(1\) ở chân núi, còn đích là địa điểm \(N\) trên đỉnh núi. Một số hoặc tất cả các địa điểm ngoài điểm xuất phát và đích được chọn làm điểm kiểm tra.

Để tránh hỗn loạn, trong thời gian thi, mỗi con đường chỉ được đi theo một chiều từ địa điểm thấp hơn đến địa điểm cao hơn. Không có hai địa điểm nào có cùng độ cao. Địa điểm \(1\) có độ cao thấp nhất và địa điểm \(N\) có độ cao cao nhất, nhưng số hiệu các địa điểm không nhất thiết được sắp theo thứ tự độ cao tăng dần. Ngay cả khi các đường được quy định một chiều như trên, từ địa điểm \(1\) vẫn có thể đến mọi địa điểm và từ mọi địa điểm vẫn có thể đến địa điểm \(N\).

Yêu cầu

Tìm tổng quãng đường nhỏ nhất mà hai người trong một đội phải đi để thỏa mãn các điều kiện. Dữ liệu bảo đảm tồn tại cách di chuyển hợp lệ cho hai người.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(N,M\), cách nhau bởi một dấu cách: số địa điểm và số con đường.
• \(N\) dòng tiếp theo cho biết những địa điểm nào là điểm kiểm tra. Dòng thứ \(i+1\) \((1\le i\le N)\) chứa số nguyên \(S_i\) bằng \(0\) hoặc \(1\). Nếu \(S_i=0\), địa điểm \(i\) không phải điểm kiểm tra; nếu \(S_i=1\), địa điểm \(i\) là điểm kiểm tra. Luôn có \(S_1=S_N=0\).
• \(M\) dòng tiếp theo mô tả các con đường. Dòng thứ \(j+N+1\) \((1\le j\le M)\) chứa ba số nguyên \(A_j,B_j,C_j\), cách nhau bởi dấu cách. Đường thứ \(j\) đi một chiều từ địa điểm \(A_j\) đến địa điểm \(B_j\) và có độ dài \(C_j\). Địa điểm \(A_j\) thấp hơn địa điểm \(B_j\). Luôn có \(A_j\ne B_j\), và không tồn tại đường \(k\ne j\) sao cho đồng thời \(A_k=A_j\) và \(B_k=B_j\).

Dữ liệu ra

In ra tổng quãng đường nhỏ nhất của hai người trong một đội khi di chuyển thỏa mãn các điều kiện.

Ràng buộc

• \(3\le N\le1\,000\).
• \(2\le M\le10\,000\).
• \(1\le K\le N-2\), trong đó \(K=S_1+S_2+\cdots+S_N\) là số điểm kiểm tra.
• \(1\le C_j\le10\,000\) với mọi \(1\le j\le M\).
• \(1\le A_j,B_j\le N\) và \(A_j\ne B_j\).
• \(S_i\in\{0,1\}\) và \(S_1=S_N=0\).
• Các địa điểm có độ cao đôi một khác nhau; mọi con đường đi từ thấp lên cao. Từ \(1\) có thể đến mọi địa điểm và từ mọi địa điểm có thể đến \(N\). Tồn tại một cặp hành trình từ \(1\) đến \(N\) đi qua tất cả điểm kiểm tra.

Thông tin kỹ thuật

Giới hạn của kỳ thi gốc: thời gian CPU \(1\) giây, bộ nhớ \(64\) MB.

Theo thông tin kỹ thuật của kỳ thi gốc, chương trình phải kết thúc bình thường với mã trả về \(0\). Một bộ dữ liệu chỉ được tính điểm khi chương trình đáp ứng giới hạn thời gian, bộ nhớ và cho kết quả đúng. Giới hạn ngăn xếp mặc định là \(8\) MB; cần tránh tràn ngăn xếp khi dùng đệ quy.

Khi cần xử lý số nguyên không vừa kiểu \(32\) bit, hãy dùng kiểu số nguyên \(64\) bit, chẳng hạn long long trong C/C++, với định dạng %lld cho scanf và printf. Với lượng dữ liệu vào/ra lớn, tài liệu kỹ thuật khuyến nghị dùng scanf/printf thay cho cin/cout để tránh chi phí vào/ra quá lớn.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các tỷ lệ dưới đây mô tả các tập dữ liệu có phần giao nhau:

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(K\le10\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn đồng thời \(N\le100\) và \(M\le500\).
• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn đồng thời \(K\le10\), \(N\le100\) và \(M\le500\).
• Các bộ dữ liệu chiếm \(50\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: \(K\le10\); hoặc đồng thời \(N\le100\) và \(M\le500\).

Ví dụ

8 12
0
1
0
0
1
1
0
0
1 4 5
1 6 5
4 2 4
4 7 9
4 5 6
2 5 8
2 8 3
6 2 7
6 7 8
7 3 2
3 5 7
5 8 3

29