USACO 2024 - Tháng 2 - Hạng Đồng - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	USACO 2024 February Contest, Bronze, Palindrome Game	100 (p)	2.0s	256M
2	USACO 2024 February Contest, Bronze, Milk Exchange	100 (p)	2.0s	256M
3	USACO 2024 February Contest, Bronze, Maximizing Productivity	100 (p)	2.0s	256M

1. USACO 2024 February Contest, Bronze, Palindrome Game

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

Bessie và Elsie đang chơi một trò chơi những viên đá. Chồng đá ban đầu có \(S\) (\(1\leq S \leq 10^{10^5}\)) viên. Hai cô bò thay phiên nhau loại bỏ \(x\) viên đã ra khỏi chồng đá, trong đó \(x\) là một số nguyên palindrome (những số viết xuôi hay ngược cũng giống nhau, ví dụ: 6446, 232). Cho đến khi không còn viên đá nào thì con bò đi lượt đó sẽ thua.

Hai cô bò dự tính chơi tổng cộng \(T\) ván, với những số đá khác nhau. Hãy tìm ra con bò chiến thắng của mỗi ván biết Bessie luôn đi trước.

Input:

Dòng đầu tiên chứa \(T\) là số ván chơi của hai cô bò
\(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên là số lượng đá trong chồng của một ván chơi mới.

Output:

Gồm \(T\) dòng, mỗi dòng chứa một kí tự B nếu Bessie thắng ván chơi và E nếu Elsia thắng.

Scoring:

Subtask 1: \(S<100\)
Subtask 2: \(S < 10^{6}\)
Subtask 3: \(S < 10^{9}\)
Subtask 4: Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

B
E
B

Note

Trong trường hợp đầu tiên, Bessie có thể loại bỏ tất cả các viên đá trong lượt đầu tiên, vì 8 là một số palindrome, đảm bảo cô ấy thắng.
Trong trường hợp thứ hai, 10 không phải là số palindrome, vì vậy Bessie không thể loại bỏ tất cả các viên đá trong lượt đầu tiên. Bất kể Bessie loại bỏ bao nhiêu viên đá trong lượt đầu tiên, Elsie luôn có thể loại bỏ tất cả các viên đá còn lại trong lượt thứ hai để chiến thắng.
Trong trường hợp thứ ba, Bessie loại bỏ 2 viên đá, trong lượt sau, dù Elsia có loại bỏ bao nhiêu viên, Bessie vẫn chiến thắng.

2. USACO 2024 February Contest, Bronze, Milk Exchange

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

Nông dân John đang tổ chức một sự kiện trao đổi sữa giữa những con bò, trong đó có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) con bò. Mỗi con bò đều mang theo một xô sữa đầy ắp, có sức chứa \(a_i\) (\(1 \leq a_i \leq 10^9\)) lít. Những con bò sau đó xếp thành một vòng tròn và được đánh số thứ tự từ \(1\) đến \(N\) sao cho con bò bên phải con bò \(i\) có số \(i\%N + 1\).

Nông dân John có một xâu hiệu lênh gồm chỉ hai kí tự "R" và "L", trong đó kí tự \(a_i\) là hướng đổ sữa của con bò thứ \(i\). Mỗi phút, những con bò sẽ đồng thời đổ đúng một lít sữa của mình vào xô của con bò bên trái hoặc phải. Nông dân John muốn biết, sau \(M\) (\(1 \leq M \leq 10^9\)) phút, tổng lượng sữa còn lại của đàn bò là bao nhiêu, biết nếu một xô sữa sẽ bị tràn nếu lượng sữa vượt quá sức chứa của nó, và một xô sữa sẽ không thay đổi nếu cho đi và nhận lại sữa cùng một lúc.

Input:

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).
Dòng thứ hai chứa xâu \(s_1, s_2, \ldots, s_N\) gồm những kí tự "L" và "R" mô tả hướng đổ sữa của những con bò
Dòng thứ ba chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) mô tả dung tích của những cái xô

