| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2018 - Standing Out from the Herd | 100 (p) | 4.0s | 512M |
| 2 | USACO 2018 - Push a Box | 100 (p) | 4.0s | 512M |
| 3 | USACO 2018 - Greedy Gift Takers | 100 (p) | 4.0s | 512M |
Cũng như con người, những cô bò thường thích cảm thấy mình độc đáo theo một cách nào đó. Vì đàn bò của bác nông dân John đều thuộc cùng một giống và trông khá giống nhau, chúng muốn đo mức độ độc đáo qua tên của mình.
Tên của mỗi cô bò có một số xâu con. Ví dụ, “amy” có các xâu con {a, m, y, am, my, amy}, còn “tommy” có các xâu con sau: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}.
Tên của một cô bò có một “hệ số độc đáo”, là số xâu con của tên đó không xuất hiện trong tên của bất kỳ cô bò nào khác. Ví dụ, nếu amy ở một mình trong đàn, hệ số độc đáo của cô là \(6\). Nếu tommy ở một mình trong đàn, hệ số độc đáo của cô là \(14\). Tuy nhiên, nếu cả hai ở cùng một đàn, hệ số độc đáo của amy là \(3\) và của tommy là \(11\).
Cho một đàn bò, hãy xác định hệ số độc đáo của từng cô bò.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 10^5\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa tên của một cô bò trong đàn. Mỗi tên chỉ gồm các chữ cái thường từ a đến z. Tổng độ dài của tất cả các tên không vượt quá \(10^5\).
In ra \(N\) số, mỗi số trên một dòng, mô tả hệ số độc đáo của từng cô bò.
Ví dụ 1
3
amy
tommy
bessie3
11
19USACO 2017 December Contest, Platinum — Standing Out from the Herd
Tác giả bài toán: Matt Fontaine.
Bessie và những người bạn đã phát minh ra một trò chơi mới. Tên trò chơi mô tả rất chính xác, dù không mấy sáng tạo. Chúng gọi trò chơi là “Đẩy một chiếc hộp quanh chuồng để đưa nó vào đúng vị trí và đừng làm xê dịch cỏ khô” (nếu bạn thấy cái tên này quá dài, bạn nên xem thử tên một số biến mà những cô bò dùng khi viết mã...)
Chuồng bò có thể được mô hình hóa thành một lưới chữ nhật \(N \times M\). Một số ô của lưới có cỏ khô. Bessie đứng ở một ô trong lưới và một chiếc hộp gỗ lớn nằm ở một ô khác. Bessie và chiếc hộp không thể cùng nằm trong một ô, đồng thời cả hai đều không thể nằm trong ô chứa cỏ khô.
Bessie có thể di chuyển theo bốn hướng trực giao (bắc, đông, nam, tây), miễn là cô không đi vào cỏ khô. Nếu cô cố bước vào ô đang có chiếc hộp, chiếc hộp sẽ bị đẩy một ô theo hướng đó, với điều kiện phía bên kia có một ô trống. Nếu không có ô trống, Bessie không thể thực hiện bước di chuyển ấy.
Một ô nhất định trên lưới được chọn làm đích. Mục tiêu của Bessie là đưa chiếc hộp vào vị trí đó.
Cho sơ đồ chuồng bò, bao gồm vị trí ban đầu của chiếc hộp, vị trí ban đầu của Bessie và vị trí đích của chiếc hộp, hãy xác định liệu có thể thắng trò chơi hay không.
Lưu ý: Bài toán này cho phép sử dụng \(512\) MB bộ nhớ, tăng so với giới hạn mặc định \(256\) MB.
Dòng đầu tiên chứa ba số \(N\), \(M\) và \(Q\), trong đó \(N\) là số hàng và \(M\) là số cột của lưới.
\(N\) dòng tiếp theo biểu diễn lưới. Các ký tự lần lượt biểu thị ô trống (.), cỏ khô (#), vị trí ban đầu của Bessie (A) và vị trí ban đầu của chiếc hộp (B).
Sau đó là \(Q\) dòng, mỗi dòng chứa một cặp số nguyên \((R, C)\). Với mỗi cặp, hãy xác định liệu có thể đưa chiếc hộp đến ô ở hàng \(R\), cột \(C\) từ trạng thái ban đầu của chuồng hay không. Hàng trên cùng là hàng \(1\) và cột bên trái là cột \(1\).
In ra \(Q\) dòng, mỗi dòng chứa chuỗi YES hoặc NO.
Ví dụ 1
5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3NO
YES
NO
NOĐể đẩy chiếc hộp đến vị trí \((3, 5)\), cô bò chỉ cần di chuyển sang phải \(3\) ô.
Không thể đưa chiếc hộp đến bất kỳ vị trí nào trong ba vị trí còn lại.
USACO 2017 December Contest, Platinum — Push a Box
Tác giả bài toán: Nathan Pinsker.
Kẻ đối địch của bác nông dân John, bác nông dân Nhoj, có \(N\) cô bò (\(1 \leq N \leq 10^5\)), được đánh số thuận tiện từ \(1 \dots N\). Chúng bất ngờ xuất hiện ở trang trại của bác nông dân John, nên bác John, vốn luôn lịch thiệp, đang cố tặng quà cho chúng.
Vì vậy, bác nông dân John mang kho quà vô hạn của mình ra, còn đàn bò của Nhoj xếp hàng trước mặt bác, với bò \(1\) ở đầu hàng và bò \(N\) ở cuối hàng. Bác nông dân John đã nghĩ rằng tại mỗi bước thời gian, cô bò ở đầu hàng sẽ nhận một món quà từ bác rồi đi xuống cuối hàng. Tuy nhiên, bác vừa nhận ra đàn bò của Nhoj không lịch sự đến thế! Sau khi nhận quà, mỗi cô bò có thể không đi xuống cuối hàng mà chen lên trước một số cô bò ở cuối hàng, rồi đứng ngay trước họ. Cụ thể, bò \(i\) luôn chen lên trước đúng \(c_i\) cô bò (\(0 \leq c_i \leq N-1\)).
Bác nông dân John biết rằng một số cô bò có thể nhận nhiều món quà; vì có nguồn quà vô hạn, điều này không làm bác lo lắng. Nhưng bác lo rằng một số cô bò có thể không vui nếu chúng không nhận được món quà nào.
Hãy giúp bác nông dân John tìm số cô bò không bao giờ nhận được bất kỳ món quà nào, bất kể có bao nhiêu món quà được phát.
Dòng đầu tiên chứa một số nguyên \(N\).
Dòng thứ hai chứa \(N\) số nguyên \(c_1, c_2, \dots, c_N\) cách nhau bởi dấu cách.
In ra số cô bò không thể nhận được bất kỳ món quà nào.
Ví dụ 1
3
1 2 01USACO 2017 December Contest, Platinum — Greedy Gift Takers
Tác giả bài toán: Dhruv Rohatgi.