USACO 2019 - Tháng 12 - Hạng Bạc

Gần đây, những cô bò của Nông dân John rất thích chơi một trò chơi số đơn giản có tên "FizzBuzz". Luật chơi rất đơn giản: đứng thành vòng tròn, các cô bò lần lượt đếm tăng dần từ một, mỗi cô nói một số duy nhất khi đến lượt mình. Tuy nhiên, nếu gặp một bội số của 3, cô bò phải nói "Fizz" thay cho số đó. Nếu gặp một bội số của 5, cô phải nói "Buzz" thay cho số đó. Nếu gặp một bội số của 15, cô phải nói "FizzBuzz" thay cho số đó. Vì vậy, đoạn đầu của một ván chơi là:

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16

Do vốn từ hơi hạn chế hơn, trong phiên bản FizzBuzz của những cô bò, họ nói "Moo" thay cho cả Fizz, Buzz và FizzBuzz. Vì vậy, phần đầu của phiên bản trò chơi dành cho bò là:

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16

Cho \(N\) (\(1 \leq N \leq 10^9\)), hãy xác định số thứ \(N\) được nói trong trò chơi này.

Phân nhóm

• Các test 2–5 thỏa mãn \(N \leq 10^6\).

Dữ liệu vào

Dữ liệu vào gồm một số nguyên duy nhất \(N\).

Dữ liệu ra

In số thứ \(N\) được nói trong trò chơi.

Ví dụ

4

7

Nguồn

USACO 2019 December Contest, Silver - MooBuzz: https://usaco.org/index.php?page=viewproblem2&cpid=966

Tác giả: Brian Dean.

Hai chuồng bò nằm tại các vị trí \(0\) và \(L\) (\(1 \leq L \leq 10^9\)) trên một trục số một chiều. Ngoài ra còn có \(N\) cô bò (\(1 \leq N \leq 5\cdot 10^4\)) ở các vị trí phân biệt trên trục số này (có thể coi các chuồng bò và các cô bò là những điểm). Ban đầu, mỗi bò \(i\) nằm tại một vị trí \(x_i\) và di chuyển theo chiều dương hoặc chiều âm với vận tốc một đơn vị mỗi giây, được biểu diễn bởi một số nguyên \(d_i\) bằng \(1\) hoặc \(-1\). Mỗi cô bò còn có trọng lượng \(w_i\) thuộc phạm vi \([1,10^3]\). Tất cả các cô bò luôn di chuyển với vận tốc không đổi cho đến khi xảy ra một trong những sự kiện sau:

• Nếu bò \(i\) đến một chuồng bò thì bò \(i\) dừng di chuyển.
• Một cuộc gặp xảy ra khi hai bò \(i\) và \(j\) cùng ở một điểm, trong đó điểm này không phải là chuồng bò. Khi đó, bò \(i\) nhận vận tốc trước đó của bò \(j\) và ngược lại. Lưu ý rằng các cô bò có thể gặp nhau tại những điểm không nguyên.

Gọi \(T\) là thời điểm sớm nhất mà tổng trọng lượng của những cô bò đã dừng di chuyển (do đến một trong hai chuồng) ít nhất bằng một nửa tổng trọng lượng của tất cả các cô bò. Hãy xác định tổng số cuộc gặp giữa các cặp bò trong khoảng thời gian \(0 \ldots T\) (kể cả tại thời điểm \(T\)).

Phân nhóm

• Các test 2–4 thỏa mãn \(N \leq 10^2\) và \(w_i=1\) với mọi \(i\).
• Các test 5–7 thỏa mãn \(N \leq 10^2\).

Dữ liệu vào

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

Mỗi dòng trong \(N\) dòng tiếp theo chứa ba số nguyên \(w_i\), \(x_i\) và \(d_i\), cách nhau bởi dấu cách. Tất cả các vị trí \(x_i\) đều phân biệt và thỏa mãn \(0<x_i<L\).

Dữ liệu ra

In một dòng duy nhất chứa đáp án.

Ví dụ

3 5
1 1 1
2 2 -1
3 3 -1

2

Nguồn

USACO 2019 December Contest, Silver - Meetings: https://usaco.org/index.php?page=viewproblem2&cpid=967

Tác giả: Benjamin Qi.

Nông dân John dự định xây dựng \(N\) trang trại (\(1 \leq N \leq 10^5\)) được nối với nhau bằng \(N-1\) con đường, tạo thành một cây (tức là mọi trang trại đều có thể đi đến nhau và không có chu trình). Mỗi trang trại có một cô bò, thuộc giống Guernsey hoặc Holstein.

\(M\) người bạn của Nông dân John (\(1 \leq M \leq 10^5\)) thường đến thăm ông. Trong chuyến thăm của người bạn \(i\), Nông dân John sẽ cùng người bạn đi dọc theo đường đi duy nhất từ trang trại \(A_i\) đến trang trại \(B_i\) (có thể xảy ra trường hợp \(A_i=B_i\)). Ngoài ra, họ có thể nếm sữa của bất kỳ cô bò nào dọc theo đường đi. Vì phần lớn bạn bè của Nông dân John cũng là nông dân, họ có sở thích rất khắt khe về sữa. Một số người bạn chỉ uống sữa Guernsey, còn những người còn lại chỉ uống sữa Holstein. Mỗi người bạn của Nông dân John chỉ vui nếu có thể uống loại sữa mình ưa thích trong chuyến thăm.

Hãy xác định liệu mỗi người bạn có vui sau chuyến thăm hay không.

Phân nhóm

• Các test 2–5 thỏa mãn \(N \leq 10^3\), \(M \leq 2\cdot 10^3\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\).

Dòng thứ hai chứa một xâu độ dài \(N\). Ký tự thứ \(i\) của xâu là G nếu cô bò ở trang trại thứ \(i\) thuộc giống Guernsey, hoặc là H nếu cô bò ở trang trại thứ \(i\) thuộc giống Holstein.

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên phân biệt \(X\) và \(Y\) (\(1 \leq X,Y \leq N\)), cho biết có một con đường giữa trang trại \(X\) và trang trại \(Y\).

\(M\) dòng tiếp theo chứa các số nguyên \(A_i\), \(B_i\) và một ký tự \(C_i\). \(A_i\) và \(B_i\) biểu thị hai đầu mút của đường đi trong chuyến thăm của người bạn \(i\), còn \(C_i\) là G hoặc H tùy theo người bạn thứ \(i\) thích sữa Guernsey hay sữa Holstein.

Dữ liệu ra

In một xâu nhị phân độ dài \(M\). Ký tự thứ \(i\) của xâu phải là 1 nếu người bạn thứ \(i\) sẽ vui, hoặc là 0 nếu không.

Ví dụ

5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H

10110

Nguồn

USACO 2019 December Contest, Silver - Milk Visits: https://usaco.org/index.php?page=viewproblem2&cpid=968

Tác giả: Spencer Compton.