OLP MT&TN 2023 Sơ Loại Không Chuyên - Bộ đề bài

1. THREE (OLP MT&TN 2023 Sơ Loại Không Chuyên)

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

Cho một tập hợp gồm \(a\) số \(1\), \(b\) số \(2\) và \(c\) số \(3\). Tìm cách chia tập hợp này thành một hay nhiều tập hợp con sao cho mỗi số thuộc duy nhất một tập hợp con và số lượng tập hợp con có tổng bằng \(3\) là lớn nhất có thể.

Input

Một dòng duy nhất chứa ba số nguyên \(a\), \(b\) và \(c\) \((0 \leq a, b, c \leq 10^{9})\).

Output

In ra một số nguyên duy nhất là số lượng tập hợp con có tổng bằng \(3\) lớn nhất tìm được.

Example

Test 1

Input

3 0 0

Output

Note

Trong ví dụ đầu tiên, ta có thể dùng cả \(3\) số để tạo một tập hợp con duy nhất có tổng bằng \(3\) (đó là \(\{1, 1, 1\}\)).

Test 2

Input

4 2 1

Output

Note

Trong ví dụ thứ hai, ta có thể chia thành \(4\) tập hợp là \(\{1, 2\}, \{1, 2\}, \{3\}, \{1, 1\}\). Trong đó, có \(3\) tập hợp con có tổng bằng \(3\).

2. TRANSFORM (OLP MT&TN 2023 Sơ Loại Không Chuyên)

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

An là một cậu bé yêu thích Số học. Mỗi khi rảnh, cậu ấy sẽ tự nghĩ ra cho mình những trò chơi thú vị với những con số. Chủ Nhật ngày hôm ấy, cậu đã nghĩ ra trò chơi như sau:

Đầu tiên ta sẽ có một số nguyên không âm \(A\), ta được thực hiện hai thao tác:

Gấp đôi giá trị của \(A\).
Viết thêm số \(1\) ở đằng sau số \(A\) (Số được biểu diễn ở dạng thập phân).

An sau đó là nghĩ ra rất nhiều số \(A\) khác nhau, với mỗi số lại biến đổi một cách khác nhau và viết các con số ấy lên các tờ giấy. Tuy nhiên, vì là một cậu bé đãng trí, An nhanh chóng quên mất mình đã biến đổi con số nào thành con số nào. Bạn hãy trả lời giúp An nhé.

Input

Dòng đầu tiên chứa số nguyên \(Q\) \((1 \leq Q \leq 100)\) là số lượng câu hỏi.
Trong \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) \((1 \leq A, B \leq 10^{9})\).

Output

In ra \(Q\) dòng, in ra YES nếu từ \(A\) có thể tạo ra \(B\) bằng không, một hay nhiều thao tác nêu trên hoặc NO nếu ngược lại.

Example

Test 1

Input

2
2 162
4 42

Output

YES
NO

Note

Trong câu hỏi đầu tiên, An sẽ thực hiện các thao tác để biến đổi số \(2\) như sau: \(2 \rightarrow 4 \rightarrow 8\rightarrow 81 \rightarrow 162\).
Trong câu hỏi thứ hai, không có cách nào mà An có thể biến đổi được từ số \(4\) thành số \(42\) bằng các thao tác của mình.

3. SWORD (OLP MT&TN 2023 Sơ Loại Không Chuyên)

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

Robin đang chơi một trò chơi hành động thế giới mở nổi tiếng vừa ra mắt gần đây. Trò chơi có rất nhiều con quỷ, mỗi con quỷ đều có điểm sức mạnh và điểm thưởng khi bị tiêu diệt. Tuy nhiên, cậu chỉ cần tiêu diệt \(n\) con quỷ quan trọng (boss) để có thể hoàn thành trò chơi.

Ban đầu Robin có \(S\) điểm sức mạnh, điểm sức mạnh cho biết cậu có thể tiêu diệt những con quỷ có điểm sức mạnh nhỏ hơn mình. Khi gặp một con quỷ có thể tiêu diệt và có điểm thưởng \(g\), điểm sức mạnh của cậu được tăng lên \(g\) đơn vị.

