Hàng cây

admin

Bình và An là đôi bạn thân. Hàng ngày, hai bạn cùng nhau đi bộ tới trường. Trên con đường mà hai bạn đi có một hàng cây gồm \(n\) cây, các cây được đánh thứ tự từ 1 đến \(n\). Bình và An rất yêu thích hàng cây này, hai bạn đã tìm hiểu và biết được độ cao của từng cây, cây thứ \(k (k=1,2,…,n)\) có độ cao là \(h_k\). Thật đặc biệt, các cây có độ cao đôi một khác nhau. Một hôm, An đố Bình bài toán sau: Tìm hai số \(i,j\) là chỉ số của hai cây thỏa mãn điều kiện: \(1 ≤ i<j ≤ n\) và \(h_i<h_j\) để giá trị (\(j-i\)) đạt giá trị lớn nhất. Bình đề nghị: “Chúng ta hãy cùng lập trình giải quyết bài toán này.”

Yêu cầu: Cho \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n\) là độ cao của \(n\) cây, hãy tìm hai số \(i,j\) là chỉ số của hai cây mà \(1 ≤ i<j ≤ n\) và \(h_i<h_j\) để giá trị (\(j-i\)) đạt giá trị lớn nhất.

Dữ liệu

  • Dòng đầu chưa một số nguyên dương \(n\);
  • Dòng thứ hai gồm \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n\ (h_i≤10^6)\);

Kết quả

  • Một dòng chứa một số là giá trị (\(j-i\)) lớn nhất tìm được. Nếu không tồn tại hai chỉ số \(i,j\) thỏa mãn thì ghi \(-1\).

Sample Input

4
4 2 1 3

Sample Output

2

Sample Input

3
4 2 1

Sample Output

-1

Giới hạn:

  • Có 50% số lượng test thỏa mãn điều kiện: \(n≤10^3\);
  • Có 50% số lượng test còn lại thỏa mãn điều kiện: \(n≤10^5\);

Nguồn: 2019 TN

Xóa dấu khoảng trống

admin, daicadihoc

Cho một chuỗi kí tự gồm \(n\) kí tự bao gồm các chữ cái và khoảng trống (\(n \leq 100\)). Chuỗi kí tự này có những dấu khoảng trống thừa, hãy xóa các dấu khoảng trống đó khỏi chuỗi sao cho giữa các từ chỉ có duy nhất 1 dấu khoảng trống.

Input:

  • Gồm 1 dòng duy nhất chứa chuỗi kí tự.

Output:

  • Chuỗi kí tự sau khi xóa dấu khoảng trống thừa.

Ví dụ

Input:

Facebook      google    YOUTUBE    amazon

Output:

Facebook google YOUTUBE amazon

Tần suất (OLP 11 - 2018)

Small

Công ty viễn thông AZPHONE đang đối mặt với tình trạng nghẽn mạng 4G tại một số thời điểm trong năm. Hiện tại công ty đã ghi nhận được số lượng thuê bao truy cập trong từng giây của \(N\) giây liên tiếp, là dãy số nguyên không âm \(a_1, a_2, …, a_N\) (\(a_i\) là số lượng thuê bao tại giây \(i, 1 ≤ i ≤ N\)). Công ty muốn biết tần suất truy cập \(T(i, L)\) của \(L\) giây liên tiếp kể từ giây \(i\), trong đó \(T(i, L) = (a_i + a_{i+1} + … + a_{i+L-1})/L (1 ≤ i < N - L)\) với điều kiện \(L\) phải không nhỏ hơn một hằng số \(K\) cho trước \((1 ≤ K ≤ L ≤ N)\).

Yêu cầu: Cho biết \(K\) và dãy a_1, a_2, …, a_N. Hãy giúp công ty xác định giá trị lớn nhất của \(T(i, L)\).

Dữ liệu

  • Dòng đầu tiên là hai số nguyên \(N\) và \(K\) (\(1 ≤ N ≤ 300000\))
  • Dòng thứ hai gồm dãy số nguyên không âm \(a_1, a_2, …, a_N (0 ≤ a_i ≤ 10^6)\).

Các số trên cùng một dòng cách nhau một ký tự trống (dấu cách).

Kết quả

  • Ghi ra duy nhất một dòng là giá trị lớn nhất của \(T(i, L)\), giá trị bình quân gồm 6 chữ số sau dấu chấm thập phân.

input

