Hàng đợi ưu tiên

Có \(N\) hạt xốp, hạt thứ \(i\) có khối lượng \(W_i\), được thả lần lượt xuống một ống nước đặc biệt được thiết kế sao cho tại mỗi thời điểm chỉ có một hạt xốp nhẹ nhất nổi lên trên bề mặt. Trước mỗi lần thả, hạt xốp đang nổi trên bề mặt sẽ bị ngấm nước và tăng gấp đôi khối lượng. Hỏi sau khi thả hạt xốp cuối cùng vào ống thì khối lượng xốp tăng so với tổng khối lượng ban đầu là bao nhiêu ?

Input

• Dòng 1: Số nguyên dương \(N\ (N≤10^5 )\)
• Dòng 2: \(N\) số nguyên dương \(W_1,…W_N\ (W_i≤100\ ∀i=1..N)\)

Output

- Ghi ra một số duy nhất là đáp án của bài toán

Scoring

Example

3
2 1 3 

3

HT AIRLINE là một hãng hàng không danh tiếng ở Việt Nam, tuy nhiên, để tồn tại trong cơn bão suy thoái kinh tế, Ban giám đốc quyết định giảm chi phi tiền lương cho phi công càng nhiều càng tốt.

HT airline có tất cả \(N\) phi công (\(N\) là số chẵn), các phi công được đánh số từ 1 đến \(N\) (Phi công 1 là phi công trẻ nhất, phi công \(i\) là phi công có tuổi cao thứ \(i\),… phi công \(n\) là phi công cao tuổi nhất). HT airline cần chính xác \(\dfrac{N}{2}\) phi hành đoàn, mỗi phi hành đoàn gồm 2 phi công (một lái chính và một lái phụ), lái chính phải nhiều tuổi hơn lái phụ. Hợp đồng mà công ty kí với các phi công có 2 điều khoản rõ ràng: tiền lương khi là lái chính và tiền lương khi là lái phụ. Rõ ràng, đối với 1 phi công, tiền lương lái chính bao giờ cũng cao hơn tiền lương khi lái phụ. Tuy nhiên, với một phi hành đoàn, có thể tiền lương của lái chính lại thấp hơn lái phụ.

Để giảm chi phí trả tiền lương, HT phải xác định một cách phân chia tối ưu \(\dfrac{N}{2}\) phi hành đoàn.

Bạn hãy giúp HT viết chương trình xác định số tiền tối thiểu để trả lương cho \(N\) phi công.

Input

• Dòng 1 : Số nguyên dương \(N\), là số phi công ở HT airline (\(2≤N≤10000\); \(N\) là số chẵn).
• \(N\) dòng tiếp theo, dòng thứ \(i\) là thông tin về phi công \(i\) : gồm hai số \(a\) và \(c\) viết cách nhau 1 dấu cách trống, tương ứng là tiền lương khi lái chính và tiền lương khi lái phụ. (\(1≤a≤c≤100.000\))

Output

• Ghi ra một số nguyên duy nhất là tiền lương tối thiểu phải trả cho \(N\) phi công.

Scoring

Example

6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000

32000

6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000

33000

Bước vào tiểu học, Bé Bi được cô giáo chủ nhiệm cho làm lớp trưởng. Nhân dịp kỷ niệm ngày thành lập trường, Bé Bi tổ chức cho cả lớp chơi 1 trò chơi sau:
Có \(N\) đống sỏi xếp thành một hàng, đống thứ \(i\) có \(A_i\) viên sỏi. Ta có thể ghép hai đống sỏi bất kỳ thành một đống và mất một chi phí bằng 5% tổng hai đống sỏi đó. Hãy tìm cách ghép \(N\) đống sỏi này thành một đống với chi phí là nhỏ nhất.
Ví dụ: Nếu chúng ta có 4 đống sỏi với số lượng sỏi là 10, 11, 12 và 13.

