LQDOJ Contest #2 Tạm biệt năm Nhâm Dần

Mùa đông đã đến. Nguyên mới phát minh ra một thiết bị làm nóng và cậu ấy quyết định đi thử nó ở Bắc Cực. Một trong những cách hữu hiệu nhất đó chính là đi phá băng.

Ban đầu, thiết bị làm nóng của Nguyên có nhiệt độ là \(T\). Có tất cả \(n\) tảng băng, tảng băng thứ \(i\) có nhiệt độ là \(t_{i}\). Thiết bị làm nóng cần có nhiệt độ lớn hơn hoặc bằng giá trị tuyệt đối của \(t_{i}\) để phá băng. Phá một tảng băng thỏa mãn điều kiện cần \(1\) giây. Khi phá được tảng băng đó, thiết bị làm nóng của Nguyên sẽ hấp thu hơi nước phát ra và nhận được thêm một lượng nhiệt độ bằng \(p_{i}\). Ngoài ra, Nguyên cũng có thể cắm điện và thiết bị làm nóng sẽ nhận một giá trị là \(k\) đơn vị nhiệt độ mỗi giây.

Tóm lại, có hai cách để Nguyên gia tăng nhiệt độ cho thiết bị làm nóng trong \(1\) giây:

• Phá một tảng băng (thỏa mãn điều kiện) và nhận \(p_{i}\) đơn vị nhiệt độ.
• Cắm điện và nhận \(k\) đơn vị nhiệt độ.

Yêu cầu: Tính thời gian ngắn nhất để Nguyên phá được hết tất cả \(n\) tảng băng?

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,T,k\) (\(n \le 10^3, T \le 10^9, k \le 10^9\)).
• \(n\) dòng tiếp theo, dòng thứ \(n+1\) chứa hai số nguyên \(t_{i}\) và \(p_{i}\) (\(-10^9 \le t_{i} \le -1, 0 \le p_{i} \le 10^9\)).

Output

• Một số nguyên duy nhất là thời gian ngắn nhất để Nguyên phá được hết \(n\) tảng băng.

Example

1 15 20
-35 1

2

Hôm nay là ngày Nguyên tham gia một gameshow truyền hình có tên là "Nhanh tay - Lẹ mắt". Như tên của chương trình, Nguyên cần phải vừa nhanh, vừa chuẩn để đạt được giải thưởng lớn trong cuộc thi. Trò chơi đầu tiên có tên là Cặp Đôi Hoàn Hảo. Cụ thể, nội dung trò chơi như sau:

Có một dãy số gồm \(n\) số nguyên dương, các số lần lượt là \(a_{1}, a_{2},..., a_{n}\). Hai số có chỉ số khác nhau được gọi là một "Cặp Đôi Hoàn Hảo" khi hai số bằng nhau.

Ngay lập tức, Nguyên thắc mắc có bao nhiêu "Cặp Đôi Hoàn Hảo" để mình lựa chọn. Do cần gấp, không thể nào tính bằng tay được, Nguyên cần đến sự trợ giúp của máy tính. Các bạn hãy giúp Nguyên nhé!

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) (\(n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2},..., a_{n}\) (\(a_{i} \le 10^9\)).

Output

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

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

7
1 1 5 3 5 1 3

5

Thành phố A nổi tiếng với nhiều danh lam thắng cảnh cũng như sự phát triển về công nghệ, để duy trì sự phồn thịnh của thành phố này, các công nhân cần làm việc vô cùng cật lực. Thành phố A hiện tại có vô hạn số công nhân, các công nhân được đánh số từ \(1\) đến \(+\infty\). Công nhân thứ \(i\) có chỉ số xây dựng là \(i\). Hiện tại thành phố cần thực hiện \(q\) công trình, mỗi công trình yêu cầu các công nhân từ \(l\) đến \(r\) hợp lực để xây dựng. Được biết, khi \(n\) công nhân cùng làm chung với nhau thì chỉ số hiệu quả của họ sẽ là tổng phép and chỉ số xây dựng của \(n\) công nhân. Là một người cầu toàn, SHIBA muốn chỉ số hiệu quả là lớn nhất bằng cách loại bỏ ra không quá \(k\) công nhân. Đây là công việc vô cùng khó khăn, vì thế bạn hãy giúp SHIBA hoàn thành nhé.

Lưu ý:

