CPP Basic 2 - Khóa 2024/12 - Middle Test - Bộ đề bài

1. Sự kiện lịch sử

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

Ryze rất thích học và rất siêng năng làm bài tập về nhà của mình. Ryze học rất giỏi các môn khoa học tự nhiên. Tuy nhiên cậu lại gặp rất nhiều vấn đề ở môn lịch sử.

Lịch sử thế giới bao gồm đúng $N$ sự kiện. Sự kiện thứ $i$ được bắt đầu từ năm $a_i$ và kết thúc vào năm $b_i$ ($a_i < b_i$). Ryze dễ dàng nhớ được các sự kiện lịch sử (Ryze được thừa hưởng trí nhớ tuyệt vời của bố cậu). Tuy nhiên giáo viên dạy lịch sử của cậu là cô giáo Fiora đã giao cho cậu một bài tập khó hơn. Giáo viên của Ryze cho rằng sự kiện $j$ chứa đựng sự kiện $i$ nếu $a_j < a_i$ và $b_j > b_i$.

Nhiệm vụ của bạn là tìm số sự kiện được chứa đựng trong một số sự kiện khác.

Input

Dòng đầu chứa số nguyên $N\ (1\leq N\leq 10^5$) là số sự kiện xảy ra trong lịch sử.
$N$ dòng tiếp theo, dòng thứ $i + 1$ chứa 2 số nguyên $a_i,b_i\ (1\leq a_i < b_i\leq 10^9)$ là thời gian bắt đầu và kết thúc của sự kiện thứ $i$.

Output

Số nguyên duy nhất là đáp án.

Example

Test 1

Input

Output

2. Lì Xì

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

Nhân dịp Tết, ba bé Bo chuẩn bị $n$ túi lì xì cho bé Bo. Trong túi thứ $i$ có số tiền là $a_i$ và một số nguyên $b_i$ $(b_i ≥ 0)$. Nếu $b_i > 0$ thì bé Bo được phép chọn thêm $b_i$ túi lì xì khác. Việc chọn thêm này là tích lũy. Đầu tiên, bé Bo chọn một túi bất kỳ, sau đó giả sử bé Bo đang có tổng số tiền là $A$ và số túi được phép chọn thêm là $B$ $(B > 0)$, nếu bé Bo chọn thêm túi thứ $i$ thì tổng số tiền là $A + a_i$ và tổng số túi được chọn thêm là $B -1 + b_i$. Cứ như vậy cho đến khi không được phép chọn thêm $(B=0)$ hoặc đã chọn hết $n$ túi.

Yêu cầu: Bạn hãy giúp bé Bo xác định thứ tự chọn túi sao cho tổng số tiền bé có được là lớn nhất nhé.

Input

Dòng đầu tiên là số nguyên $n$ $(1 \leq n \leq 100)$.
Trong $n$ dòng tiếp theo, dòng thứ $i$ gồm $2$ số nguyên $a_i$ và $b_i$ cách nhau một khoảng trắng $(1 \leq a_i \leq 100, 0 \leq b_i \leq 100)$.

Output

Là số nguyên xác định số tiền nhiều nhất mà bé Bo có được.

Example

Test 1

Input

Output

Test 2

Input

Output

Note

Trong test 1, do chỉ chọn được 1 túi nên chọn túi có số tiền nhiều nhất là 2.
Trong test 2, đầu tiên chọn túi 3, sau đó chọn túi 1 và tiếp theo là túi 2.

3. Mua chocolate

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

Những con bò rất thích ăn Sô-cô-la, nên Farmer John quyết định mua một ít cho chúng.

Cửa hàng có $N$ loại sô-cô-la (được đánh số từ $1$..$N$) với số lượng mỗi loại không hạn chế. Loại thứ $i$ có giá $P_i$ và có đúng $C_i$ con bò muốn ăn loại Sô-cô-la ấy. Farmer John có $B$ để mua Sô-cô-la cho lũ bò.

Yêu cầu: Hỏi số bò tối đa mà Farmer John có thể phục vụ là bao nhiêu ? Biết rằng mỗi con bò chỉ thích một loại sô-cô-la, và nó chỉ được ăn loại sô-cô-la ấy.