• Bước 1: Ghép 2 đống 10 và 11 thành 1 đống có số lượng 21 (chi phí là \(1.05\))
• Bước 2: Ghép đống 21 vừa thu được với đống 12 thành đống có số lượng 33 (chi phí \(1.65\))
• Bước 3: Ghép đống 33 vừa thu được với đống 13 thành 1 đống cuối cùng có số lượng sỏi là 46 (chi phí \(2.3\))
• Vậy tổng chi phí là \(5.00\). Tuy nhiên đây không phải là phương án ghép đống tối ưu, chúng ta có phương án ghép 4 đống này thành 1 đống với chi phí nhỏ nhất là \(4.60\).

Các bạn hãy tìm giúp Bé Bi phương án chơi tối ưu nhé!

Input

• Dòng 1: Số nguyên dương \(N\ (2≤N≤100.000)\) là số đống sỏi.
• Dòng tiếp theo, ghi \(N\) số nguyên dương, tương ứng là số lượng sỏi trong từng đống. Số lượng sỏi không vượt quá 10.000.

Output

• Đưa ra một số thực duy nhất là chi phí nhỏ nhất phải trả để ghép N đống sỏi thành 1 đống. Kết quả ghi dưới dạng 2 chữ số sau dấu thập phân.

Scoring

Example

4
10 11 12 13

4.60

2
1 1

0.10

Tại của hàng pizza của Mr. Hải Dương có một điểm khác biệt với các cửa hàng khác, nếu tại của hàng bình thường thì khách hàng đến trước sẽ được phục vụ trước, khách hàng đến sau sẽ được phục vụ sau thì ở của hàng Pizza của Mr. Hải Dương sẽ phục vụ theo tiêu chí thời gian đợi trung bình của khách hàng là nhỏ nhất, vì vậy Anh ta sẽ quyết định phục vụ khách hàng nào trước chứ không phụ thuộc vào khách đến sớm hay muộn.
Mỗi loại bánh pizza khác nhau thì cần một khoảng thời gian khác nhau để làm bánh. Vì chỉ có một lò nướng bánh nên trong thời gian nướng một chiếc bánh pizza này thì Anh ta không thể nướng thêm chiếc bánh nào khác.
Ví dụ: Nếu cửa hàng có 3 khách đến vào các thời điểm \(t_1=0,t_2=1\) và \(t_3=2\) và yêu cầu 3 chiếc bánh pizza có thời gian làm bánh là \(l_1=3,l_2=9,l_3=6\). Nếu theo tiêu chí khách đến trước được phục vụ trước thì thời gian chờ đợi của ba khách hàng lần lượt là \(q_1=3,q_2=11,q_3=16\). Như vậy thời gian chờ trung bình là \((3+11+16)/3=10\). Đây không phải là phương án tối ưu theo tiêu chí thời gian chờ trung bình nhỏ nhất. Mr. Hải Dương sẽ lựa chọn phục vụ theo thứ tự là khách 1, khách 3 và sau đó mới là khách 2. Khi đó thời gian chờ của ba khách lần lượt là \(q_1=3,q_2=17,q_3=7\). Như vậy thời gian chờ trung bình là \((3+17+7)/3=9\).
Yêu cầu: Bạn hãy giúp Mr. Hải Dương tính thời gian chờ trung bình nhỏ nhất. Chỉ cần in ra phần nguyên của thời gian chờ trung bình nhỏ nhất.
Ghi chú:

• Thời gian chờ của một khách hàng là độ chênh lệch giữa hai thời điểm: thời điểm khách hàng đến của hàng và thời điểm khách hàng rời cửa hàng;
• Mr. Hải Dương không biết trước các yêu cầu của khách hàng, tức là đến thời điểm \(t_i\), khi khách hàng \(i\) tới cửa hàng thì Mr. Hải Dương mới biết khách hàng \(i\) yêu cầu bánh pizza làm trong thời gian \(l_i\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\ (1≤n≤10^5)\) là số khách hàng;
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(t_i,l_i\) \((0≤t_i≤10^9,1≤l_i≤10^9)\) mô tả khách hàng \(i\) đến của hàng vào thời điểm \(t_i\) và chiếc bánh khách hàng \(i\) cần sẽ mất thời gian làm bánh là \(l_i\).

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là phần nguyên của thời gian chờ trung bình nhỏ nhất.