• nếu không có công nhân nào xây dựng thì chỉ số hiệu quả được tính bằng \(0\).
• bạn có thể tham khảo về phép AND tại đây https://en.wikipedia.org/wiki/Bitwise_operation#AND

Input:

• Dòng thứ nhất chứa \(1\) số nguyên dương \(q\) (\(1 \le q \le 10^4\)).
• \(q\) dòng tiếp theo mỗi dòng chứa \(3\) số nguyên dương \(l,r,k\) (\(1 \le l \le r \le 10^6,1 \le k \le 10^2\)).

Output:

• Gồm \(q\) dòng, mỗi dòng in ra chỉ số hiệu quả lớn nhất sau khi loại bỏ ra không quá \(k\) công nhân.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le l,r,k,q \le 10^2\)
• Subtask \(2\) (\(80\%\) số điểm): \(1 \le l,r \le 10^6, 1 \le k \le 10^2,1 \le q \le 10^4\)

Example

2
1 3 1
4 8 1

2
4

Hưng được stormgamming cho \(1\) cây vô hướng có trọng số, Hưng rất thích cái cây của stormgamming, vì nó quá đẹp nên Hưng đã xin stormgamming nhưng stormgamming không dễ dàng cho không như vậy. stormgamming cho Hưng \(k\) thiết bị quan sát, thiết bị quan sát sẽ được gắn trên một đỉnh của cây và có thể quan sát các đỉnh khác nó trong phạm vi \(\le r\), stormgamming cần biết trọng số tối đa khi có \(k\) thiết bị quan sát, một đỉnh có thể được quan sát bởi nhiều thiết bị và trọng số được lấy chỉ tính \(1\) lần, vì Hưng quá non nên không thể tìm được nên cần đến sự trợ giúp của bạn.

Input

• Dòng đầu tiên gồm \(3\) số nguyên dương \(n, k, r\) lần lượt là số đỉnh của cây, số thiết bị quan sát, phạm vi quan sát của mỗi thiết bị quan sát.
• Dòng thứ \(2\) gồm \(n\) số nguyên số nguyên thứ \(i\) là trọng số của đỉnh \(w_i\).
• \(n-1\) dòng tiếp theo gồm \(2\) số nguyên dương \(u, v\) \(-\) mô tả \(1\) cạnh trên cây.

Output

• Gồm \(1\) số nguyên dương là trọng số tối đa khi có \(k\) thiết bị quan sát.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \le k \le n \le 20\), \(1 \le r,w_i \le 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le k \le n \le 50\), \(1 \le r,w_i \le 50\).
• Subtask \(3\) (\(10\%\) số điểm): \(1 \le k \le n \le 1000\), \(1 \le r \le 1000\), \(0 \le w_i \le 10^{6}\), cây tạo thành \(1\) đường thẳng
• Subtask \(4\) (\(20\%\) số điểm): \(1 \le n,r \le 1000\), \(1 \le w_i \le 10^{6}\), \(k \le 2\).
• Subtask \(5\) (\(30\%\) số điểm): \(1 \le k \le n \le 1000\), \(1 \le r \le 1000\), \(0 \le w_i \le 10^{6}\).

Example

20 3 1
4 12 17 2 16 6 11 9 9 20 2 12 19 8 14 18 15 20 3 8 
1 2
1 3
3 4
1 5
2 6
2 7
2 8
7 9
7 10
8 11
10 12
3 13
3 14
1 15
5 16
1 17
11 18
4 19
7 20

157

"Tết tết tết tết đến rồi, tết tết tết tết đến rồi" - câu hát rất quen thuộc của mọi nhà mỗi dịp Tết đến, xuân về. Đó là với mọi người, còn với phuongman thì không, tại vì Tết thì đến rồi nhưng manthibichloi vẫn chưa đến đón phuongman đi chơi Tết. phuongman quyết định sẽ dỗi "người ấy" của mình.

