LQDOJ Contest #10 - Sinh Nhật LQDOJ (Bảng C)

Vào thứ hai hàng tuần, trường THPT chuyên Lê Quý Đôn Đà Nẵng tổ chức lễ chào cờ, lớp của Flower_On_Stone Có \(N\) học sinh xếp thành một hàng dọc. Học sinh thứ \(i\) cao \(a_i\) cm.

Để một hàng dọc nhìn trở nên cân đối và đẹp hơn, Flower_On_Stone sẽ cho một vài học trò đứng lên các chiếc gạch sao cho người ở trước mặt mình sẽ không thấp hơn mình. Biết rằng mỗi chiếc gạch có chiều cao tùy ý Flower_On_Stone (chiều cao là một số nguyên và nó không âm).

Yêu cầu: Bạn hãy tính tổng chiếc gạch ít nhất có thể mà thỏa mãn điều kiện Flower_On_Stone đề ra.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \le N \le 10^6)\).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((1 \le a_i \le 10^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(N \le 5000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
2 1 4 3 5

2

Vào ngày sinh nhật của LQDOJ, shiba - một thành viên của Team Shiba quyết định tặng kẹo cho các bạn trẻ trong trường. Có \(N\) đứa trẻ muốn được nhận kẹo và shiba có một bịch kẹo gồm \(M\) vị khác nhau. Có một điều khiến shiba phải băn khoăn rằng tất cả đứa trẻ muốn tất cả viên kẹo mà mình có đều phải có cùng một vị. shiba cũng biết rằng các bạn trẻ sẽ ghen tị nếu có một bạn được quá nhiều kẹo. Để giải quyết các điều này một cách êm đềm nhất, shiba quyết định chia kẹo sao cho mức độ ghen tị sẽ là nhỏ nhất có thể, biết rằng mức độ ghen tị là số kẹo nhiều nhất mà một bạn trẻ có được.

Ví dụ bịch kẹo của shiba có \(7\) viên kẹo vị \(X\) và \(4\) viên kẹo vị \(Y\) thì mà cần chia cho \(5\) đứa trẻ thì shiba có thể chia như sau: \(XX\),\(XX\),\(YY\),\(YY\),\(YYY\). Mức độ ghen tị lúc này là \(3\), là mức độ ghen tị nhỏ nhất có thể.

Tuy nhiên thực hiện việc chia kẹo là quá khó với shiba. Anh ấy nhờ các bạn lập trình tài năng của LQDOJ giúp shiba tìm cách chia sao cho mức độ ghen tị là nhỏ nhất có thể.

Yêu cầu: Bạn hãy giúp shiba tính mức độ ghen tị nhỏ nhất có thể. Biết rằng trường hợp có đứa trẻ không nhận được một viên kẹo nào là có thể xảy ra.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(M\) \((1 \le N \le 10^9,1 \le M \le 3 \times 10^5, M \le N)\).
• \(M\) dòng tiếp theo mỗi dòng chứa một số nguyên dương là số kẹo của từng vị mà shiba có. Số kẹo của từng vị nằm trong đoạn \([1;10^9]\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 25\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
4
7

3

Nhà ông \(T\) có nuôi \(n\) con mèo, con mèo thứ \(i\) hiện tại đang ở vị trí \(x_i\), vì có dự báo sắp có bão đổ bộ, nên ông tìm cách đưa các con mèo vào \(1\) nơi an toàn. May mắn thay, nhà ông có \(m\) lồng cho mèo, lồng thứ \(i\) có sức chứa \(b_i\) con mèo và được đặt tại vị trí \(a_i\). Ông muốn nhốt các con mèo của mình vào các lồng sao cho số lượng mèo ở \(1\) lồng bất kì không vượt quá sức chứa của lồng đấy đồng thời tổng độ mệt mỏi của \(n\) con mèo là ít nhất. (Độ mệt mỏi của \(1\) con mèo khi di chuyển từ vị trí \(x\) sang \(y\) là \(|x - y|\)). Vì không giỏi tính toán, nên bạn hãy tính độ mệt mỏi nhỏ nhất giúp ông \(T\) nhé.
NOTE : Các con mèo khác nhau sẽ ở vị trí khác nhau, các lồng khác nhau sẽ ở vị trí khác nhau

Input

• Dòng đầu tiên ghi \(2\) số \(n\) và \(m\) \((1 \le n, m \le 5*10^3)\) lần lượt là số mèo và số lồng;
• Dòng tiếp theo gồm \(n\) số nguyên phân biệt mô tả mảng \(x\) \((1 \le x_i \le 10^9)\) là vị trí của từng con mèo.
• \(m\) dòng tiếp theo, dòng thứ \(i\) gồm \(2\) số nguyên \(a_i\) và \(b_i\) lần lượt là vị trí và sức chứa của lồng thứ \(i\) (\(1 \le a_i \le 10^9\), \(0 \le b_i \le n\)).

Output

• Gồm \(1\) số nguyên tổng độ mệt mỏi bé nhất của \(n\) con mèo (Nếu không có cách chia thỏa mãn thì in ra \(-1\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm):\(0 \le b_i \le 1\) (với mọi \(i\) từ \(1\) đến \(m\)).
• Subtask \(2\) (\(70\%\) số điểm): Không có rằng buộc gì thêm.

3 5
1 4 7
3 1
5 1 
2 2
7 3
9 3

2

shiba là một anh chàng rất thích vẽ tranh. Anh ấy sở hữu một hộp màu chứa \(m\) màu khác nhau._minhduc biết bạn thân shiba của mình rất thích vẽ nên đã tặng cho một cuốn sách có \(n\) trang, mỗi trang được đánh số từ \(1\) đến \(n\).

Mỗi trang shiba sẽ vẽ một màu duy nhất trong \(m\) màu có trong hộp bút. shiba quy định bức tranh trang thứ \(a_i\) phải tô khác màu so với bức tranh trang thứ \(i\). Có một trường hợp ngoại lệ đặc biệt là \(a_i = i\). Nếu \(a_i = i\) thì shiba có thể tô màu bất kì miễn là màu đó có trong hộp màu.

Yêu cầu: shiba muốn biết rằng mình có mấy cách khác nhau để tô hết cuốn sách do _minhduc tặng. Bạn hãy giúp shiba đếm số cách mà anh ấy có thể tô.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(n\) và \(m\) \((1 \le n,m \le 10^6)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((1 \le a_i \le n)\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Example

3 4
2 1 2

36

Tiếp nối câu chuyện của đá thủ _minhduc ở phần trước LQDOJ Contest #7 - Bài 2 - Bản Nhạc Của Đá, lần này:
_minhduc có \(n\) tảng đá, tảng đá thứ \(i\) có trọng lượng là \(w_i\), khi nhảy lên trên chúng sẽ phát ra một loại âm thanh, để thuận tiện thì ta đánh số chúng trùng với trọng lượng của tảng đá, gọi là chất âm. Các tảng đá có thể khác nhau về trọng lượng cũng như chất âm, nhưng trọng bộ sưu tầm có rất nhiều đá của _minhduc vẫn có thể tồn tại hai hoặc nhiều tảng đá cùng trọng lượng và chất âm. _minhduc ban đầu xếp chúng thành một con đường thẳng, từ tảng đá thứ \(1\) cho tới tảng đá thứ \(n\). Khi nhảy từ tảng đá đầu tiên tới tảng đá cuối cùng, ta nhận được một "bản nhạc" khá vui tai. Sau đấy cậu ấy đã gọi điện cho bạn gái cũ của shiba để mời cô ấy đến thử đoạn đường này và ngắm nhìn khung cảnh tuyệt đẹp kia.

Tuy nhiên, ngay trước thời điểm cô ấy đến, _minhduc bỗng muốn thay đổi "bản nhạc" kia. Cậu ấy có thể làm thao tác sau vô số lần, đó là chọn hai tảng đá liền kề có chênh lệch trọng lượng không quá \(k\) và đổi chỗ chúng. Sau khi đổi chỗ, cậu ấy sẽ lại thử nhảy từ tảng đá thứ \(1\) tới tảng đá thứ \(n\) và lại thu được một "bản nhạc".

Cậu ấy tự hỏi, nếu cứ thực hiện các thao tác trên, thì "bản nhạc" có thứ tự từ điển nhỏ nhất là bản nhạc nào.
Bản nhạc \(A\) được xem là nhỏ hơn \(B\) nếu ở vị trí \(i\) đầu tiên mà \(A_i\) khác \(B_i\), ta có \(A_i < B_i\)

Yêu cầu: In ra bản nhạc có thứ tự từ điển nhỏ nhất có thể thu được.

Input

• Dòng đầu tiên chứa hai số nguyên dương lần lượt là \(N\) và \(K\) – lần lượt là số tảng đá và độ chênh lệch tối đa để đổi chỗ hai tảng đá liền kề _minhduc \((1 \le N \le 10^5, 1\le K \le 10^9)\).

• Dòng thứ \(2\) chứa \(N\) số nguyên dương \(w_1,w_2,...,w_N\) \((1 \le w_i \le 10^9)\).

Output

• In ra "bản nhạc" có thự từ điển nhỏ nhất.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N \le 7\).

• Subtask \(2\) (\(30\%\) số điểm): Có \(N \le 1000\).

• Subtask \(3\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 4
9 4 5 6 7

5
6
7
9
4

shiba và chú chó _minhduc của mình chơi trò trốn tìm với nhau, trong đó shiba là người đi tìm và _minhduc sẽ đi trốn. Trong ngôi nhà của shiba có \(N\) hộp khác nhau đứng liền kề nhau và được đánh số từ \(1\) đến \(N\). _minhduc sẽ trốn vào một hộp bất kì trong \(N\) hộp đó. Sau khi trốn xong shiba bắt đầu đi tìm, mỗi giây shiba sẽ thực hiện thao tác tìm chú chó của mình như sau:

• Đầu tiên shiba chọn một hộp bất kì và kiểm tra nó (ta sẽ gọi hộp đó là hộp đã kiểm tra). Nếu shiba thấy chú chó _minhduc của mình ở đó thì trò chơi kết thúc, nếu chưa tìm ra thì shiba sẽ đặt lại hộp vào chỗ cũ.

• Sau đó, _minhduc sẽ chọn một trong hai lựa chọn như sau: nằm im ở trong hộp mình đang đứng, hoặc nhảy sang hộp bên cạnh (hộp cạnh bên trái hoặc hộp cạnh bên phải đều được). Lưu ý rằng _minhduc có thể nhảy vào hộp đã kiểm tra nếu đó là hộp bên cạnh chú chó ấy đang đứng (giả sử rằng thời gian nhảy từ hộp này sang hộp khác là không đáng kể, có thể nói là \(0\) giây).

Các lựa chọn của _minhduc tùy thuộc vào tình trạng của nó lúc đó. Cụ thể _minhduc có hai tâm trạng như sau:

• Nếu _minhduc đang ở tình trạng sợ hãi thì nó sẽ nhảy ra xa hộp đã kiểm tra. Nếu nó đang ở hộp số \(1\) hoặc ô số \(N\) thì nó sẽ đứng im trong hộp đấy.

• Nếu _minhduc đang ở tình trạng tò mò thì nó sẽ nhảy đến gần hộp đã kiểm tra (lưu ý rằng _minhduc luôn có thể tiến lại gần hơn).

Lưu ý rằng chú chó _minhduc chỉ hành động dựa trên hộp đã kiểm tra gần nhất, không quan tâm đến hộp đã kiểm tra trước đó.

Vì _minhduc là một con chó cưng của shiba nên anh ấy hiểu rất rõ các tâm trạng của _minhduc. shiba biết rằng tình trạng của _minhduc luôn xen kẽ giữa đúng \(X\) giây sợ hãi và \(Y\) giây tò mò. Ví dụ với \(X = 1\) và \(Y = 2\) thì tâm trạng của _minhduc lần lượt sẽ là (sợ hãi, tò mò, tò mò, sợ hãi, tò mò, tò mò, sợ hãi,...).

shiba cảm thấy việc tìm chú chó của mình quá khó khăn nên anh ấy quyết định nhờ các bạn tài năng của LQDOJ tính toán một chuỗi các hộp cần kiểm tra sao cho chú chó _minhduc dù cho lúc đầu có trốn ở đâu thì shiba sẽ luôn tìm ra chú chó ấy.

Yêu cầu: Bạn hãy giúp shiba giải quyết vấn đề trên.

Input

• Chứa ba số nguyên lần lượt là \(N,X,Y\) \((2 \le N \le 10^4; 0 \le X,Y \le 50)\).

Output

• Dòng đầu tiên in ra số giây \(M\) shiba cần để tìm ra chú chó _minhduc.

• Dòng tiếp theo in ra \(M\) số nguyên nằm trong đoạn \([1;N]\) là liệt kê các hộp được kiểm tra vào mỗi giây (trình tự này được phép lặp lại). Mỗi số được liệt kê cách nhau một khoảng trắng.

Scoring

Gọi \(M\) là số giây trong trình tự tìm hộp của bạn. Nếu bạn cố kiểm tra một hộp không hợp lệ (tức là hộp bạn kiểm tra nằm ngoài đoạn \([1;N]\)) hoặc trình tự tìm hộp của bạn không phải lúc nào cũng có thể tìm ra chú chó _minhduc thì bạn sẽ nhận được \(0\) điểm với chú thích Wrong Answer. Với mỗi test có \(P\) điểm thì bạn sẽ nhận được \(k \times P\) điểm với \(k\) là:

• \(k = 0\) nếu \(M > 2 \times N\).

• \(k = 1\) nếu \(M \le T\).

• Các trường hợp còn lại \(k = \frac{1}{2} \times (\frac{T}{M})^2\).

• Ta có \(T = \frac{N\ \times(X+Y)}{X+2max(X,Y)} + 3max(X,Y)\).

Subtask

• Subtask \(1\) (\(8\%\) số điểm): Có \(X = 0\) và \(Y = 1\).
• Subtask \(2\) (\(12\%\) số điểm): Có \(X = 1\) và \(Y = 0\).
• Subtask \(3\) (\(8\%\) số điểm): Có \(X = 1\) và \(Y = 1\).
• Subtask \(4\) (\(72\%\) số điểm): Không có ràng buộc gì thêm.

Example

10 2 1

6
1 3 10 6 8 10