Scoring

Example

3
0 3
1 9
2 5

8

4
0 3
20 1
1 9
2 6

7

HD muốn tất cả các bánh quy của anh ấy đều có độ ngọt \(≥K\). Để làm được điều này, Anh ấy đã làm như sau:

• Chọn 2 bánh quy có độ ngọt nhỏ nhất và nhỏ nhì
• Trộn hai bánh này vào nhau, nướng lại thành 1 bánh với độ ngọt mới \(=(1 \times \text{độ ngọt nhỏ nhất} + 2 \times \text{độ ngọt nhỏ nhì})\)

Anh ấy lặp đi lặp lại thao tác như vậy cho đến khi tất cả các bánh quy đều có độ ngọt \(≥K\). Bạn hãy cho biết Anh ấy phải nướng lại bao nhiêu lần để được như vậy?

Input

• Dòng 1: Hai số nguyên dương \(n\ (1≤n≤10^6)\) là số lượng bánh quy và số nguyên \(K\ (0≤K≤10^9)\)
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,…,a_n\) (\(0≤a_i≤10^6\)), \(a_i\) là độ ngọt của bánh quy thứ \(i\)

Output

• Ghi ra một số nguyên duy nhất là số lần nướng lại bánh, ghi \(-1\) nếu không thể đạt được tất cả các bánh quy đều có độ ngọt \(≥K\)

Scoring

Example

6 7
1 2 3 9 10 12     

2

Cho dãy số \(a_1,a_2,…,a_n\). Ta có định nghĩa \(median\) của một dãy số như sau:

• Nếu độ dài dãy là lẻ thì median = phần tử giữa của dãy sau khi sort. Ví dụ \(a={1,2,3}\) thì \(median =2\)
• Nếu độ dài dãy là chẵn thì \(median =\) trung bình cộng của hai phần tử giữa của dãy sau khi sắp xếp. Ví dụ \(a={1,2,3,4}\) thì \(median=\dfrac{(2+3)}{2}=2.5\)

Yêu cầu: Cho \(n\) số nguyên, với mỗi lần nhập \(a_i\) bạn phải thực hiện:

• Thêm \(a_i\) vào dãy số
• Tính \(median\) cho dãy số mới cập nhật
• In ra \(median\) của các dãy số mới cập nhật trên từng dòng, mỗi \(median\) in ra theo định dạng 1 chữ số thập phân sau dấu phẩy.

Input

• Dòng 1: số nguyên dương \(n\ (1≤n≤10^5)\)
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(a_i\ (0≤a_i≤10^5)\)

Output

• Ghi ra \(n\) số thực trên \(n\) dòng theo thứ tự là median của các dãy số.

Scoring

Example

6
12
4
5
3
8
7

12.0
8.0
5.0
4.5
5.0
6.0

Cho dãy số \(a_1,a_2,…,a_n\). Với mỗi chỉ số \(i\), bạn hãy cho biết tích của ba số hạng lớn nhất, lớn nhì và lớn ba của các số trong đoạn \([1;i]\).

Input

• Dòng 1: số nguyên dương \(n\ (1≤n≤10^5)\)
• Dòng tiếp theo, chứa dãy số \(a_1,a_2,…,a_n\ (0≤a_i≤10^6)\)

Output

• Ghi ra \(n\) dòng, mỗi dòng tương ứng với kết quả yêu cầu. Nếu không tồn tại số lớn nhì và lớn thứ 3 thì ghi -1

Scoring

Example

5  
1 2 3 4 5

-1
-1
6
24
60

Sân vận động Lạch Tray tổ chức trận chung kết Champion league giữa MU và Barce, hiện tại còn \(M\) hàng ghế trống (đánh số từ 1 đến \(M\)), hàng ghế \(i\) còn trống \(x_i\) ghế. Hiện tại xếp hàng ngoài cổng sân vận động Lạch Tray có \(n\) người mua vé, mỗi người đến lượt mình được mua 1 vé do ban tổ chức đưa (không có sự lựa chọn). Giá vé được quy định như sau: tại thời điểm mua vé, nếu nhận được vé ở hàng \(i\) thì giá vé bằng số ghế còn trống của hàng \(i\).

