USACO 2022 - Tháng 2 - Hạng Đồng

Bò Bessie rất hào hứng vì gần đây đã được quay lại học trực tiếp! Đáng tiếc, giáo viên của cô, Farmer John, giảng bài rất nhàm chán nên cô thường xuyên ngủ gật trong lớp.

Farmer John nhận thấy Bessie không chú ý trong giờ học. Ông nhờ một học sinh khác trong lớp là Elsie ghi lại số lần Bessie ngủ gật trong mỗi buổi học. Có \(N\) buổi học (\(1\le N\le 10^5\)), và Elsie ghi nhận rằng Bessie ngủ gật \(a_i\) lần (\(0\le a_i\le 10^6\)) trong buổi học thứ \(i\). Tổng số lần Bessie ngủ gật trong tất cả các buổi học không vượt quá \(10^6\).

Vì rất thích cạnh tranh với Bessie, Elsie muốn khiến Farmer John nghĩ rằng Bessie luôn ngủ gật cùng một số lần trong mọi buổi học — qua đó làm cho vấn đề có vẻ hoàn toàn là lỗi của Bessie, không phụ thuộc vào những bài giảng đôi khi nhàm chán của Farmer John. Cách duy nhất Elsie được phép sửa nhật ký là gộp hai buổi học kề nhau. Ví dụ, nếu \(a=[1,2,3,4,5]\) và Elsie gộp buổi học thứ hai với buổi học thứ ba, nhật ký sẽ trở thành \([1,5,4,5]\).

Hãy giúp Elsie tính số lần sửa nhật ký ít nhất cần thực hiện để tất cả các số trong nhật ký bằng nhau.

Dữ liệu vào

Mỗi tệp vào chứa \(T\) (\(1\le T\le 10\)) bộ test cần được giải độc lập.

Dòng đầu tiên chứa \(T\), số bộ test cần giải. Sau đó là \(T\) bộ test, mỗi bộ được mô tả bởi hai dòng. Dòng đầu tiên chứa \(N\), dòng thứ hai chứa \(a_1,a_2,\ldots,a_N\).

Trong mỗi bộ test, tổng mọi giá trị trong \(a\) không vượt quá \(10^6\). Đồng thời, tổng \(N\) trên tất cả các bộ test không vượt quá \(10^5\).

Dữ liệu ra

In ra \(T\) dòng; với mỗi bộ test, dòng tương ứng là số lần sửa ít nhất Elsie có thể thực hiện để mọi phần tử của nhật ký bằng nhau.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

3
2
0

   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

   2 2 3
-> 2 5
-> 7

Nguồn

USACO 2022 February Contest, Bronze — Sleeping in Class: https://usaco.org/index.php?page=viewproblem2&cpid=1203

Tác giả: Jesse Choe.

Trong một tình huống có vẻ quen thuộc, Farmer John đang xếp hàng \(N\) con bò (\(1\le N\le 10^5\)), được đánh số thuận tiện từ \(1\ldots N\), để chụp ảnh.

Ban đầu, từ trái sang phải, các con bò đứng theo thứ tự \(a_1,a_2,\ldots,a_N\). Mục tiêu của Farmer John là xếp chúng theo thứ tự \(b_1,\ldots,b_N\) từ trái sang phải. Để làm được điều này, ông có thể thực hiện một chuỗi lần thay đổi thứ tự. Mỗi lần thay đổi gồm việc chọn một con bò duy nhất và dịch nó sang trái một số vị trí.

Hãy tính số lần thay đổi ít nhất cần thiết để Farmer John xếp đàn bò theo thứ tự mong muốn.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng thứ hai chứa \(a_1,a_2,\ldots,a_N\). Dòng thứ ba chứa \(b_1,b_2,\ldots,b_N\).

Dữ liệu ra

In số lần thay đổi ít nhất cần thiết để tạo ra thứ tự Farmer John mong muốn.

Phân nhóm

• Các test 3–6 thỏa mãn \(N\le 100\).
• Các test 7–10 thỏa mãn \(N\le 5000\).
• Các test 11–14 không có ràng buộc bổ sung.

Ví dụ

5
1 2 3 4 5
1 2 3 4 5

0

5
5 1 3 2 4
4 5 2 1 3

2

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

Nguồn

USACO 2022 February Contest, Bronze — Photoshoot 2: https://usaco.org/index.php?page=viewproblem2&cpid=1204

Tác giả: Benjamin Qi.

Để cải thiện vốn từ vựng, bò Bessie đã có một bộ gồm bốn khối gỗ hình lập phương, mỗi khối có một chữ cái trong bảng chữ cái được viết trên mỗi mặt trong sáu mặt. Cô đang học đánh vần bằng cách xếp các khối thành một hàng sao cho các chữ cái trên mặt trên của chúng tạo thành từ.

Biết các chữ cái trên mỗi khối trong bốn khối của Bessie và một danh sách các từ cô muốn đánh vần, hãy xác định những từ nào trong danh sách mà cô có thể đánh vần thành công bằng các khối.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1\le N\le 10\)), số từ Bessie muốn đánh vần. Bốn dòng tiếp theo, mỗi dòng chứa một chuỗi gồm sáu chữ cái in hoa, biểu diễn các chữ cái trên sáu mặt của một khối. \(N\) dòng tiếp theo chứa \(N\) từ Bessie muốn đánh vần. Mỗi từ dài từ 1 đến 4 chữ cái in hoa.

Dữ liệu ra

Với mỗi từ trong danh sách của Bessie, in YES nếu cô có thể dùng các khối để đánh vần từ đó, và in NO nếu không thể.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM

YES
NO
YES
YES
NO
NO

Nguồn

USACO 2022 February Contest, Bronze — Blocks: https://usaco.org/index.php?page=viewproblem2&cpid=1205

Tác giả: Brian Dean.