4 1
1 0 4 3

Output

4.000000

input

5 2
2 4 3 4 1

Output

3.666667

Ràng buộc: 60% số test ứng với 60% số điểm của bài có \(N ≤ 5000\)


Nguồn: Olympic 30/4 năm 2018.

Trồng cây

Small

Trường THPT Chuyên Khoa học Tự Nhiên – Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội (tên gọi thân thương: Chuyên Tổng Hợp, Hải Sản Giun Sán – HSGS) là trường chuyên lâu đời và có bảng thành tích ấn tượng nhất Việt Nam. Xuất thân từ các khối chuyên trực thuộc Đại học Tổng Hợp Hà Nội, trải qua hơn 50 năm hình thành và phát triển, trường đều đặn đóng góp cho Việt Nam nhiều tấm huy chương trong các kỳ thi Olympic quốc tế (IMO, IOI, IPhO, IChO và IBO). Nhiều học sinh sau khi ra trường đã trở thành những giáo sư, tiến sỹ khoa học mang tầm cỡ quốc tế.

Chuyên Tổng Hợp không chỉ nổi tiếng với những thánh nhân đại tài, mà còn nổi tiếng với vườn sưa cổ kính. Suốt bao năm nay, những cây sưa vẫn đứng vững giữa sân trường, đến tháng 3 hàng năm vẫn trổ khóm hoa trắng xoá, báo hiệu cuộc chia ly sắp đến và vẫy gọi học sinh cũ về ghé lại mái trường xưa. Hình ảnh sưa trắng trong nền lá xanh biếc đã ghi vào ký ức bao học trò. Nhưng bạn có biết không, cây xanh không chỉ phủ bóng góc sân, mà còn len lỏi vào trong những phòng học đội tuyển.

Nếu có dịp ghé thăm phòng học đội tuyển Tin, bạn sẽ được chiêm ngưỡng những cây dây leo treo quanh tường, những cây hoa xinh xinh trên bệ cửa, và những chậu xương rồng âm thầm sinh sôi. Chuyện kể rằng, để làm tươi mát tâm hồn khô khan của những coder chỉ biết code và code, thầy giáo dẫn đội đã mang về khu vườn mini này. Nhưng khu vườn còn là biểu tượng linh thiêng, báo hiệu những thành quá ấn tượng mà thầy trò đội tuyển sẽ gặt hái. Vào một ngày đầu năm 2014, thầy giáo quan sát thấy cây xương rồng nở 8 bông hoa. Và ngay hôm sau, tuyển tin Tổng Hợp có 8 bạn được vào vòng 2.

Để biến trường chuyên từ vườn ươm tài năng thành vườn ươm cây xanh, nhân ngày trường tròn 55 tuổi, thầy hiệu trưởng quyết định mang các loại cây về trồng.

Theo kế hoạch ban đầu, thầy định trồng \(𝑛\) loại cây, với số cây mỗi loại được trồng lần lượt là \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\). Mỗi loại có ít nhất hai cây được đặt. Nhận ra số cây đã đặt quá lớn và không đủ diện tích để trồng tập trung, thầy hiệu trưởng chia số cây ra làm nhiều khu vườn. Tuy nhiên, kế hoạch này vấp phải một khó khăn: Thầy muốn các khu vườn giống nhau, nhưng có thể không có cách chọn số khu vườn sao cho các loại cây đều được chia đều vào mỗi khu vườn.

Vì vậy, thầy quyết định thay đổi đơn hàng ban đầu. Với mỗi loại cây, công ty cây xanh cho thầy ba sự lựa chọn:

  • Mua thêm một cây thuộc loại này
  • Bỏ bớt một cây thuộc loại này
  • Huỷ toàn bộ số cây đã đặt thuộc loại này, nghĩa là không trồng loại này nữa.

Nếu chọn lựa chọn thứ ba, thầy giáo phải trả cho công ty \(𝑥\) đồng. Nếu chọn một trong hai lựa chọn đầu tiên, thầy giáo phải trả \(𝑦\) đồng. Ngoài ra, để giữ tính thẩm mỹ cho khu vườn, công ty đưa ra thêm ràng buộc: Nếu thầy giáo huỷ toàn bộ số cây loại \(𝑙\) và loại \(𝑟\) (\(1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛\)), toàn bộ số cây thuộc các loại \(𝑖\) với \(𝑙 ≤ 𝑖 ≤ 𝑟\) cũng phải huỷ bỏ. Lưu ý, nếu không huỷ bỏ một loại cây, số cây thuộc loại đó chỉ có thể thay đổi không quá 1. Dĩ nhiên, thầy giáo có thể chọn không thay đổi số lượng cây đã đặt, và không phải trả thêm phí.

