Tin học trẻ B - Bắc Ninh - Quảng Bình - Hưng Yên 2024

Cho ba số nguyên dương \(a,b,c\). Hỏi có thể tạo ra tổng lớn hơn \(1000\) từ hai số bất kì trong ba số không?

Input

• Dòng thứ nhất chứa một số nguyên dương \(T\) (\(T \le 100\)) - số bộ dữ liệu.
• Mỗi dòng trong \(T\) dòng kế tiếp chứa ba số nguyên dương \(a,b,c\) (\(a,b,c < 1000\)).

Output

• Với mỗi bộ dữ liệu, đưa ra YES trên một dòng nếu thoả mãn, ngược lại đưa ra NO

Example

1
200 900 800

YES

Cho một dãy gồm \(n\) số nguyên. Bạn được phép sắp xếp lại dãy theo bất kì thứ tự nào bạn muốn. Hỏi dãy dài nhất mà chênh lệch giữa hai số liên tiếp không vượt quá \(k\) có độ dài bao nhiêu?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,k\) (\(n \le 2 \times 10^5, k \le 10^9\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) (\(a_i \le 10^9\)).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

4 1
2 1 4 3

4

Cho dãy \(a\) gồm \(n\) số nguyên.

Bạn phải trả lời \(q\) truy vấn, mỗi truy vấn cho hai số nguyên \(b,c\), bạn cần tìm số cặp \((i,j)\) thoả mãn:

• \(1 \le i < j \le n\).
• \(a_i + a_j = b\).
• \(a_i \times a_j = c\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) (\(1 \le n \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(1 \le |a_i| \le 10^9\)).
• Dòng thứ ba chứa một số nguyên dương \(q\) (\(1 \le q \le 2 \times 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(b,c\) mô tả một truy vấn (\(1 \le |b| \le 2 \times 10^9, 1 \le |c| \le 10^{18}\)).

Output

• Với mỗi truy vấn, đưa ra trên một dòng một số nguyên là kết quả của truy vấn đó.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10^3, q = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(|a_i| \le 10^6, |c| \le 10^9\).
• Subtask \(3\) (\(20\%\) số điểm): \(|c| \le 10^9\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_i\) phân biệt từng đôi một.
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

3
1 3 2
1
3 2

1

Hôm nay là ngày sinh nhật của Bob, mẹ của Bob tặng cho cậu một xâu \(s\). Thích thú với món quà trên tay, Bob liền chạy đi tìm Alice để chơi trò xoá xâu.

Luật chơi: Mỗi lượt, một người được chọn \(2\) kí tự liên tiếp giống nhau và xoá chúng ra khỏi xâu \(s\). Người nào không thực hiện được thao tác xoá sẽ bị xử thua.

Vì là xâu của Bob nên Bob đương nhiên sẽ được đi trước. Hãy tính toán xem nếu như Bob và Alice đều chơi tối ưu, thì ai sẽ là người chiến thắng?

Input

• Một dòng duy nhất là xâu \(s\) (Độ dài của xâu \(s \le 10^5\)) chỉ chứa các chữ cái từ a đến z.

Output

• Gồm một xâu duy nhất là Bob hoặc Alice tương ứng với người chiến thắng.

Scoring

• Subtask \(1\) (\(16\%\) số điểm): Xâu \(s\) chỉ chứa duy nhất một loại kí tự.
• Subtask \(2\) (\(84\%\) số điểm): không có ràng buộc gì thêm.

Example

abacaba

Alice

iiq

Bob

Có \(n\) học sinh đang xếp hàng từ trái sang phải. Mỗi học sinh được nhận diện bằng mã số sinh viên là \(ID\). Để thách đố học sinh của mình, thầy chủ nhiệm đã phát cho mỗi em học sinh một mảnh giấy để ghi lại mã số sinh viên lần lượt của bạn đứng trước (xếp bên trái) và sau đó là bạn đứng sau mình (xếp bên phải). Trong trường hợp không có bạn nào ở trước hoặc ở sau thì học sinh sẽ điền giá trị 0.

Sau khi đã viết lên giấy xong, thầy bắt đầu thu hồi lại các mảnh giấy và sắp xếp lại các mảnh giấy theo một trình tự ngẫu nhiên. Sau đó thầy hỏi các bạn về thứ tự xếp hàng ban đầu.

Cho dữ liệu về số học sinh \(n\) và nội dung theo đúng trình tự của các mảnh giấy. Hãy cho biết ban đầu, các học sinh đã xếp hàng như thế nào?

Input

• Dòng đầu tiên là số nguyên dương \(n\) (\(n \leq 2 \times 10^5\)) là số học sinh đã tham gia xếp hàng.
• \(n\) dòng tiếp theo: mỗi dòng là hai số nguyên dương \(a_{i}\) và \(b_{i}\) \((a_{i}, b_{i} \leq 10^6)\) lần lượt là \(ID\) của bạn đứng trước và \(ID\) của bạn đứng sau. Nếu \(a_{i} = 0\) thì không có bạn nào đứng trước và nếu \(b_{i} = 0\) thì không có bạn nào đứng sau.

Output

• Gồm \(n\) số nguyên dương là \(ID\) của các bạn theo trình tự xếp hàng ban đầu từ trái sang phải của các bạn học sinh.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(80\%\) số điểm): Không ràng buộc gì thêm.

Example

5
1 3
0 5
5 2
3 4
2 0

1 5 3 2 4