Dữ liệu vào

Dòng đầu tiên là hai số nguyên $N$ và $B$.
N dòng tiếp theo, dòng thứ $i+1$ là hai số nguyên dương $P_i$ và $C_i$.

Kết quả

Gồm một số duy nhất là kết quả.

Sample Input 1

Sample Output 1

Giải thích
FJ sẽ mua như sau:

+Mua 3 gói sô-cô-la loại 1 mất 3*5= 15$.

+Mua 1 gói sô-cô-la loại 2 mất 1*1= 1$.

+Mua 2 gói sô-cô-la loại 3 mất 2*10= 20$

+Mua 2 gói sô-cô-la loại 4 mất 2*7= 14$.

Tổng cộng hết :15+1+20+14=50$, và FJ đã phục vụ được 8 con bò.

Giới hạn

$1 \le N \le 10^5$
$1 \le B \le 10^{18}$
$1 \le C_i \le 10^{18}$
$1 \le P_i \le 10^{18}$

Nguồn: SPOJ

4. Khẩu trang

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

Khi nghe tin Đà Nẵng có ca dịch Covid mới, Khôi liền chạy tới tiệm thuốc mua khẩu trang.

Cửa hàng có $n$ hộp khẩu trang. Giá của mỗi hộp khẩu trang được biểu diễn bằng mảng $A$. Hộp thứ $i$ có giá $A_i$ đồng.

Bất chợt có một người đàn ông tên là Small đến hỏi Khôi vài câu hỏi. Mỗi câu hỏi, Khôi sẽ trả lời số hộp khẩu trang có giá tiền nhỏ hơn $M$ đồng.

Input

Dòng đâu tiên chứa số nguyên dương $N$ $(N \leq 10^5)$.
Dòng 2 chứa $N$ số nguyên dương $A_i$ $(A_i \leq 10^9)$.
Dòng thứ 3 chứa số nguyên $Q$ $(Q \leq 10^5)$ - là số câu hỏi.
$Q$ dòng tiếp theo, mỗi dòng chứa $1$ giá tri $M$ $(M \leq 10^9)$.

Output

Gồm $Q$ dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

Test 1

Input

Output

5. TAMHOP - Bộ tam hợp (HSG'13)

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

Cho dãy số nguyên $a_1, a_2, ..., a_n$, các số khác nhau từng đôi một ($3 <= N <= 5000$; với mọi i ta có $|a_i| <= 10^6$). Bộ ba số $a_i, a_j, a_k (i <> j <> k)$ được gọi là Bộ tam hợp nếu có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.

Yêu cầu:

Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị của ba số là lớn nhất.

Input

Dòng 1 chứa số N;
Dòng 2 chứa n số $a_1, a_2, ..., a_N$ cách nhau ít nhất một dấu cách

Output

Dòng 1 ghi một số nguyên dương là số lượng bộ tam hợp tìm được;
Dòng 2 ghi tổng giá trị ba số của bộ tam hợp là lớn nhất.

Example

Test 1

Input

7
6 1 9 2 3 4 8

Output

5
18

6. Gàu nước

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

Rùa có một cái xô nước đang chứa $L$ lít nước. Rùa muốn lấy cái xô làm việc khác nên Rùa muốn chuyển lượng nước sang những chiếc gàu nước.
Biết rằng, nhà Rùa có vô tận những chiếc gàu thuộc 2 loại, loại chứa được $5$ lít và loại chứa được $2$ lít. Hỏi, tổng số gàu ít nhất Rùa cần sử dụng để đong hết $L$ lít nước là bao nhiêu?

Input

Một dòng duy nhất chứa một số nguyên $L$ $(1 \leq L \leq 10^{18})$

Output

In ra tổng số gàu ít nhất Rùa cần sử dụng

Test 1

Input

Output

Note

Với $L=27$, Rùa có thể sử dụng $5$ gàu nước 5 lít và $1$ gàu nước 2 lít.

Test 2

Input

Output

Note

Với $L=30$, Rùa có thể sử dụng $6$ gàu nước 5 lít.