Thầy hiệu trưởng muốn sửa lại đơn hàng theo quy định của công ty, sao cho có ít nhất 1 loại cây được giữ lại, và tồn tại cách chọn số khu vườn (nhiều hơn 1) sao cho số cây của mỗi loại đều có thể chia đều vào các khu vườn. Các bạn hãy giúp thầy tính chi phí nhỏ nhất nhé.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên \(𝑇\) (\(1 ≤ 𝑇 ≤ 4\)) – số thứ tự của subtask chứa test này.
  • Dòng thứ hai chứa ba số nguyên \(n, x, y\) (\(1\le n \le 5 \times 10^5, 1\le x,y \le 10^9\)), – số loại cây dự định được trồng, chi phí để huỷ bỏ đơn đặt hàng của một loại cây và chi phí để mua thêm hoặc bớt đi một cây thuộc một loại nào đó.
  • Dòng thứ ba chứa \(𝑛\) số nguyên \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) (\(2 ≤ 𝑎𝑖 ≤ 10^{12}\)) – số cây được đặt hàng ở mỗi loại, theo đơn hàng ban đầu.

Kết quả Một số nguyên duy nhất là số tiền nhỏ nhất thầy hiệu trưởng cần bỏ ra, hoặc −1 nếu không có cách nào để thầy hiệu trưởng thay đổi đơn hàng như ý muốn.

Sample Input 1

1 
3 1 1 
3 5 4

Sample Output 1

2

Sample Input 2

2 
5 1000000000 1 
18 54 30 42 24

Sample Output 2

0

Sample Input 3

3 
4 1 5 
7 45 90 11

Sample Output 3

3

Giải thích:

  • Trong ví dụ đầu tiên, thầy giáo có thể tăng thêm một cây ở loại 1 và huỷ bỏ toàn bộ số cây ở loại 2. Khi đó thầy có 4 cây mỗi loại 1 và 3, chia đều được vào 4 khu vườn.
  • Trong ví dụ thứ hai, số cây hiện tại đã đủ chia vào 6 khu vườn, nên thầy không cần thay đổi gì.
  • Trong ví dụ thứ ba, phương án tối ưu là huỷ bỏ các cây thuộc loại 2, 3 và 4 và giữ nguyên số cây loại 1. Lưu ý rằng thầy giáo không thể thay đổi đơn hàng sao cho số cây chia đều vào 9 khu vườn; bởi số cây loại 1 và 4 không thể thay đổi quá 1; và nếu loại bỏ cả hai loại cây 1 và 4, tất cả các loại 2 và 3 cũng bị huỷ bỏ theo. Nhưng thầy cần giữ lại ít nhất một loại cây.

Giới hạn

  • Subtask 1 (11 điểm): \(𝑛 ≤ 10\)
  • Subtask 2 (13 điểm): \(𝑥 = 109\) và \(𝑦 = 1\)
  • Subtask 3 (20 điểm): \(𝑛 ≤ 2000\) và \(𝑎_𝑖 ≤ 50000\)
  • Subtask 4 (26 điểm): Không có ràng buộc gì thêm.

Nguồn: 2020 PreVOI Online

SUMDIV

hhoangcpascal

Giáo sư Wu Zi Mu đã tiếp tục ra bài tập cho học sinh lớp \(1\) như sau:

"Định nghĩa \(S(N)\) là tổng tất cả các ước nguyên dương của \(N\). Ví dụ: \(S(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28\)

Cho \(Q\) truy vấn, mỗi truy vấn gồm số nguyên dương \(N\). Tính \(S({N!}^3)\) mod \(1200000090\)."

Học sinh nghĩ mãi không ra. Các bạn hãy giúp học sinh trả lời \(Q\) truy vấn trên.

