USACO 2020 - Tháng 1 - Hạng Bạc

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 USACO 2020 - Berry Picking 100 (p) 4.0s 512M
2 USACO 2020Jan Silver - Loan Payment 100 (p) 1.0s 256M
3 USACO 2020 - Wormhole Sort 100 (p) 4.0s 512M

1. USACO 2020 - Berry Picking

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bessie và em gái Elsie đang hái quả mọng trong vườn cây của Farmer John. Khu vườn có đúng \(N\) cây quả mọng (\(1\le N\le 1000\)); cây thứ \(i\) có đúng \(B_i\) quả (\(1\le B_i\le 1000\)). Bessie có đúng \(K\) chiếc giỏ (\(1\le K\le 1000\), \(K\) là số chẵn). Mỗi giỏ có thể chứa bao nhiêu quả từ một cây tùy ý Bessie muốn, nhưng không thể chứa quả từ hai cây khác nhau vì hương vị của chúng sẽ xung khắc. Các giỏ có thể được để trống.

Bessie muốn tối đa hóa số quả mình thu hoạch được. Tuy nhiên, Farmer John muốn Bessie chia sẻ với em gái, vì vậy Bessie sẽ phải đưa cho Elsie \(K/2\) chiếc giỏ có số quả nhiều nhất. Điều này có nghĩa là Elsie thậm chí có thể nhận được nhiều quả hơn Bessie, thật vô cùng bất công, nhưng tiếc thay, quan hệ giữa chị em không phải lúc nào cũng công bằng.

Hãy giúp Bessie xác định số quả tối đa mà cô có thể thu được.

