LQDOJ Contest #4

Hàng năm làng LQDOJ tổ chức cho người dân thi đấu giải bóng đá có tên là FOS Champion League. Năm nay có \(N\) đội đăng kí tham dự giải, mỗi đội được gán một \(ID\) riêng biệt. FOS Champion League là giải đấu loại trực tiếp và Flower_On_Stone - phó trưởng làng được quyền quyết định đội thắng cuộc, đội thua cuộc sẽ bị loại khỏi giải đấu. Giải sẽ kết thúc khi chỉ còn một đội vô địch.

Flower_On_Stone nhận thấy một sự trùng lặp ngẫu nhiên trên bảng điểm điện tử trong các trận đấu.Trong bất kỳ trận đấu nào,điểm kết hợp của cả hai đội đấu đúng bằng phép toán XOR trên \(ID\) của hai đội. Ví dụ: Nếu hai đội có \(ID\) là \(12\) và \(20\) đang đấu thì tổng điểm của hai đội là \(28\) vì \((12\) XOR \(20) = 28\).

Chính vì điều thú vị này mà ban tổ chức muốn tổ chức thật nhiều trận đấu sao cho tổng điểm ghi được trong giải FOS Champion League là lớn nhất có thể.

Yêu cầu: Hãy giúp ban tổ chức lên lịch thi đấu sao cho tổng điểm ghi được là lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((2 \le N \le 2000)\).
• \(N\) dòng tiếp theo mỗi dòng chứa \(ID\) của một đội \((1 ≤ ID ≤ 1073741823)\).

Output

• In ra đáp án sau khi thực hiện yêu cầu bài toán.

Scoring

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

Example

4
3
6
9
10

37

Vào một ngày đẹp trời, _minhduc rủ shiba cùng chơi một trò chơi điện tử với cậu ấy. Trò chơi ấy diễn ra như sau:

Có tất cả \(n\) điểm, được sắp xếp lần lượt từ điểm \(1\) tới điểm \(n\). Ở điểm thứ \(i\) sẽ diễn ra một loại trò chơi mà nếu thắng thì người chiến thắng sẽ nhận được \(a_i\) điểm. Người chơi đi từ điểm \(1\) đến điểm \(n\) và tham gia chơi các trò chơi trên đoạn đường đó, tuy nhiên do không thể chơi liên tục nên có một giới hạn được gọi là "thanh năng lượng". Thanh năng lượng của người chơi ban đầu là \(m\) và có giới hạn tối đa là \(m\). Nếu như "thanh năng lượng" của người chơi về \(0\) thì người chơi sẽ không thể chơi trò chơi mà cần phải nghỉ ngơi. Nếu nghỉ ngơi thì cần nghỉ ngơi tới khi đầy thanh năng lượng mới có thể chơi tiếp. Mỗi lần chơi một trò chơi, thanh năng lượng của người chơi bị sụt giảm đi \(1\) đơn vị.

Do là một người chơi tài năng, _minhduc tự tin rằng có thể chiến thắng tất cả các trò chơi, tuy nhiên giới hạn duy nhất của cậu ấy chính là thanh năng lượng kia. Cậu ấy cần phải kết thúc tất cả trò chơi với một thanh năng lượng đầy. Cậu ấy không biết cách chơi như thế nào để có thể tối ưu được số điểm của mình. Bạn hãy giúp _minhduc nhé!

Yêu cầu: Tính số điểm lớn nhất mà _minhduc có thể nhận được.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(1 \le n \le 10^5, 1 \le m \le 200\)).
• 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 dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

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

Example

6 2
6 1 5 4 3 2

15

sunflower và anh03032007 là hai đứa trẻ tinh nghịch đang chơi trốn tìm tại nhà của _minhduc (vì nhà của _minhduc rất to (có thể coi là biệt phủ), điều đó thuận lợi cho việc chơi trốn tìm của hai đứa trẻ).

Nhà của _minhduc gồm \(N\) hàng và \(M\) cột và có hai giá trị là X hoặc O.

Hiện tại sunflower là người tìm và anh03032007 là người trốn. anh03032007 chỉ có thể trốn ở chỗ có kí tự O, và anh ấy đang cần đếm số lượng kí tự O đó để thuận lợi cho việc trốn hơn.

Bạn hãy giúp anh03032007 đếm xem ở cột dọc thứ \(i\) \((1 \le i \le M)\) đang có bao nhiêu quả kí tự O.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) \((1 \le N,M \le 1000)\).
• \(N\) dòng tiếp theo mỗi dòng chứa \(M\) giá trị X hoặc O viết liền nhau.

Output

• In ra đáp án sau khi thực hiện yêu cầu bài toán, mỗi giá trị cách nhau một khoảng cách.

Example

3 4
XXXO
XXOO
XOOO

0 1 2 3

Hôm nay là chủ nhật, shiba quyết định ra đảo chơi.

