USACO 2019 - Tháng 1 - Hạng Đồng

Để giết thời gian, cô bò Bessie và cô bạn Elsie thích chơi một phiên bản của trò chơi mà họ từng thấy tại hội chợ hạt.

Đầu tiên, Bessie úp ba chiếc vỏ sò lên bàn và đặt một viên sỏi tròn nhỏ bên dưới một trong số chúng (ít nhất cô hy vọng đó là một viên sỏi — cô nhặt được nó trên mặt đất ở một trong các đồng cỏ). Sau đó Bessie liên tục hoán đổi từng cặp vỏ sò, trong khi Elsie cố đoán vị trí của viên sỏi.

Trong phiên bản thông thường của trò chơi mà các cô bò thấy tại hội chợ hạt, người chơi được nhìn thấy vị trí ban đầu của viên sỏi, rồi phải đoán vị trí cuối cùng của nó sau khi tất cả các lần hoán đổi hoàn tất.

Tuy nhiên, các cô bò thích chơi một phiên bản mà Elsie không biết vị trí ban đầu của viên sỏi và được phép đoán vị trí viên sỏi sau mỗi lần hoán đổi. Vì biết đáp án đúng, khi trò chơi kết thúc Bessie cho Elsie số điểm bằng số lần cô đoán đúng.

