Đề 2 - Ngày 30/09/2026

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Đong nước 100 (p) 1.0s 256M
2 Mua sắm 100 (p) 1.0s 256M
3 Chọn cam 100 (p) 1.0s 256M
4 Hình chữ nhật 100 (p) 1.0s 256M

1. Đong nước

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

Trong phòng thí nghiệm chỉ có đúng ba loại cốc có dung tích là \(5\) (\(ml\)), \(3\) (\(ml\)) và \(2\) (\(ml\)). Hỏi cần ít nhất bao nhiêu lần đong nước để lấy được đúng \(N\) (\(ml\)).

Input

  • Một số nguyên dương duy nhất \(N\) (\(2 \le N \le 10^{18}\)) là số nước cần đong.

Output

  • Một số nguyên dương duy nhất là số lượng lần đong ít nhất thoả mãn yêu cầu đề bài.

Example

Test 1

Input 
12
Output 
3
Note

Đong hai lần bằng cốc \(5\) (\(ml\)) và một lần bằng cốc \(2\) (\(ml\)).

Test 2

Input 
6
Output 
2
Note

Đong hai lần bằng cốc \(3\) (\(ml\)).

2. Mua sắm

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

Một cửa hàng trên sàn thương mại điện tử có \(N\) sản phẩm khác nhau được niêm yết với giá tiền lần lượt là \(A_1, A_2, \dots, A_N\). Việt muốn mua hai sản phẩm, mỗi sản phẩm mua tối đa một lần, sao cho tổng số tiền phải trả nằm trong khoảng từ \(L\) đến \(R\).

Yêu cầu: Em hãy lập trình đưa ra số tiền nhỏ nhất mà Việt phải trả khi mua hai sản phẩm khác nhau mà tổng số tiền phải trả nằm trong đoạn \([L, R]\).

Input

  • Dòng đầu tiên gồm ba số nguyên dương \(N, L, R\) (\(N \le 10^6; 1 \le L \le R \le 10^9\));
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(A_i \le 10^9; 1 \le i \le N\)).

Output

  • Một số nguyên duy nhất là kết quả của bài toán. Dữ liệu đảm bảo luôn tồn tại ít nhất một cách mua thỏa mãn.

Example

Test 1

Input 
5 5 9
8 1 2 2 5
Output 
6
Note

Mua hai sản phẩm có giá tiền là 1 và 5 với tổng số tiền phải trả là 6.

Ràng buộc

  • Có \(80\%\) số test ứng với \(80\%\) số điểm có \(N \le 10^3\);
  • Có \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

3. Chọn cam

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

Một băng chuyền có \(N\) khay đựng cam được đánh số liên tiếp từ \(1\) đến \(N\). Mỗi khay chứa hai quả cam, mỗi quả cam được dán nhãn phân loại từ \(1\) đến \(5\). Trong đợt khuyến mãi này, người mua chỉ được chọn mua một loại cam bất kỳ trong một dãy liên tiếp các khay và mỗi khay người mua phải chọn một trong hai quả cam chứa trong khay đó.

Yêu cầu: Cho biết phân loại các quả cam trong \(N\) khay liên tiếp. Hãy viết một chương trình cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng.

Input

  • Dòng đầu chứa một số nguyên dương \(N\);
  • \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) (\(1 \le A, B \le 5\)) cho biết phân loại của 2 quả cam trong khay tương ứng.

Output

  • Ghi ra hai số nguyên lần lượt cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng. Trong trường hợp có nhiều kết quả giống nhau hãy xuất ra kết quả ứng với loại cam nhỏ nhất.

Example

Test 1

Input 
2
1 2
3 1
Output 
2 1

Test 2

Input 
3
1 2
2 3
4 3
Output 
2 2

Test 3

Input 
5
1 2
2 3
5 2
2 2
1 4
Output 
4 2
Note