Dữ liệu vào: Gồm \(Q + 1\) dòng:

  • Dòng đầu tiên gồm số \(Q\).
  • \(Q\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(N\).

Kết quả: Gồm \(Q\) dòng là kết quả của \(Q\) truy vấn theo thứ tự từ trên xuống dưới, in ra từng dòng.

Ví dụ:

Input:

2
4 
3

Output:

40920
600

Giới hạn:

  • \(10\)% số test đầu tiên có \(N \leq 5, Q \leq 3\)
  • \(30\)% số test tiếp theo có \(N \leq 10^4, Q \leq 10\)
  • \(30\)% số test tiếp theo có \(N \leq 10^6, Q \leq 10\)
  • \(30\)% số test còn lại có \(N \leq 4.10^7, Q \leq 4\), tổng các số \(N\) trong \(Q\) truy vấn không quá \(4.10^7\).

Số "tương lai" 2

kid2201, phanhuykhang, dang7rickroll

Định nghĩa: Số "tương lai" là số có các ước (không kể \(1\) và chính nó) là các số nguyên tố.

Ví dụ: \(10\) có \(2\) ước thực sự là \(2\) và \(5\) là các số nguyên tố nên \(10\) là số "tương lai".

Yêu cầu: Cho dãy số nguyên \(a_1,a_2,...a_n\) \((1 <= n <= 10^6; 1 <= a_i <= 2 * 10^7\)). Hãy cho biết trong dãy trên có bao nhiêu số tương lai.

Dữ liệu:

  • Dòng thứ nhất gồm số nguyên \(n\).
  • Dòng thứ hai gồm các số \(a_1,a_2,...,a_n\).

Kết quả:

  • Số lượng số tương lai thỏa đề.

Sample input

9
9 7 10 6 17 4 19 21 13

Sample output

5

Nguồn: LQDCODER

Được đề xuất tăng giới hạn bởi phanhuykhang

[Python_Training] Giá trị nhỏ nhất đơn giản

jumptozero
  • Cho \(3\) số nguyên dương \(a,b,c\). Đặt \(S=min\left\{a+b,b+c,c+a\right\}\), xuất \(S\) ra màn hình.

Input:

  • Dòng thứ nhất chứa \(3\) số nguyên dương \(a,b,c(1\le a,b,c\le 10000)\)

Output:

  • In ra \(S\) cần tìm.

Ví dụ:

Input:

2 5 6

Output:

7

Nguồn: Atcoder

Chênh lệch độ dài

Cho 2 chuỗi kí tự \(a\) và \(b\). Hãy in ra độ chênh lệnh độ dài của 2 chuỗi.

Input:

  • Dòng thứ nhất là chuỗi kí tự \(a\).
  • Dòng thứ hai là chuỗi kí tự \(b\).

Output:

  • Gồm một dòng duy nhất là kết quả cần tìm.

Lưu ý: Chuỗi nhập vào có thế có dấu khoảng trống (dùng getline).

Ví dụ

Input:

zzzzzz aa
ssssss aaaaaa

Output:

 4

Phép toán

Small

Vì nghỉ hè quá lâu nên bạn Nam học sinh lớp 3 đã quên hết các phép toán : cộng, trừ, nhân, chia. Các em hãy giúp Nam ôn tập lại các phép toán đó nhé!

Input

  • Dòng 1 chứa số nguyên dương \(a\)
  • Dòng 2 chứa số nguyên dương \(b\)

Output

  • In ra giá trị của các phép toán cộng \((+)\), trừ \((-)\), nhân \((*)\), chia lấy nguyên \((//)\).
  • Mỗi giá trị trên một dòng.

sample Input

10
2

Sample Output

12
8
20
5

Cánh diều - TONG3SO - Tổng ba số

DKingQA, Flower_On_Stone, habelle

Nhập vào 3 số nguyên. Tính và in ra tổng, tổng bình phương ba số.

Input:

Gồm ba dòng mỗi dòng ghi một số nguyên có giá trị tuyệt đối không quá \(10^6\).

Output:

Dòng đầu ghi tổng ba số đã cho.

Dòng thứ hai ghi tổng bình phương ba số đã cho (theo định dạng như ví dụ mẫu).

Ví dụ:

Sample Input 1

2  
4  
7

Sample Output 1

Tong ba so: 13 
Tong binh phuong ba so: 69

Sample Input 2

-1  
5  
5

Sample Output 2

Tong ba so: 9 
Tong binh phuong ba so: 51

Bài toán đồng xu 1

jumptozero

Cho \(N\) là một số nguyên dương lẻ.

Có \(N\) đồng xu, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), khi đồng xu \(i\) được gieo, xác suất nó xảy ra mặt ngửa là \(p_i\) và xác suất nó xảy ra mặt úp là \(1-p_i\).

\(Kaninho\) gieo \(N\) đồng xu cùng một lúc. Tính xác suất để ta thu được số lượng đồng xu ngửa lớn hơn số lượng đồng xu úp.

Input:

  • Dòng thứ nhất chứa số nguyên dương lẻ \(N(1\le N\le 2999)\)

  • Dòng thứ hai chứa \(n\) số thực có \(2\) chữ số ở hàng thập phân \(p_i(0<p_i<1)\)

Output:

  • In ra đáp án cần tìm. (Gọi \(x\) là đáp án của bạn, \(y\) là đáp án của bài toán, thì \(x\) được chấp nhận là đúng nếu \(|x-y|<10^{-9}\))

Ví dụ:

Input:

3
0.30 0.60 0.80

Output:

0.612

Giải thích:

Xác suất của mỗi trường hợp có số lượng đồng xu ngửa lớn hơn số lượng đồng xu úp là :

  • \(P(ngua,ngua,ngua) = 0.3*0.6*0.8=0.144\)

  • \(P(up,ngua,ngua) = 0.7*0.6*0.8=0.336\)

  • \(P(ngua,up,ngua) = 0.3*0.4*0.8=0.096\)

  • \(P(ngua,ngua,up) = 0.3*0.6*0.2=0.036\)

Như vậy, xác suất có số lượng mặt ngửa lớn hơn số lượng đồng xu úp là: \(0.144+0.336+0.096+0.036 = 0.612\)

SGAME8

vinhntndu

Trong một cây nhị phân có độ dài vô hạn:

  • Gốc ban đầu có giá trị là 1
  • Mỗi node sẽ có hai gốc con, 1 gốc bên trái và 1 gốc bên phải. Nếu node được gán nhãn X, thì hai gốc con sẽ có nhãn là 2X (bên trái) và 2X+1 (bên phải).
  • Đi từ đỉnh xuống, ta có thể đi qua gốc con bên trái, hoặc gốc con bên phải, hoặc dừng lại ở vị trí đang đứng.

Cho bài toán sau: Đi từ gốc xuống:

  • Nếu là L thì sẽ đi qua gốc con bên trái.
  • Nếu là R thì sẽ đi qua gốc con bên phải.
  • Nếu là P thì sẽ dừng lại.
  • * là ẩn với 3 cách đi: trái, phải hoặc dừng lại.

Ví dụ: L* thì ta có thể đi: LR, LP hoặc LL. Bạn hãy tính tổng các giá trị nhãn của các nút là đích đến mà có thể đi tới được.

INPUT: Một dòng duy nhất là một chuỗi biểu diễn đường đi. Độ dài chuỗi không vượt quá 10000

OUTPUT: kết quả bài toán.

Ví dụ


INPUT

**

OUTPUT

33

Cánh diều - COUNT100 - Đếm số phần tử nhỏ hơn 100

anhkha2003, Flower_On_Stone

Cho \(N\) số nguyên. Hãy đếm xem trong dãy có bao nhiêu phần tử có giá trị nhỏ hơn hoặc bằng \(100\) ?

Input:

  • Dòng đầu ghi số nguyên \(N\) \((1 ≤ N ≤ 10^6)\)

  • Dòng thứ hai ghi \(N\) số nguyên cách nhau bởi dấu cách \((|a_{i}| ≤ 10^6)\)

Output:

  • Ghi một số nguyên là số lượng phần tử có giá trị nhỏ hơn hoặc bằng \(100\) trong dãy.

Ví dụ:

Input:

5
19 120 999 0 -120

Output:

3

Quản lý vùng BALLAS

hhoangcpascal

Sau khi thanh toán hết băng nhóm BALLAS, CJ đã tịch thu những nơi do băng BALLAS làm chủ. Là một trong những người đứng đầu nhóm GROVE STREET FAMILIES, nên CJ đã ra lệnh cho một số lính thăm dò về vùng đất bị thu hồi này. Sau khi thăm dò, thì CJ biết trong vùng có \(N\) ngôi nhà, đánh số từ \(1\) tới \(N\), và có \(M\) tuyến đường giao thông hai chiều nối trực tiếp hai ngôi nhà với nhau. Lúc này CJ ra lệnh cho một số lính quản lý vùng đã được thu hồi với các điều kiện sau:

  • Mỗi ngôi nhà chỉ chịu quản lý của một lính của CJ.
  • Tập hợp các ngôi nhà có thể kết nối được với nhau (bất kỳ hai ngôi nhà nào cũng có thể kết nối với nhau) thì cũng chỉ chịu quản lý bởi một lính của CJ.
  • Định nghĩa ngôi nhà u với ngôi nhà v kết nối được với nhau là tồn tại một đường đi giữa hai ngôi nhà \(u\) và \(v\), tức là tồn tại dãy các ngôi nhà \(P = 〈u = p_0, p_1, …, p_k = v〉\) sao cho \(\forall i: 1 < i ≤ k\) thì tồn tại tuyến đường trực tiếp giữa hai ngôi nhà \(p_{i-1}\) và \(p_i\) trong khu vực.
  • Số lính để quản lý là ít nhất.

Yêu cầu: Hãy tìm số lính quản lý thoả mãn các điều kiện của CJ, và chỉ ra rõ ra những ngôi nhà mà từng lính quản lý. Nếu có nhiều cách quản lý, chỉ ra một cách bất kì.

Dữ liệu vào: Gồm \(M + 1\) dòng:

  • Dòng \(1\) chứa 2 số nguyên dương \(N\), \(M\);
  • \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u\), \(v\) thể hiện có tuyến đường hai chiều nối trực tiếp từ ngôi nhà \(u\) tới ngôi nhà \(v\) trong vùng.

Kết quả: Gọi \(K\) là số đàn em quản lý thoả mãn các điều kiện của CJ. Ghi ra \(K+1\) dòng:

  • Dòng \(1\) ghi ra số nguyên dương \(K\).
  • \(K\) dòng tiếp theo, dòng i ghi ra số đầu tiên là số \(X\) - số ngôi nhà do lính \(i\) quản lý, \(X\) số tiếp theo là số hiệu ngôi nhà do lính \(i\) quản lý.

Ví dụ

INPUT

12 10
1 4
2 3
3 6
4 5
6 7
8 9
8 10
9 11
11 8
11 12

OUTPUT

3
3 1 4 5 
4 2 3 6 7 
5 8 9 10 11 12

Giới hạn

  • \(30\)% số test đầu tiên có \(N \leq 10^3, M \leq 10^4\)
  • \(70\)% số test còn lại có \(N \leq 10^5, M \leq 10^6\)

Thay thế tổng

cuom1999

Có \(n\) hộp kẹo trên bàn. Hộp thứ \(i\) chứa \(a_i\) viên kẹo. Bạn muốn gộp tất cả viên kẹo lại một hộp. Cách làm như sau:

  • Nếu trên bàn còn ít nhất hai hộp kẹo có kẹo, ta chọn ra hai hộp ít kẹo nhất rồi đổ chung vào một hộp. Nói cách khác, nếu hai hộp kẹo chứa \(x\) và \(y\) viên kẹo, ta gộp chúng lại thành \(1\) hộp chứa \(x + y\) viên kẹo. Thời gian để thực hiện thao tác là \((x + y)\) giây.
  • Thực hiện đến khi nào trên bàn còn đúng một hộp kẹo.

In ra số lượng kẹo trong hộp sau khi thực hiện xong và tổng thời gian cần dùng.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(n \ (1 \leq n \leq 2*10^5)\), số hộp kẹo.
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n \ (1 \leq a_i \leq 10^9)\)