Biết các lần hoán đổi và các dự đoán nhưng không biết vị trí ban đầu của viên sỏi, hãy xác định số điểm cao nhất mà Elsie có thể đã đạt được.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\), là số lần hoán đổi (\(1 \leq N \leq 100\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một bước của trò chơi và chứa ba số nguyên \(a\), \(b\) và \(g\), cho biết Bessie hoán đổi hai vỏ sò \(a\) và \(b\), sau đó Elsie đoán vỏ sò \(g\). Cả ba số nguyên này đều thuộc tập \(\{1, 2, 3\}\) và \(a \neq b\).

Dữ liệu ra

In ra số điểm tối đa mà Elsie có thể đã đạt được.

Ví dụ

3
1 2 1
3 2 1
1 3 1

2

Nguồn

Đề bài gốc: USACO 2019 January Contest, Bronze — Shell Game

Tác giả: Brian Dean

Farmer John đang cố gắng sắp xếp \(N\) con bò của mình (\(1 \leq N \leq 100\)), được đánh số thuận tiện từ \(1 \dots N\), trước khi chúng ra đồng cỏ ăn sáng.

Hiện tại, các cô bò đang đứng thành một hàng theo thứ tự \(p_1, p_2, p_3, \dots, p_N\), còn Farmer John đứng trước cô bò \(p_1\). Ông muốn sắp xếp lại để các cô bò có thứ tự \(1, 2, 3, \dots, N\), trong đó cô bò \(1\) đứng cạnh Farmer John.

Hôm nay các cô bò hơi buồn ngủ, nên tại bất kỳ thời điểm nào, cô bò duy nhất chú ý đến chỉ dẫn của Farmer John là cô đứng ngay trước mặt ông. Trong một bước thời gian, ông có thể yêu cầu cô bò này di chuyển xuống dưới hàng \(k\) vị trí, với \(k\) bất kỳ trong khoảng \(1 \ldots N-1\). \(k\) cô bò mà cô ấy đi qua sẽ chậm rãi tiến lên phía trước, tạo chỗ để cô ấy chen vào hàng ngay sau họ.

Ví dụ, giả sử \(N=4\) và ban đầu các cô bò đứng theo thứ tự sau:

FJ: 4, 3, 2, 1

Cô bò duy nhất đang chú ý đến FJ là cô bò \(4\). Nếu ông yêu cầu cô ấy di chuyển xuống dưới hàng \(2\) vị trí, thứ tự sau đó sẽ là:

FJ: 3, 2, 4, 1

Lúc này cô bò duy nhất đang chú ý đến FJ là cô bò \(3\), nên ở bước thời gian thứ hai ông có thể đưa ra chỉ dẫn cho cô bò \(3\), và cứ tiếp tục như vậy cho đến khi các cô bò được sắp xếp xong.

Farmer John nóng lòng hoàn thành việc sắp xếp để có thể trở về trang trại ăn sáng. Hãy giúp ông tìm số bước thời gian tối thiểu cần thiết để sắp xếp các cô bò.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, \(p_1, p_2, p_3, \dots, p_N\), cho biết thứ tự ban đầu của các cô bò.

Dữ liệu ra

In ra một số nguyên duy nhất: số bước thời gian trước khi \(N\) con bò được xếp theo đúng thứ tự, nếu Farmer John hành động tối ưu.

Ví dụ

4
1 2 4 3

3

Nguồn

Đề bài gốc: USACO 2019 January Contest, Bronze — Sleepy Cow Sorting

Tác giả: Dhruv Rohatgi

Khi đã chán trò chơi vỏ sò thường ngày, cô bò Bessie và cô bạn Elsie thích chơi một trò chơi phổ biến khác có tên là "đoán con vật".

Đầu tiên, Bessie nghĩ đến một con vật nào đó (phần lớn thời gian con vật này là một con bò, khiến trò chơi khá nhàm chán, nhưng đôi khi Bessie sáng tạo và nghĩ đến một con vật khác). Sau đó Elsie đặt một loạt câu hỏi để tìm ra con vật Bessie đã chọn. Mỗi câu hỏi hỏi xem con vật có một đặc điểm cụ thể nào đó hay không, và Bessie trả lời mỗi câu bằng "có" hoặc "không". Ví dụ:

Elsie: "Con vật có bay không?"
Bessie: "Không"
Elsie: "Con vật có ăn cỏ không?"
Bessie: "Có"
Elsie: "Con vật có tạo ra sữa không?"
Bessie: "Có"
Elsie: "Con vật có kêu moo không?"
Bessie: "Có"
Elsie: "Vậy thì tớ nghĩ con vật là một con bò."
Bessie: "Chính xác!"

Gọi "tập khả thi" là tập hợp tất cả các con vật có đặc điểm phù hợp với những câu hỏi Elsie đã đặt ra cho đến thời điểm hiện tại. Elsie tiếp tục hỏi cho đến khi tập khả thi chỉ còn một con vật, sau đó cô công bố con vật này là câu trả lời. Trong mỗi câu hỏi, Elsie chọn một đặc điểm của một con vật nào đó trong tập khả thi để hỏi (ngay cả khi đặc điểm này có thể không giúp cô thu hẹp tập khả thi thêm chút nào). Cô không bao giờ hỏi về cùng một đặc điểm hai lần.

Biết tất cả các con vật mà Bessie và Elsie biết cùng với đặc điểm của chúng, hãy xác định số câu trả lời "có" tối đa mà Elsie có thể nhận được trước khi cô biết đúng con vật.

Dữ liệu vào

Dòng đầu tiên chứa số lượng con vật \(N\) (\(2 \leq N \leq 100\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một con vật. Dòng bắt đầu bằng tên con vật, tiếp theo là một số nguyên \(K\) (\(1 \leq K \leq 100\)), rồi đến \(K\) đặc điểm của con vật đó. Tên con vật và các đặc điểm là những xâu có độ dài không quá \(20\), chỉ gồm các chữ cái thường a đến z. Không có hai con vật nào có tập đặc điểm hoàn toàn giống nhau.

Dữ liệu ra

In ra số câu trả lời "có" tối đa mà Elsie có thể nhận được trước khi trò chơi kết thúc.

Ví dụ

4
bird 2 flies eatsworms
cow 4 eatsgrass isawesome makesmilk goesmoo
sheep 1 eatsgrass
goat 2 makesmilk eatsgrass

3

Nguồn

Đề bài gốc: USACO 2019 January Contest, Bronze — Guess the Animal

Tác giả: Brian Dean