Output:

Gồm một số nguyên duy nhất là tổng lượng sữa còn lại sau \(M\) phút.

Scoring

Subtask 1: \(N,M \leq 1000\)
Subtask 2: Không có ràng buộc gì thêm.

Example:

Test 1

Input

3 1
RRL
1 1 1

Output

Note

Các con bò 2 và 3 trao đổi 1 lít sữa cho nhau, nên sữa của chúng được bảo toàn. Khi con bò 1 trao sữa cho con bò 2, xô của con bò 2 tràn và mất 1 lít sữa sau 1 phút.

Test 2

Input

5 20
LLLLL
3 3 2 3 3

Output

Note

Mỗi con bò đều trao đổi 1 lít sữa cho con bò bên trái và nhận 1 lít sữa từ con bò bên phải, nên tất cả sữa đều được bảo toàn.

Test 3

Input

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

Output

Note

Ban đầu, có tổng cộng 51 lít sữa. Sau 5 phút, các con bò số 3, 6 và 7 sẽ mất lần lượt 5, 3 và 5 lít sữa. Do đó, còn lại tổng cộng 38 lít sữa

3. USACO 2024 February Contest, Bronze, Maximizing Productivity

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

Nông dân John có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) nông trại được đánh số từ \(1\) đến \(N\). Anh thường đóng cửa những nông trại thứ \(i\) của mình vào giờ \(c_i\), nhưng cô bò Bessie chỉ thức dậy và bắt đầu làm việc vào giờ \(S\). Do không muốn bị cắt lương, Bessie muốn tối ưu hiệu suất công việc của mình bằng cách ghé qua nhiều nông trại nhất có thể trước khi chúng đóng cửa. Cô dự định sẽ ghé qua nông trại thứ \(i\) vào khoảng thời gian \(t_i + S\), và cô phải làm vậy trước khi nông dân John đóng cửa nông trại đó.

Bessie có \(Q\) câu hỏi (\(1 \leq Q \leq 2 \times 10^5\)), với mỗi câu hỏi, cô ấy cho bạn biết hai số nguyên \(S\) và \(V\) và hi vọng bạn cho cô ấy biết liệu cô có thể ghé qua \(V\) nông trại nếu thức giấc vào thời gian \(S\) hay không.

Input:

Dòng đầu tiên gồm hai số nguyên \(N\) và \(S\).
Dòng thứ hai gồm \(c_1, c_2, \ldots, c_N\) (\(1 \leq c_i \leq 10^6\))
Dòng thứ ba gồm \(t_1, t_2, \ldots, t_N\) (\(1 \leq t_i \leq 10^6\))
\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(V\) (\(1 \leq V \leq N\)) và \(S\) (\(1 \leq S \leq 10^6\))

Output:

Gồm Q dòng, mỗi dòng gồm "YES" hoặc "NO" là câu trả lời cho mỗi truy vấn.

Scoring:

Subtask 1: \(N\), \(Q \leq 10^3\)
Subtask 2: \(c_{i}\), \(t_{i} \leq 20\)
Subtask 3: Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

YES
NO
YES
YES
NO

Note

Đối với truy vấn đầu tiên, Bessie sẽ đến thăm trang trại vào thời điểm t=[9,7,8,8,13], nên cô ấy sẽ chỉ được đến thăm trang trại 4 đúng thời hạn trước khi FJ đóng cửa trang trại.
Đối với truy vấn thứ hai, Bessie sẽ không thể đến thăm bất kỳ trang trại nào đúng giờ.
Đối với truy vấn thứ ba, Bessie sẽ đến thăm trang trại 3,4,5đúng giờ.
Đối với truy vấn thứ tư và thứ năm, Bessie sẽ có thể đến thăm tất cả trừ trang trại đầu tiên đúng giờ.