Output

  • In ra hai số nguyên trên một dòng: số đầu tiên là số viên kẹo trong hộp cuối cùng, số thứ hai là tổng thời gian cần sử dụng.
  • Nếu bạn in đúng một trong hai số, bạn sẽ nhận được \(30\%\) số điểm của test đó.

Ví dụ

Input

4
1 2 3 4

Output

10 19

Giải thích

  • Ban đầu, hai hộp kẹo ít nhất là \(1\) và \(2\). Chúng ta gộp lại thành một hộp kẹo có \(3\) viên. Sau đó, có 3 hộp kẹo \([3, 3, 4]\), chọn ra hai hộp ít nhất là \(3\) và \(3\) và gộp thành \(6\). Cuối cùng còn hai hộp \(4\) và \(6\), gộp lại thành \(10\).
  • Tổng thời gian là \((1 + 2) + (3 + 3) + (6 + 4) = 19\).

Giới hạn

  • Có \(20\%\) test có \(n \leq 20\)
  • Có \(30\%\) test có \(n \leq 2000\)
  • Có \(50\%\) test có \(n \leq 2 * 10^5\).

Thuê hội trường

hhoangcpascal

~Giáo sư Wu Zi Mu đi thăm quan một hội trường ở Los Santos. Trong khi đi quanh thì gặp người quản lý. Người này nhờ giáo một bài toán như sau:

  • Có \(N\) người muốn thuê hội trường. Người thứ \(i\) nếu thuê được hội người sẽ bắt đầu từ thời gian \(S_i\) tới thời gian \(F_i\), với chi phí \(F_i - S_i + 1\).
  • Tại mỗi thời điểm hội trường chỉ được thuê bởi một người. Người \(j\) có thể thuê sau người \(i\) nếu \(F_i < S_j\).
  • Người quản lý muốn làm sao để nhiều người thuê nhất có thể để lấy quan hệ. Trong trường hợp cùng số người thuê nhiều nhất thì quản lý muốn thu được nhiều chi phí nhất. Giáo sư Wu Zi Mu vì quên mang theo laptop, với quá nhiều người thuê, nên các bạn hãy giúp giáo sư tìm ra số người thuê nhiều nhất và chi phí nhiều nhất tương ứng.

