Luyện tập #?

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 THREE (OLP MT&TN 2023 Sơ Loại Không Chuyên) 100 (p) 0.25s 512M
2 TRANSFORM (OLP MT&TN 2023 Sơ Loại Không Chuyên) 100 (p) 1.0s 512M
3 SWORD (OLP MT&TN 2023 Sơ Loại Không Chuyên) 100 (p) 0.35s 512M
4 Những bông hoa (Contest ôn tập #02 THTA 2023) 100 (p) 1.0s 256M
5 Nhảy số học 100 (p) 1.0s 256M

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 
1
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 
3
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 
5 2
6 1
7 3
4 2
10 5
12 4
Output 
0
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 
5 3
10 7
5 3
14 10
1 2
2 1
Output 
3
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. Những bông hoa (Contest ôn tập #02 THTA 2023)

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

Khu vườn của T có \(n\) tảng đá xếp thành một hàng dọc. Một hôm, T nhìn ra vườn và nhận thấy rằng trên một số tảng đá đã mọc ra những bông hoa. Cảm thấy không thoải mái với điều này, T quyết định chọn một nhóm dài nhất các tảng đá nằm kề nhau, và ra vườn nhổ hết các bông hoa trên những tảng đá. T là một người rất lười biếng, nên anh ta muốn công việc của mình phải thật hiệu quả: trong số các tảng đá được chọn, số tảng đá có hoa phải chiếm một tỉ lệ ít nhất là \(\dfrac{u}{v}\). Đồng thời, T cũng muốn dọn dẹp càng nhiều tảng đá càng tốt (chuỗi các tảng đá được chọn phải càng dài càng tốt). Các bạn hãy cho biết chuỗi các tảng đá dài nhất mà T có thể chọn bao gồm bao nhiêu tảng đá.

Input

  • Ba dòng đầu tiên, mỗi dòng số tự nhiên tương ứng \(n, u, v\) (\(n \le 10^5; u \le v \le 10^9\))
  • Dòng thứ tư gồm một xâu \(S\) gồm \(n\) kí tự tượng trưng cho trạng thái có/không có hoa của các viên đá. Kí tự thứ \(i\) là . nếu viên đá thứ \(i\) không có hoa và là # nếu viên đá thứ \(i\) có hoa.
  • Dữ liệu đầu vào đảm bảo có ít nhất một viên đá có hoa.

Output

  • In ra một số nguyên duy nhất là độ dài chuỗi đá dài nhất tìm được.

Example

Test 1

Input 
11 
12 
20
...##.##...
Output 
6
Note

Ta có thể chọn chuỗi đá từ vị trí thứ \(3\) đến vị trí thứ \(8\) hoặc từ vị trí thứ \(4\) đến vị trí thứ \(9\). Các chuỗi đá này có tỉ lệ số tảng đá có hoa là \(\dfrac{4}{6} \ge \dfrac{12}{20}\).

Test 2

Input 
11
16
20
...##.##...
Output 
5
Note

Ta có thể chọn chuỗi đá từ vị trí thứ \(4\) đến vị trí thứ \(8\). Chuỗi đá này có tỉ lệ số tảng đá có hoa là \(\dfrac{4}{5} \ge \dfrac{16}{20}\).

Test 3

Input 
11 
1 
1
...#####...
Output 
5
Note

Ta có thể chọn chuỗi đá từ vị trí thứ \(4\) đến vị trí thứ \(8\) gồm toàn những tảng đá có hoa.

Scoring

  • Subtask \(1\) (\(25\%\)): \(n \le 100\)
  • Subtask \(2\) (\(25\%\)): \(n \le 1000\)
  • Subtask \(3\) (\(25\%\)): \(u = v = 1\)
  • Subtask \(4\) (\(25\%\)): Không có giới hạn gì thêm

5. Nhảy số học

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

Từ một số tự nhiên \(n\) ta có thể "nhảy" lên bằng cách cộng thêm số tận cùng của \(n\). Ví dụ: số \(1234\) ta có thể "nhảy" đến số \(1238 = 1234 + 4\).

Viết chương trình tính giá trị \(n\) sau khi "nhảy" được \(k\) lần.

66% test: \(k \le 1000\).

Dữ liệu vào

  • Dòng đầu tiền chứa số nguyên dương \(t\) là số câu hỏi. \((t \le 100)\)
  • \(t\) dòng tiếp theo, mỗi dòng là hai giá trị \(n\) và \(k\) \((0 \le n, k < 2^{31})\)

Dữ liệu ra

  • \(t\) dòng, với mỗi dòng in ra giá trị \(n\) sau khi nhảy \(k\) lần.

Ví dụ

Input 
2
9 3
11 0
Output 
32
11
Note 
9 + 9 = 18
18 + 8 = 26
26 + 6 = 32