Quần đảo nơi shiba chơi có tất cả \(n\) đảo, được nối với nhau bằng \(m\) con đường một chiều. shiba quyết định sẽ đi tham quan từ đảo \(1\) tới đảo \(n\). Con đường thứ \(i\) nối hai đảo \(u_i\) và \(v_i\) với nhau có chi phí là \(c_i\). shiba có siêu năng lực là cải tạo các con đường (yep, ngay lập tức) tuy nhiên khả năng này chỉ có thể sử dụng \(k\) lần. Sau khi cải tạo, chi phí của con đường sẽ là \(\lfloor \frac{c_i}{2} \rfloor\). Tuy nhiên có một giới hạn là nếu như cậu ấy cải tạo ít nhất một con đường đến đỉnh thứ \(u\), thì cậu ấy sẽ không thể cải tạo bất cứ con đường nào đi ra từ đỉnh \(u\) đó.

Yêu cầu: Tìm đường đi ngắn nhất từ đảo \(1\) tới đảo \(n\). Nếu không thể tìm thấy đường đi, in ra -1.

Input

• Dòng thứ nhất chứa ba số nguyên dương \(n,m,k\) (\(n \le 10^3, m \le 10^5, k \le min(m,500)\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(u,v,c\) (\(u,v \le n, c \le 10^9\)).

Output

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

Example

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

3

Cho \(N \times 2\) quả bóng gồm \(N\) quả bóng màu vàng và \(N\) quả bóng màu xanh dương được đặt trong một hàng dọc được kí hiệu là \(color_i\) và \(a_i\). Trong đó \(color_i\) tượng trưng cho màu của quả bóng, \(color_i\) là yellow nếu quả bóng đó là màu vàng và \(color_i\) là blue nếu quả bóng đó là màu xanh dương và \(a_i\) là số thứ tự của quả bóng \((1\le a_i\le N)\).

Lúc đầu các quả bóng được sắp xếp ngẫu nhiên, shiba muốn sắp xếp các quả bóng bằng cách hoán đổi vị trí của hai quả bóng liền kề nhau cho đến khi \(N\) quả bóng màu vàng được sắp theo tăng dần từ trên xuống dưới theo số thứ tự và \(N\) quả bóng màu xanh dương được sắp theo tăng dần từ trên xuống dưới theo số thứ tự

Biết rằng shiba có thể thay đổi vị trí nhiều lần hoặc có thể không cần đổi, và mỗi lần chỉ được hoán đổi vị trí của hai quả bóng liền kề nhau. shiba chỉ quan tâm \(N\) quả bóng màu vàng được sắp theo tăng dần hay chưa (tương tự với quả bóng màu xanh dương) mà không cần quan tâm màu gì đứng trước màu gì.

Yêu cầu: Bạn hãy tìm số lần thực hiện thao tác ít nhất có thể để các quả bóng được sắp xếp theo đúng mong muốn của shiba.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2000)\).
• \(N \times 2\) Dòng tiếp theo mỗi dòng chứa hai giá trị \(color_i\) và \(a_i\)
  \((color_i =\) yellow hoặc \(color_i =\) blue, \(1 \le a_i \le N)\).
• Input luôn đảm bảo rằng số thứ tự của mỗi màu không bị trùng lặp.

Output

• In ra số lần thực hiện thao tác ít nhất có thể để các quả bóng được sắp xếp theo đúng các điều kiện trên.

Scoring

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

Example

3
yellow 2
blue 3
yellow 1
blue 1
blue 2
yellow 3

4

5
blue 3
blue 2
blue 5
yellow 4
blue 4
yellow 1
yellow 5
blue 1
yellow 2
yellow 3

15

shiba quyết định sẽ đi chợ tìm mì tôm về ăn. Chợ có tất cả \(N\) gói mì tôm, gói mì tôm thứ \(i\) có trọng lượng là \(W_i\). Do là người phàm ăn, shiba đã ăn hết tất cả các gói mì tôm trong chợ. Sau khi về đến nhà, shiba mới chợt nhớ ra là cậu ấy chưa cầm gói nào về nhà cả vì vậy cậu ấy quyết định sẽ trở lại chợ để mua mì cầm về nhà.

Tuy nhiên, do shiba đã ăn quá no nên cậu ấy sẽ không thể tự bê mì về được mà cần thuê xe kéo hàng. Cậu ấy cũng không nhớ rõ là gói mì tôm thứ \(i\) có trọng lượng là bao nhiêu, mà cậu ấy nhớ như sau: Giả sử có một dãy \(A\) gồm \(N - 1\) số nguyên, thì giá trị của \(A_i\) lớn hơn hoặc bằng trọng lượng lớn nhất của một trong hai gói mì \(W_i\) và \(W_{i+1}\).

Căng da bụng, trùng da mắt, shiba quyết định nhờ _minhduc ghi lại trọng lượng của từng gói mì tôm sao cho tổng trọng lượng của \(N\) gói mì tôm là lớn nhất có thể và đúng với điều kiện shiba đã nêu ra. Bạn hãy in ra tổng trọng lượng lớn nhất có thể của \(N\) gói mì tôm đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((2 \le N \le 100)\).
• Dòng tiếp theo chứa \(N-1\) số nguyên \(A_1,A_2,...,A_{N-1}\) \((0 \le A_i \le 10^5)\).

Output

• In ra đáp án sau khi thực hiện yêu cầu bài toán.

Example

3
1 3

5