Dữ liệu vào: Gồm \(N+1\) dòng:

  • Dòng thứ nhất chứa số nguyên dương \(N\).
  • N dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(S_i, F_i\) \((S_i \leq F_i \leq 10^9)\).

Kết quả: In ra hai số nguyên dương là người thuê nhiều nhất và chi phí nhiều nhất tương ứng.

Ràng buộc:

  • \(50\)% số test đầu tiên tương ứng với \(50\)% số điểm có \(N \leq 10^3\).
  • \(50\)% số test tiếp theo tương ứng với \(50\)% số điểm có \(N \leq 10^5\).

Ví dụ:

Input:

3
1 4
3 5
6 8

Output:

2 7

Salary Queries

hhoangcpascal

Một công ty có \(N\) nhân viên với với mức lương nhất định. Nhiệm vụ của bạn là theo dõi mức lương và thực hiện truy vấn.

Dữ liệu vào:

  • Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1\) tới \(N\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) là lương của mỗi người.
  • \(Q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong hai dạng sau:
    • \(!\) \(k\) \(x\): thay đổi lương của người thứ \(k\) thành \(x\).
    • \(?\) \(a\) \(b\): đếm số người có mức lương từ \(a\) tới \(b\).

Kết quả: In ra kết quả cho truy vấn \(?\).

Ràng buộc:

  • Subtask 1 \((30\%)\): \(N, Q \leq 2.10^3\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).
  • Subtask 2 \((30\%)\): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^5\) với \(\forall i, 1 \leq i \leq N\).
  • Subtask 3 \((40\%)\): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).