Yêu cầu: Bạn hãy giúp BTC bán được nhiều tiền nhất?

Input

• Dòng 1: Hai số nguyên dương \(m,n\ (1≤m,n≤10^6)\)
• Dòng tiếp theo, chứa dãy số \(x_1,x_2,…,x_m\ (0≤x_i≤10^6,x_1+x_2+⋯+x_m≥n)\)

Output

• Ghi ra một số nguyên duy nhất là số tiền lớn nhất thu được.

Scoring

Example

3 4
1 2 4

11

Bản đồ thành phố HP như hệ trục tọa độ Oxy, HD đang ở tọa độ \(O(0;0)\), Anh ấy muốn đến nghỉ tại Hostel gần thứ \(K\) của thành phố HP.
Bạn có \(q\) truy vấn như sau:

• \(1\ x\ y\): đưa hostel ở tọa độ \((x;y)(-10^6≤x,y≤10^6)\) vào danh sách khách sạn mà HD biết.
• \(2\): đưa ra khoảng cách của khách sạn gần thứ \(K\) trong danh sách của HD. Biết rằng khoảng cách hai điểm \(A(x_1;y_1 ),B(x_2;y_2)\) là \(AB=(x_2-x_1 )^2+(y_2-y_1 )^2\)

Biết rằng:

• Trong mọi truy vấn 2, HD luôn ở tọa độ \(O(0;0)\)
• Có ít nhất \(k\) truy vấn 1 trước khi có truy vấn 2.

Input

• Dòng 1: Hai số nguyên dương \(Q, K\ (0≤K≤Q≤10^5)\)
• \(Q\) dòng tiếp theo chứa các truy vấn

Output

• Ghi ra trên từng dòng, mỗi dòng là kết quả ứng với truy vấn 2.

Scoring

Example

9 3
1 10 10
1 9 9
1 -8 -8
2
1 7 7
2
1 6 6 
1 5 5
2

200
162
98

Cho dãy \(a_1,a_2,…a_n\) và \(q\) truy vấn như sau

• \(K\ S\): đưa ra giá trị nhỏ thứ \(K\)
• \(K\ L\): đưa ra giá trị lớn thứ \(K\).

Input

• Dòng 1: Hai số nguyên dương \(N\ (0≤N≤10^6)\)
• Dòng 2: \(N\) số nguyên dương \(a_1,a_2,…a_n\ (1≤a_i≤10^9 )\)
• Dòng 3: Số nguyên dương \(Q\ (1≤Q≤10^6)\)
• \(Q\) dòng tiếp theo chứa các truy vấn dạng \(K\ S(L)(1≤K≤10^5)\)

Output

• Ghi ra trên từng dòng, mỗi dòng là kết quả ứng với truy vấn.

Scoring

Example

5
1 2 3 4 5
3
3 L
3 S
1 L

3
3
5

HD rất thích chơi bài ma thuật, vào một ngày đẹp trời, anh ta bước vào một cửa hàng để mua ít nhất một số quân bài biết rằng:

• Các quân bài được đặt cạnh nhau trên 1 bàn dài đánh số từ 1 đến \(n\), quân bài i có chỉ số sức mạnh là \(a_i\)
• HD phải mua một dãy liên tiếp các quân bài và các quân bài này phải có chỉ số sức mạnh đôi một khác nhau (tức là không có hai quân bất kỳ nào cùng chỉ số)
• Tổng chỉ số sức mạnh các quân bài là lớn nhất có thể?

Input

• Dòng 1: Số nguyên dương \(N\ (0≤N≤10^5)\)
• Dòng tiếp theo chứa \(N\) số nguyên \(a_1,a_2,…a_n\) \((-10^9≤a_i≤10^9 )\)

Output

• Ghi ra một số nguyên duy nhất là tổng sức mạnh lớn nhất có thể mua được.

Scoring

Example

6
1 2 1 2 -2 5

6