Thi thử VOI ngày 2

Bài 1. xyz

Nhóm \(n\) người bạn của Alice bị lạc vào không gian, hiện tại người thứ \(t\) (\(1 \le t \le n\)) ở tọa độ \((x_t, y_t, z_t)\). Alice muốn chia \(n\) người thành ba nhóm, mỗi nhóm ít nhất một người để hỗ trợ và liên lạc với nhau. Nhóm thứ nhất sẽ dùng chiều không gian \(x\) để liên lạc, do đó chi phí để thiết lập kênh liên lạc cho nhóm thứ nhất được tính bằng \(\max X - \min X\), trong đó \(\max X\) và \(\min X\) tương ứng là tọa độ \(x\) lớn nhất và nhỏ nhất trong những người được phân vào nhóm thứ nhất. Tương tự, nhóm thứ hai sẽ dùng chiều không gian \(y\) để liên lạc và chi phí thiết lập kênh liên lạc được tính bằng \(\max Y - \min Y\); chi phí cho nhóm thứ ba bằng \(\max Z - \min Z\). Alice chia nhóm để tổng chi phí thiết lập kênh liên lạc cho cả ba nhóm là nhỏ nhất.

Yêu cầu: Cho \(n\) tọa độ \(x_t, y_t, z_t\), hãy giúp Alice chia nhóm để tổng chi phí thiết lập kênh liên lạc cho cả ba nhóm là nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ \(t\) (\(1 \le t \le n\)) trong \(n\) dòng tiếp theo chứa ba số nguyên \(x_t, y_t, z_t\) (\(-10^9 \le x_t, y_t, z_t \le 10^9\)).

Output

• Ghi ra một dòng chứa một số nguyên là tổng chi phí nhỏ nhất để thiết lập kênh liên lạc cho cả ba nhóm.

Example

6
1 5 5
5 5 5
9 9 9
8 8 8
1 3 3
1 5 9

1

Scoring

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 10\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 20\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 40\).
• Có \(25\%\) số test còn lại ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 100\).

Công ty của Alice vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của robot, Alice tạo ra một bức tường từ \(n\) cột các khối lập phương, các cột đặt cạnh nhau, bề dày bức tường là \(1\) và với độ cao tương ứng là \(a_1, a_2, \ldots, a_n\), trong đó \(a_i\) là độ cao cột thứ \(i\) (do \(a_i\) khối lập phương tạo lên). Robot được giao nhiệm vụ thay đổi bức tường với độ cao tương ứng là \(b_1, b_2, \ldots, b_n\). Robot chỉ có thể thực hiện một trong ba loại thao tác sau:

• Thao tác 1: Lấy khối trên cùng của một cột để bỏ đi, thời gian thực hiện thao tác này là \(x\);
• Thao tác 2: Lấy một khối mới, đặt khối đó lên trên cùng của một cột, thời gian thực hiện thao tác này là \(y\);
• Thao tác 3: Chuyển một khối từ cột \(i\) sang cột \(j\), thời gian thực hiện thao tác này là \(z \cdot |i-j|\).

Yêu cầu: Cho \(a_1, a_2, \ldots, a_n\); \(b_1, b_2, \ldots, b_n\) và \(x, y, z\). Hãy xác định thời gian ngắn nhất để robot hoàn thành nhiệm vụ.

Input

• Dòng đầu chứa bốn số nguyên dương \(n, x, y, z\) (\(x, y, z \le 1000\));
• Dòng thứ hai gồm \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10\));
• Dòng thứ ba gồm \(n\) số nguyên không âm \(b_1, b_2, \ldots, b_n\) (\(b_i \le 10\)).

Output

• Ghi ra một dòng chứa một số nguyên là thời gian ít nhất để robot hoàn thành nhiệm vụ.

Example

4 10 10 1
1 2 2 4
2 2 2 2

13

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\) và \(a_i, b_i \le 1\);
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 10^2\) và \(a_i, b_i \le 1\);
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 10^3\);
• Subtask \(4\) (\(25\%\) số điểm): \(n \le 10^5\).

Bài 3. Monodigit

Một số được gọi là monodigit nếu nó có tất cả các chữ số giống nhau. Cho độ dài lớn nhất \(L\) và tập \(A\) gồm \(n\) số nguyên dương, bạn hãy tìm số monodigit lớn nhất sao cho:

• Có độ dài không quá \(L\) chữ số.
• Chia hết cho ít nhất \(2\) phần tử của tập \(A\).

Input

• Dòng đầu tiên chứa \(2\) số nguyên dương \(L, n\) (\(1 \le L \le 10^9\), \(2 \le n \le 10\)).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_i\) (\(1 \le a_i \le 10^6\)).

Output

• Mỗi số monodigit được biểu diễn bởi \(2\) giá trị \(\ell\) và \(d\) trong đó \(\ell\) là độ dài và \(d\) là chữ số mà nó chứa. Bạn hãy in ra hai giá trị này.

Example

2 2
2 3

2 6

10 2
2021 2022

1 0

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(1 \le L \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(1 \le L \le 1000\), \(1 \le a_i \le 1000\).
• Subtask \(3\) (\(25\%\) số điểm): \(1 \le L \le 10^9\), \(1 \le a_i \le 1000\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.