Vì để có thể ~~làm phuongman hết dỗi mặc dù không tự nguyện~~ đi chơi với phuongman sớm nhất có thể, manthibichloi cần chọn con đường ngắn nhất để có thể đến nhà "người ấy". Trong thành phố nơi hai người ở, có \(n\) địa điểm, nhà của phuongman ở vị trí \(n\) còn nhà của manthibichloi ở vị trí \(1\). Trong thành phố có \(m\) con đường nối với nhau, các con đường này có thể đi theo cả hai hướng, con đường thứ \(i\) nối hai địa điểm \(u_{i}\) và \(v_{i}\), khi đi hết con đường đó tốn một khoảng thời gian là \(t_{i}\) giây. Tuy nhiên, con đường nào cũng cần phải trả phí, vì thế anh ta muốn chọn con đường ngắn nhất và phí phải trả là ít nhất. Con đường thứ \(i\) sẽ ngốn của anh ta một khoản tiền có giá trị bằng \(c_{i}\). manthibichloi chỉ có thể đi trên con đường thứ \(i\) nếu hiện tại anh ấy có lượng tiền trong ví lớn hơn hoặc bằng \(c_{i}\). Ban đầu, trước khi đi, ví của manthibichloi có tất cả \(k\) đồng, đây cũng là số tiền tối đa manthibichloi có thể để trong ví. Ở bất cứ địa điểm nào, manthibichloi đều có thể đến cây ATM để rút tiền. Mỗi lần rút tiền ở cây ATM, anh ta có thể rút một lượng tiền bất kì, miễn sao cho lượng tiền đó khi bỏ vào ví sẽ không vượt quá \(k\) đồng. Mỗi lần rút tiền sẽ tốn của anh ấy \(1\) giây.

Yêu cầu: Tìm lượng thời gian nhỏ nhất có thể để manthibichloi có thể đến được nhà phuongman, trong những đường đi có thời gian ít nhất, tìm đường đi có số tiền mà sau khi đi trong ví còn nhiều tiền nhất. Nếu không tồn tại đường đi thì in ra -1 -1.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n \le 5 \times 10^4\), \(m \le 5 \times 10^5\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên biểu diễn một con đường (\(1 \le u,v \le n, 0 \le t \le 10^4, 0 \le c \le 10^3\)).
• Dòng cuối cùng là một số nguyên dương \(k\) (\(\max(c_{i}) \le k \le 10^3\)).

Output

• In ra hai số nguyên, lần lượt là thời gian ngắn nhất và số tiền trong ví sau khi đi hết con đường.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): \(c_{i} = 0\) với mọi \(i = 1, 2, 3..., m\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

7 7
2 1 2 1
2 4 2 1
4 3 2 1
4 5 1 1
2 5 3 1
5 6 2 1
7 6 8 1
3

16 2

Ở thành phố LQĐOJ, môn bóng đá là môn thịnh thành và được rất nhiều người yêu thích, nhất là các bạn lứa trẻ. Vào một ngày đẹp trời nọ, công ty của stormgamming - một công ty lớn nhất về sản xuất và kinh doanh bóng của thành phố bất ngờ tuyên bố phá sản. Nhận biết được điều này và cũng sắp đến tết, _minhduc định mở công ty bán bóng để tiếp tục thừa kế truyền thống yêu bóng đá của thành phố LQĐOJ và kiếm tiền đi chơi tết 😃

Xưởng của _minhduc có \(A\) quả bóng màu vàng và \(B\) quả bóng màu hồng. _minhduc cần đựng tất cả số bóng đó vào \(N\) cái hộp để đi bán nhưng vì không có kinh nghiệm nên anh đấy đã nhờ cht_duong đựng các quả bóng đó vào, nhưng không phải là đặt đại mà là phải đúng theo yêu cầu của _minhduc. Yêu cầu của _minhduc là các hộp phải đáp ứng được điều kiện của anh ta:

• Tất cả các hộp đều phải có ít nhất \(1\) quả bóng.

• Hai hộp bất kì không được trùng nhau. Hai hộp được xem là trùng nhau khi số bóng màu đỏ và số bóng màu hồng giữa hai hộp giống nhau.

Yêu cầu: Bạn hãy tìm và in ra \(N\) sao cho \(N\) là lớn nhất có thể nhưng vẫn thỏa mãn các yêu cầu trên biết rằng tất cả các quả bóng có trong xưởng phải được bỏ vào các hộp, không được bỏ sót quả nào.

Input

• Chứa hai số nguyên không âm lần lượt là \(A\) và \(B\) \((0 \le A,B \le 10^{12})\).

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\) (\(10\%\) số điểm): \(A = 0\) hoặc \(B = 0\) \((A \neq B)\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 \le A,B \le 50\).
• Subtask \(3\) (\(70\%\) số điểm): \(1 \le A,B \le 10^{12}\).

Example

8 3

5