Do Robin là một người chỉ thích đánh boss và không muốn mất thời gian với những con quỷ không quan trọng, bạn hãy giúp Robin xác định xem cậu có thể tiêu diệt tối đa bao nhiêu con boss? Biết rằng, đây là một trò chơi thế giới mở và Robin có thể chọn boss để đánh tùy theo ý của cậu.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(S\) \((1 \leq n \leq 10^{5}, 1 \leq S\le 10^{9})\) lần lượt là số lượng boss trong game và số điểm sức mạnh ban đầu của Robin.
Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(p_{i}\) và \(g_{i}\) \((1 \leq p_{i}, g_{i} \leq 10^{9})\) lần lượt là điểm sức mạnh và điểm thưởng của con boss thứ \(i\).

Output

In ra một số nguyên duy nhất là số lượng con boss tối đa mà Robin có thể tiêu diệt nếu bỏ qua các con quỷ phụ.

Scoring

Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{3}\).
Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

Note

Trong ví dụ đầu tiên, có \(5\) con boss và Robin có \(2\) điểm sức mạnh.
Do không có con boss nào có điểm sức mạnh nhỏ hơn điểm sức mạnh ban đầu của Robin nên cậu không thể tiêu diệt được con boss nào.

Test 2

Input

Output

Note

Trong ví dụ tiếp theo, có \(4\) con boss và Robin có \(3\) điểm sức mạnh.
Robin có thể tiêu diệt các con boss như sau: đầu tiên, cậu diệt con boss có điểm sức mạnh là \(2\) và được tăng thêm \(1\) điểm sức mạnh.
Lúc này, Robin có \(4\) điểm sức mạnh, cậu đi diệt con boss có điểm sức mạnh là \(1\) và được tăng thêm \(2\) điểm sức mạnh.
Lúc này, Robin có \(6\) điểm sức mạnh, cậu đi diệt con boss có điểm sức mạnh là \(5\) và được tăng thêm \(3\) điểm sức mạnh.
Đến đây, điểm sức mạnh của Robin là \(9\) và cậu không còn con boss nào có điểm sức mạnh nhỏ hơn để tiêu diệt nữa. Như vậy, đáp án cho ví dụ này là \(3\).

4. COLORBOX (OLP MT&TN 2023 Sơ Loại Không Chuyên)

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

Vì có kết quả cao trong kỳ thi học sinh giỏi vừa qua nên Phát được mẹ thưởng cho một hộp màu tuyệt đẹp. Bộ màu ấy bao gồm \(n\) cây màu được xếp theo thứ tự từ trái qua phải, cây màu thứ \(i\) (\(1 \leq i \leq n\)) có màu được mô tả bởi một số nguyên \(a_i\).

Tuy nhiên, có một số sơ suất trong quá trình sản xuất nên hộp màu của Phát có thể chứa một số cây màu giống nhau. Vì là một người thích sự hoàn hảo nên Phát muốn bỏ bớt một số cây màu sao cho những cây màu còn lại đôi một phân biệt với nhau.

Để làm vậy, Phát sẽ chọn nhiều nhất một đoạn con gồm các cây màu liên tiếp rồi bỏ chúng đi, tức là, Phát sẽ chọn hai số nguyên \(l\) và \(r\) thoả mãn \(1 \leq l \leq r \leq n\) rồi bỏ các cây màu từ vị trí \(l\) đến vị trí \(r\) và giữ nguyên các cây màu còn lại.

Hãy giúp Phát tìm ra số lượng cây màu bị bỏ đi ít nhất sao cho các cây màu còn lại thoả mãn điều kiện.

Input

Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^6\)) là số lượng cây màu.
Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq n\)).

Output

In ra một số nguyên duy nhất là số lượng cây màu bị bỏ đi.

Scoring

Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{2}\).
Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\).
Subtask \(3\) (\(30\%\) số điểm): \(n \leq 10^{5}\).
Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

4
1 1 2 2

Output

Note

Trong ví dụ đầu tiên, Phát có thể bỏ đi các cây màu từ vị trí \(2\) đến vị trí \(3\).

Test 2

Input

5
1 4 1 4 5

Output

Note

Trong ví dụ thứ hai, Phát có thể chọn một trong ba cách sau:
Bỏ đi các cây màu từ vị trí \(1\) đến vị trí \(2\).
Bỏ đi các cây màu từ vị trí \(2\) đến vị trí \(3\).
Bỏ đi các cây màu từ vị trí \(3\) đến vị trí \(4\).