USACO 2022 - Tháng 1 - Hạng Bạc - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2022 - Searching for Soulmates	100 (p)	4.0s	512M
2	USACO 2022 - Cow Frisbee	100 (p)	4.0s	512M
3	USACO 2022 - Cereal 2	100 (p)	4.0s	512M

1. USACO 2022 - Searching for Soulmates

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

Mỗi chú bò của Nông dân John đều muốn tìm tri kỷ — một chú bò khác có những đặc điểm tương tự và tương hợp với mình nhất. Tính cách của mỗi chú bò được mô tả bằng một số nguyên \(p_i\) (\(1\le p_i\le 10^{18}\)). Hai chú bò có cùng tính cách là tri kỷ. Một chú bò có thể thay đổi tính cách bằng một “phép thay đổi”: nhân với \(2\), chia cho \(2\) (nếu \(p_i\) chẵn), hoặc cộng \(1\).

Ban đầu, Nông dân John ghép đôi những chú bò một cách tùy ý. Ông muốn biết cần bao nhiêu phép thay đổi để hai chú bò trong mỗi cặp trở thành tri kỷ. Với mỗi cặp, hãy xác định số phép thay đổi ít nhất mà chú bò thứ nhất trong cặp phải thực hiện để trở thành tri kỷ với chú bò thứ hai.

Dữ liệu vào

Dòng đầu chứa \(N\) (\(1\le N\le 10\)), là số cặp bò. Mỗi dòng trong \(N\) dòng còn lại mô tả một cặp bò bằng hai số nguyên chỉ tính cách của chúng. Số đầu tiên là tính cách của chú bò cần được thay đổi để khớp với chú bò thứ hai.

Dữ liệu ra

In \(N\) dòng. Với mỗi cặp, in số phép toán ít nhất cần thiết để chú bò thứ nhất biến đổi tính cách của mình thành tính cách của chú bò thứ hai.

Phân nhóm

Các test 1–4 thỏa mãn \(p_i\le 10^5\).
Các test 5–12 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Với bộ test đầu tiên, một dãy thay đổi tối ưu là \(31\implies 32\implies 16\implies 8\implies 9\implies 10\implies 11\implies 12\implies 13\).

Với bộ test thứ hai, một dãy thay đổi tối ưu là \(12\implies 6\implies 7\implies 8\).

Nguồn

USACO 2022 January Contest, Silver — Searching for Soulmates: https://usaco.org/index.php?page=viewproblem2&cpid=1182

Tác giả: Quanquan Liu.

2. USACO 2022 - Cow Frisbee

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

\(N\) chú bò của Nông dân John (\(N\le 3\times 10^5\)) có chiều cao \(1,2,\ldots,N\). Một ngày nọ, những chú bò đứng thành một hàng theo một thứ tự nào đó để chơi ném đĩa; gọi \(h_1\ldots h_N\) là chiều cao của những chú bò theo thứ tự này (do đó các \(h\) là một hoán vị của \(1\ldots N\)).

Hai chú bò ở vị trí \(i\) và \(j\) trong hàng có thể ném đĩa qua lại thành công khi và chỉ khi mọi chú bò nằm giữa chúng đều có chiều cao nhỏ hơn \(\min(h_i,h_j)\).

Hãy tính tổng khoảng cách giữa mọi cặp vị trí \(i<j\) có hai chú bò có thể ném đĩa qua lại thành công. Khoảng cách giữa vị trí \(i\) và \(j\) là \(j-i+1\).

Dữ liệu vào

Dòng đầu chứa một số nguyên \(N\). Dòng tiếp theo chứa \(h_1\ldots h_N\), cách nhau bởi dấu cách.

Dữ liệu ra

In tổng khoảng cách của mọi cặp vị trí có những chú bò có thể ném đĩa qua lại. Lưu ý rằng các số nguyên lớn trong bài có thể đòi hỏi kiểu số nguyên 64 bit (ví dụ long long trong C/C++).

Phân nhóm

Các test 1–3 thỏa mãn \(N\le 5000\).
Các test 4–11 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

7
4 3 1 2 5 6 7

Output

Giải thích