Ví dụ:

Input:

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3

Output:

3
2

Nguồn: CSES

Running (DHBB 2021 T.Thử)

Small

Vương quốc chuẩn bị tổ chức một cuộc thi chạy việt dã. Mạng lưới đường sá của vương quốc bao gồm \(n - 1\) đường hai chiều kết nối \(n\) tỉnh. Giữa hai tỉnh bất kì đều có thể đi đến được với nhau thông qua những con đường này. Cuộc thi chạy sẽ có điểm xuất phát là tỉnh A (kinh đô) và điểm đích là tỉnh B (cố đô).

Do công tác bảo trì đường sá không được quốc vương chú trọng, các con đường này đã xuống cấp trầm trọng. Nếu chỉ đi bộ thì không có vấn đề gì, tuy nhiên, đây lại là một cuộc thi chạy. Mỗi con đường chỉ có thể chịu được một số lượng người nhất định chạy qua nó mà thôi.

Quốc vương vì muốn nhiều người được tham gia cuộc thi chạy nhất nên quyết định xây thêm một con đường mới (với chất lượng rất tốt, bao nhiêu người chạy qua cũng không hỏng). Tuy nhiên, con đường này không được phép nối trực tiếp đến kinh đô và cũng không được phép nối trực tiếp đến cố đô. Hãy giúp quốc vương tính xem sau khi xây dựng con đường mới, sẽ có tối đa bao nhiêu người có thể tham gia vào cuộc thi chạy?