Giải thích ví dụ:
Bài toán yêu cầu tìm một dãy các khay liên tiếp dài nhất sao cho tồn tại ít nhất một loại cam \(X\) xuất hiện ở tất cả các khay trong dãy đó (bởi vì mỗi khay người mua bắt buộc phải lấy 1 quả).

  • Ví dụ 1: Ta chọn dãy khay từ \(1\) đến \(2\). Khay \(1\) có cam loại \(1\), khay \(2\) cũng có cam loại \(1\). Vậy khách hàng lấy được liên tục \(2\) quả cam loại \(1\). Kết quả là 2 1.
  • Ví dụ 2: Dãy khay liên tiếp dài nhất chứa cùng một loại cam là dãy từ khay \(1\) đến \(2\) (cùng chứa cam loại \(2\), được \(2\) quả) hoặc từ khay \(2\) đến \(3\) (cùng chứa cam loại \(3\), được \(2\) quả). Do số lượng bằng nhau (\(2\) quả) nên ta ưu tiên in ra loại cam có nhãn nhỏ hơn là loại \(2\). Kết quả là 2 2.
  • Ví dụ 3 (Test mở rộng): Dãy khay từ vị trí số \(1\) đến vị trí số \(4\) đều có chứa cam loại \(2\). Cụ thể: Khay 1 (1, 2), Khay 2 (2, 3), Khay 3 (5, 2), Khay 4 (2, 2). Như vậy ta lấy được tối đa \(4\) quả cam loại \(2\). Khay thứ \(5\) chứa (1, 4) không có cam loại \(2\) nên chuỗi bị ngắt. Kết quả là 4 2.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N \le 100\).
  • Subtask \(2\) (\(40\%\) số điểm): \(N \le 10000\).
  • Subtask \(3\) (\(20\%\) số điểm): \(N \le 100000\).

4. Hình chữ nhật

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

Cho \(N\) hình chữ nhật, mỗi hình chữ nhật \(H\) có chiều dài \(D_H\) và chiều rộng \(R_H\). Hình chữ nhật \(A\) được gọi là lớn hơn hình chữ nhật \(B\), ký hiệu \(A > B\) nếu:

  • Hoặc diện tích hình chữ nhật \(A\) lớn hơn diện tích hình chữ nhật \(B\), tức là:

    \[D_A \times R_A > D_B \times R_B\]

  • Hoặc diện tích hình chữ nhật \(A\) bằng diện tích hình chữ nhật \(B\) và chiều dài hình chữ nhật \(A\) lớn hơn chiều dài hình chữ nhật \(B\), tức là:

    \[D_A \times R_A = D_B \times R_B \text{ và } D_A > D_B\]

Yêu cầu

Hãy tìm độ dài của dãy giảm dài nhất (không cần liên tiếp) các hình chữ nhật. Tức là tìm số \(k\) lớn nhất sao cho tồn tại dãy các chỉ số \(i_1 < i_2 < \cdots < i_k\) mà:

\[H_{i_1} > H_{i_2} > \cdots > H_{i_k}\]

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \le N \le 3000\)).
  • \(N\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(D_i, R_i\) (\(1 \le D_i, R_i \le 10^9\)), lần lượt là chiều dài và chiều rộng của hình chữ nhật thứ \(i\).

Output

  • In ra một số nguyên duy nhất là độ dài của dãy giảm dài nhất tìm được.

Example

Test 1

Input 
4
2 3
3 2
2 2
1 3
Output 
3
Note

Các hình chữ nhật: \(H_1(2, 3)\), \(H_2(3, 2)\), \(H_3(2, 2)\), \(H_4(1, 3)\).
Diện tích tương ứng: \(S_1 = 6, S_2 = 6, S_3 = 4, S_4 = 3\).
So sánh: \(H_2 > H_1 > H_3 > H_4\) (Do \(S_2 = S_1\) nhưng \(D_2 > D_1\)).
Dãy giảm dần dài nhất theo chỉ số tăng dần là:
\(H_1 > H_3 > H_4 \Rightarrow\) Độ dài là 3.