| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO Bronze 2022/Dec - Trường Đại học Bò sữa | 100 (p) | 1.0s | 512M |
| 2 | USACO 2022 December Contest, Bronze, Feeding the Cows | 100 (p) | 2.0s | 256M |
| 3 | USACO 2022 December Contest, Bronze, Reverse Engineering | 100 (p) | 2.0s | 256M |
Bác Nông dân John sắp mở một trường Đại học mới cho Bò!
Có \(N\) con bò có khả năng dự đại học. Mỗi con bò có khả năng chi trả mức học phí cao nhất là \(c_i\) đồng. Bác John có thể chốt mức học phí mà tất cả loài bò đều phải đóng. Nếu mức học phí này lớn hơn khả năng chỉ trả cao nhất của một con bò nào đó, thì con bò đó sẽ không đi học đại học nữa. Bác John muốn kiếm được nhiều tiền nhất có thể để bác có thể trả các giảng viên một mức lương xứng đáng. Hãy xác định số tiền mà bác có thể kiếm được, và mức học phí mà các con bò phải đóng.
Bài có 12 testcase
Ví dụ
4
1 6 4 612 4Nếu bác thu học phí 4 đồng/con bò, sẽ có 3 con bò đi học, vì thế bác kiếm được \(3 \times 4 = 12\) đồng.
Nông dân John có \(N\) (\(1 \le N \le 10^5\)) con bò, mỗi con thuộc một trong hai giống: Guernsey hoặc Holstein. Chúng được xếp hàng theo vị trí từ \(1, 2, \dots, N\).
Vì tất cả các con bò đều đói, Nông dân John quyết định trồng các bãi cỏ tại một số vị trí từ \(1, 2, \dots, N\). Bò Guernsey và bò Holstein thích các loại cỏ khác nhau, do đó nếu bác John quyết định trồng cỏ tại một vị trí, bác phải chọn trồng cỏ dành riêng cho bò Guernsey hoặc bò Holstein — bác không thể trồng cả hai loại cỏ tại cùng một vị trí. Mỗi bãi cỏ có thể nuôi sống một số lượng không giới hạn bò của giống phù hợp.
Mỗi con bò chỉ sẵn sàng di chuyển tối đa \(K\) (\(0 \le K \le N-1\)) vị trí để đến một bãi cỏ. Hãy tìm số lượng bãi cỏ tối thiểu cần trồng để nuôi sống tất cả các con bò. Đồng thời, in ra một phương án của các bãi cỏ sao cho sử dụng số lượng bãi cỏ tối thiểu đó để nuôi sống tất cả các con bò. Bất kỳ phương án nào thỏa mãn điều kiện trên đều được chấp nhận.
Mỗi input gồm \(T\) bộ test, mỗi bộ mô tả một dãy bò.
G nghĩa là Guernsey, H nghĩa là Holstein).Với mỗi bộ test trong \(T\) bộ test, hãy in ra hai dòng output:
. nếu tại vị trí đó không trồng bãi cỏ nào.G nếu trồng bãi cỏ cho bò Guernsey.H nếu trồng bãi cỏ cho bò Holstein.Bất kỳ phương án hợp lệ nào đều được chấp nhận.
Test 1
6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HGLưu ý rằng với một số test, có thể có nhiều hơn một phương án tối ưu. Ví dụ trong test thứ tư, một phương án chấp nhận được khác là:
.GH..
Elsie có một phần mềm mà khi nhận được đầu vào là một dãy gồm \(N\) \((1 \le N \le 100)\) biến \(b[0], b[1], \dots, b[N - 1]\), mỗi biến chỉ nhận giá trị \(0\) hoặc \(1\) và trả về kết quả sau khi áp dụng một dãy các câu lệnh điều kiện if/else if/else lên đầu vào. Mỗi câu lệnh kiểm tra giá trị của tối đa một biến trong đầu vào, và trả về \(0\) hoặc \(1\). Ví dụ của một chương trình thoả mãn:
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
Lấy ví dụ, nếu đầu vào của chương trình trên là "10" \((b[0] = 1, b[1] = 0)\), thì đầu ra sẽ là \(1\).
Elsie đã nói cho Bessie đầu ra chính xác cho \(M\) \((1 \le M \le 100)\) đầu vào khác nhau. Bessie hiện tại đang muốn đảo ngược cấu trúc trong phần mềm của Elsie. Không may là, Elsie có thể đã buông lời dối gian; có thể có trường hợp mà không phần mềm nào cho đầu ra phù hợp với những lời Elsie nói.
Với mỗi test trong \(T\) \((1 \le T \le 10)\) test, hãy xác định xem Elsie nói dối hay thành thực!!
Test 1
4
1 3
0 0
0 0
1 1
2 4
00 0
01 1
10 1
11 1
1 2
0 1
0 0
2 4
00 0
01 1
10 1
11 0
OK
OK
LIE
LIE
if (b[0] == 0) return 0;
else return 1;
if (b[0] == 1) return 1;
else return 0;
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;