Input:

  • Dòng đầu tiên chứa ba số nguyên \(n, A\) và \(B (4 ≤ n ≤ 100000; 1 ≤ A, B ≤ n; A ≤ B)\).
  • \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v\) và \(c (1 ≤ u, v ≤ n; u ≤ v; 1 ≤ c ≤ 1000)\) cho biết có một con đường hai chiều nối hai tỉnh \(u\) và \(v\), có tối đa \(c\) người có thể chạy qua con đường này.

Output: In ra số lượng tối đa người có thể tham gia cuộc thi chạy sau khi quốc vương xây thêm một con đườngmới.


Sample Input

4 1 4
1 2 10
1 4 10
3 4 5

Sample Output

15

Nguồn: 2021 Thi thử

RACE

zipdang04, invisible

Kết hợp với IOI, thành phố Pattaya sẽ tổ chức cuộc đua: Olympic quốc tế về đua tốc độ (IOR) 2011.

Là nhà tổ chức, chúng ta phải tìm ra vòng đua tốt nhất cho cuộc thi tốc độ này.

Ở vùng Pattaya − Chonburi, có \(N\) thành phố được nối với nhau bởi mạng gồm N−1 đường cao tốc. Mỗi đường cao tốc đều cho phép đi theo cả hai chiều nối hai thành phố phân biệt và có độ dài đo bởi kilomet là số nguyên. Ngoài ra có đúng một đường đi giữa cặp hai thành phố bất kỳ. Nghĩa là, có đúng một cách đi từ một thành phố này đến một thành phố khác dọc theo dãy các đường cao tốc không qua bất cứ thành phố nào quá một lần.

IOR có qui tắc đặc biệt đòi hỏi vòng đua phải dài đúng \(K\) kilomet, bắt đầu và kết thúc ở hai thành phố phân biệt. Rõ ràng là không có đường cao tốc (và vì thế cũng không có thành phố) nào có thể được sử dụng quá một lần trên vòng đua để ngăn ngừa đụng độ. Để cực tiểu ảnh hưởng đến giao thông, vòng đua phải chứa một số ít nhất đường cao tốc có thể.

Yêu cầu: Bạn hãy cho biết số lượng đường cao tốc nhỏ nhất trên vòng đua hợp qui tắc có độ dài đúng bằng \(K\). Nếu không tìm được vòng đua như vậy, kết quả sẽ là \(-1\).

Input

  • Dòng đầu ghi số \(N, K\).
  • \(N-1\) dòng tiếp theo mỗi dòng ghi 3 số \(u, v, l\) – đường cao tốc nối thành phố \(u\) và \(v\), độ dài \(l (l≤10^6)\).

Output

  • 1 số nguyên duy nhất là kết quả của bài toán.

Scoring

  • \(1≤N≤2×10^5\)
  • \(1≤K≤10^6\)

Example 1:

Input:
4 3
0 1 1
1 2 2
1 3 4
Output:
2

Example 2:

Input:
3 3
0 1 1
1 2 1
Output:
-1

Example 3:

Input:
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
Output:
2

Tập hợp "kì dị"

jumptozero

Cho tập hợp \(S\) gồm \(N\) phần tử. \(S\) được gọi là tập hợp "kì dị" nếu \(S\) chứa tất cả các số từ \(1\) đến \(N\) và các phần tử này được sắp xếp theo thứ tự từ điển từ bé đến lớn.

Gọi \(W(N,K)\) là vị trí của số \(K\) trong tập hợp "kì dị" gồm \(N\) phần tử. (Biết rằng: Các phần tử của tập hợp được đánh số từ \(1\))

Yêu cầu: Cho hai số nguyên dương \(K,M\). Tìm số nguyên dương \(N\) nhỏ nhất sao cho \(W(N,K)=M\), nếu không tồn tại \(N\) , in ra \(0\).

Input:

  • Dòng duy nhất chứa hai số nguyên \(K,M(1\le K,M\le 10^9)\),

Output:

  • In ra đáp án cần tìm

Ví dụ:

Input:

2 4

Output:

11

Giải thích:

  • Xét tập hợp "kì dị" \(S\) gồm \(11\) phần tử. Khi đó \(S=\left\{1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9\right\}\). Khi đó ta có: \(W(11,2)=4\) vì số thứ \(4\) trong tập \(S\) là \(2\).

Subtask:

  • \(20\text{%}\) test có \(1\le K,M\le 100\)

  • \(80\text{%}\) test có \(1\le K,M\le 10^9\)