Phân nhóm

  • Các test từ \(1\) đến \(4\) thỏa mãn \(K\le 10\).
  • Các test từ \(5\) đến \(11\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp berries.in.

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.

Dòng thứ hai chứa \(N\) số nguyên \(B_1,B_2,\ldots,B_N\), cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra tệp berries.out một dòng chứa đáp án.

Ví dụ

Ví dụ 1

Input 
5 4
3 6 8 4 2
Output 
8
Giải thích

Nếu Bessie xếp:

  • một giỏ chứa \(6\) quả từ cây thứ \(2\);
  • hai giỏ, mỗi giỏ chứa \(4\) quả từ cây thứ \(3\);
  • một giỏ chứa \(4\) quả từ cây thứ \(4\),

thì cô nhận được hai giỏ, mỗi giỏ có \(4\) quả, tổng cộng là \(8\) quả.

Nguồn

2. USACO 2020Jan Silver - Loan Payment

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bác John nợ Bessie \(N\) lít sữa \((1 \leq N \leq 10^{12})\), và phải trả cho Bessie trong \(K\) ngày. Tuy nhiên, bác không muốn trả nợ sữa quá sớm. Dù vậy, bác vẫn phải thúc đẩy tiến độ trả nợ, nên bác John phải trả Bessie ít nhất \(M\) lít sữa mỗi ngày \((1 \leq M \leq 10^{12})\).

Sau đây là cách bác John trả nợ Bessie. đầu tiên bác chọn ra một số nguyên dương \(X\). Sau đó bác lặp lại quy trình sau hằng ngày:

  1. Giả sử bác đã trả Bessie \(G\) lít sữa, làm tròn xuống \(\dfrac{N-G}{X}\). Gọi số này là \(Y\).
  2. Nếu \(Y < M\), đặt \(Y = M\).
  3. Trả cho Bessie \(Y\) lít sữa.

Hãy xác định số \(X\) lớn nhất sao cho nếu bác John thực hiện quy trình trên, bác sẽ trả Bessie ít nhất \(N\) lít sữa sau \(K\) ngày \((1 \leq K \leq 10^{12})\).

Dữ liệu đầu vào

  • Một dòng duy nhất chứa ba số nguyên dương tách nhau bằng một dấu cách \(N, K\) và \(M\) thỏa mãn \(K \times M < N\).

Định dạng đầu ra

  • Một dòng duy nhất in ra số \(X\) lớn nhất sao cho bác John sẽ trả ít nhất \(N\) lít sữa với quy trình trên.

Điểm số

  • Test 2-4 thỏa mãn \(K \leq 10^5\)
  • Test 5-11 không có điều kiện nào khác

Ví dụ

Ví dụ 1

Đầu vào 
10 3 3
Đầu ra 
2
Giải thích

Với ví dụ này, khi \(X = 2\), bác John trả Bessie 5 lít sữa trỏng ngày đầu và \(M=3\) lít trong vòng 2 ngày tiếp theo.

Lưu ý: nên sử dụng các kiểu dữ liệu số nguyên 64-bit (như long long trong C++)

3. USACO 2020 - Wormhole Sort

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Những con bò của Farmer John đã chán ngấy việc mỗi sáng ông đều yêu cầu chúng tự sắp xếp trước khi rời chuồng. Chúng vừa hoàn thành bằng tiến sĩ vật lý lượng tử và đã sẵn sàng tăng tốc mọi việc một chút.

Sáng nay, như thường lệ, \(N\) con bò của Farmer John (\(1\le N\le 10^5\)), được đánh số thuận tiện từ \(1\dots N\), đang rải rác tại \(N\) vị trí phân biệt trong chuồng, cũng được đánh số từ \(1\dots N\), sao cho bò \(i\) đang ở vị trí \(p_i\). Nhưng sáng nay còn có \(M\) hố giun (\(1\le M\le 10^5\)), được đánh số từ \(1\dots M\); hố giun \(i\) nối hai chiều vị trí \(a_i\) với vị trí \(b_i\) và có độ rộng \(w_i\) (\(1\le a_i,b_i\le N\), \(a_i\neq b_i\), \(1\le w_i\le 10^9\)).

Tại bất kỳ thời điểm nào, hai con bò nằm ở hai đầu đối diện của một hố giun có thể chọn đồng thời đổi chỗ cho nhau qua hố giun đó. Những con bò phải thực hiện các lần đổi chỗ như vậy cho đến khi bò \(i\) ở vị trí \(i\) với mọi \(1\le i\le N\).

Những con bò không muốn bị các hố giun ép bẹp. Hãy giúp chúng tối đa hóa độ rộng của hố giun hẹp nhất mà chúng buộc phải sử dụng để tự sắp xếp. Đề bài đảm bảo rằng những con bò có thể tự sắp xếp được.

Phân nhóm

  • Các test từ \(3\) đến \(5\) thỏa mãn \(N,M\le 1000\).
  • Các test từ \(6\) đến \(10\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp wormsort.in.

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).

Dòng thứ hai chứa \(N\) số nguyên \(p_1,p_2,\dots,p_N\). Đề bài đảm bảo \(p\) là một hoán vị của \(1\ldots N\).

Với mỗi \(i\) từ \(1\) đến \(M\), dòng thứ \(i+2\) chứa ba số nguyên \(a_i\), \(b_i\) và \(w_i\).

Dữ liệu ra

Ghi ra tệp wormsort.out một số nguyên: giá trị lớn nhất có thể của độ rộng nhỏ nhất trong số các hố giun mà một con bò phải chui ép qua trong quá trình sắp xếp. Nếu những con bò không cần dùng hố giun nào để tự sắp xếp, hãy in ra \(-1\).

Ví dụ

Ví dụ 1

Input 
4 4
3 2 1 4
1 2 9
1 3 7
2 3 10
2 4 3
Output 
9
Giải thích

Sau đây là một cách sắp xếp những con bò chỉ bằng các hố giun có độ rộng ít nhất là \(9\):

  • Bò \(1\) và bò \(2\) đổi chỗ bằng hố giun thứ ba.
  • Bò \(1\) và bò \(3\) đổi chỗ bằng hố giun thứ nhất.
  • Bò \(2\) và bò \(3\) đổi chỗ bằng hố giun thứ ba.

Ví dụ 2

Input 
4 1
1 2 3 4
4 2 13
Output 
-1
Giải thích

Không cần dùng hố giun nào để sắp xếp những con bò.

Nguồn