Lớp lập trình 1 - Sắp xếp - Đề ôn 1

Tối thứ 5 sẽ chấm bài PHUDOAN1 và các bài trong đề này. Các bạn nhớ làm đầy đủ.

Thời gian: 120 phút

Bài 1.       NUMCON Ghép số lớn OLPK10 2010

Input	Output
2 20 004 66	66220004
3	3
56465 2165 14 231541 1	564652315412165141
32 51 14 5 12 13 7 2134 2 1 9	9755132221341413121

Vaxia đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với anh trai Petia về thành quả vừa đạt được. Tuy nhiên,  khi Vaxia vừa ra khỏi phòng để gọi anh trai thì cô em Kachia chạy vào phòng và xé rách cuộn giấy thành một số mảnh. Kết quả là trên mỗi mảnh có một hoặc vài kí số theo thứ tự đã viết.

Bây giờ Vaxia không thể nhớ chính xác mình đã viết số gì. Vaxia chỉ nhớ rằng đó là một số rất lớn.

Để làm hài lòng cậu em trai, Petia quyết định truy tìm  số nào là lớn nhất mà Vaxia đã có thể viết lên cuộn giây trước khi bị xé. Bạn hãy giúp Petia làm việc này.

Input

-         Ghi một hoặc nhiều dòng. Mỗi dòng ghi một dãy kí số. Số dòng không vượt quá 100. Mỗi dòng ghi từ 1 đến 100 kí số. Bảo đảm rằng có ít nhất một dòng mà kí số đầu tiên khác 0.

Output: Ghi ra số lớn nhất đã có thể viết trên cuộn giấy trước khi bị xé rách.

Bài 2.       INSUL Cách nhiệt

Input	Output
4 5 4 1 7	24

Cho một dãy N viên gạch lần lượt có độ cách nhiệt là các số a₁.. a_N. Nếu xếp lần lượt các viên gạch theo trình tự đó thì độ cách nhiệt cả khối là a₁ + a₂ + ... + a_N + max(0, a₂ - a₁) + max(0, a₃ - a₂) + ... + max(0, a_N - a_{N - 1}). Nhiệm vụ của bạn là tìm cách xếp sao cho độ cách nhiệt của cả khối là lớn nhất có thể.

Dữ liệu

·        Dòng đầu ghi số nguyên dương N (0 < n ≤ 10⁵).

·        N dòng sau mỗi dòng ghi một số a_i ( 1 ≤ i ≤ N và 1 ≤ a_i ≤ 10⁴).

Kết quả: Độ cách nhiệt lớn nhất có thể.

Bài 3.       CBUYING Chocolate Buying

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ò.

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.

Input

·        Dòng đầu tiên là hai số nguyên N và B. (1 ≤ N ≤ 10⁵; 1 ≤ B ≤ 10¹⁸)

·        N dòng tiếp theo, dòng thứ i+1 là hai số nguyên dương P_i và C_i. (1 ≤ P_i, C_i ≤ 10¹⁸)

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

Input	Output
5 50 5 3 1 1 10 4 7 2 60 1	8

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ò.