Các cặp vị trí thành công trong ví dụ này là:

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)

Nguồn

USACO 2022 January Contest, Silver — Cow Frisbee: https://usaco.org/index.php?page=viewproblem2&cpid=1183

Tác giả: Quanquan Liu.

3. USACO 2022 - Cereal 2

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

Không gì khiến những chú bò của Nông dân John thích hơn ngũ cốc vào bữa sáng! Thực tế, đàn bò ăn khỏe đến mức mỗi con sẽ ăn hết cả một hộp ngũ cốc trong một bữa.

Trang trại vừa nhận một lô hàng gồm \(M\) loại ngũ cốc khác nhau (\(2\le M\le 10^5\)). Không may, mỗi loại chỉ có một hộp! Mỗi chú bò trong số \(N\) chú bò (\(1\le N\le 10^5\)) có một loại ngũ cốc yêu thích nhất và một loại yêu thích thứ hai. Khi được cho một số loại ngũ cốc để lựa chọn, một chú bò thực hiện quy trình sau:

Nếu hộp ngũ cốc yêu thích nhất của cô bò vẫn còn, cô lấy nó rồi rời đi.
Nếu không, nếu hộp ngũ cốc yêu thích thứ hai của cô vẫn còn, cô lấy nó rồi rời đi.
Nếu vẫn không được, cô rống lên thất vọng và rời đi mà không lấy ngũ cốc.

Hãy tìm số bò bị đói nhỏ nhất nếu bạn sắp xếp chúng theo thứ tự tối ưu. Đồng thời, hãy tìm một hoán vị bất kỳ của \(N\) chú bò đạt được giá trị nhỏ nhất này.

Dữ liệu vào

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

Với mỗi \(1\le i\le N\), dòng thứ \(i\) chứa hai số nguyên cách nhau bởi dấu cách \(f_i\) và \(s_i\) (\(1\le f_i,s_i\le M\) và \(f_i\ne s_i\)), lần lượt biểu thị loại ngũ cốc yêu thích nhất và yêu thích thứ hai của chú bò thứ \(i\).

Dữ liệu ra

In số bò bị đói nhỏ nhất, sau đó là một hoán vị bất kỳ của \(1\ldots N\) đạt được giá trị nhỏ nhất này. Nếu có nhiều hoán vị, có thể in bất kỳ hoán vị nào.

Phân nhóm

Trong \(4\) trên tổng số \(14\) test, \(N,M\le 100\).
Trong \(10\) trên tổng số \(14\) test, không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Trong ví dụ này, có \(8\) chú bò và \(10\) loại ngũ cốc.

Lưu ý rằng ta có thể giải cho ba chú bò đầu tiên độc lập với năm chú bò cuối, vì hai nhóm không có chung loại ngũ cốc yêu thích nào.

Nếu ba chú bò đầu chọn theo thứ tự \([1,2,3]\), bò \(1\) sẽ chọn ngũ cốc \(2\), bò \(2\) sẽ chọn ngũ cốc \(3\), và bò \(3\) sẽ bị đói.

Nếu ba chú bò đầu chọn theo thứ tự \([1,3,2]\), bò \(1\) sẽ chọn ngũ cốc \(2\), bò \(3\) sẽ chọn ngũ cốc \(3\), và bò \(2\) sẽ chọn ngũ cốc \(4\); không con nào trong số này bị đói.

Dĩ nhiên, còn có những hoán vị khác khiến không chú bò nào trong ba chú bò đầu bị đói. Ví dụ, nếu ba chú bò đầu chọn theo thứ tự \([3,1,2]\), bò \(3\) sẽ chọn ngũ cốc \(2\), bò \(1\) sẽ chọn ngũ cốc \(1\), và bò \(2\) sẽ chọn ngũ cốc \(3\); một lần nữa, không con nào trong số các bò \([1,2,3]\) bị đói.

Có thể chứng minh rằng trong năm chú bò cuối, ít nhất một con phải bị đói.

Nguồn

USACO 2022 January Contest, Silver — Cereal 2: https://usaco.org/index.php?page=viewproblem2&cpid=1184

Tác giả: Dhruv Rohatgi.