LQDOJ Cup 2024 - Round #6

Công chúa vương quốc LQDOJ đã bị bắt bởi \(1\) con rồng đáng sợ, vì vậy, quốc vương quyết định nhờ bạn (một người giỏi võ nghệ) lên đường giải cứu công chúa.

Hang ổ của con rồng này nằm cách vương quốc \(n\) đơn vị khoảng cách, đường đi từ vương quốc đến hang ổ có thể coi như một trục số nằm ngang, mỗi vị trí \(i\) \((1 \le i \le n)\) nguyên trên đường đi lại có \(1\) trong \(4\) tính chất sau:

• Không gây ảnh hưởng gì đến bạn.
• Tăng cho bạn \(1\) thể lực.
• Tăng cho bạn \(1\) máu.
• Có \(1\) con quái vật là tay sai của con rồng, bạn có \(2\) lựa chọn: lẩn trốn và bị mất \(1\) máu, đánh bại con quái vật này và bị mất \(1\) thể lực.

Ban đầu, bạn có \(p\) thể lực và \(h\) máu.

Hãy giải cứu công chúa bằng cách tiêu diệt ít quái vật nhất mà luôn giữ cho máu và thể lực dương. Trong trường hợp bạn không thể giải cứu nàng, hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa \(3\) số nguyên dương \(n\), \(p\), \(h\) \((1 \le n, p, h \le 200)\).
• Dòng thứ hai chứa \(n\) số \(a_i\) \((0 \le a_i \le 3)\) với \(0\) là sẽ không gây ảnh hưởng đến bạn, \(1\) là tăng thể lực, \(2\) là tăng máu, và \(3\) là có quái vật.

Output

• Dòng đầu tiên chứa số nguyên \(x\) là số quái vật ít nhất cần tiêu diệt.
• Dòng thứ hai chứa \(x\) số nguyên dương \(t_i\) \((1 \le t_i \le n)\) là các vị trí của quái vật bạn sẽ tiêu diệt in theo thứ tự bất kì, nếu có nhiều phương án, in \(1\) phương án bất kì.

Scoring

• Subtask \(1\) (\(35\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(25\%\) số điểm): Không có vị trí loại \(1\) và \(2\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 1 1
0 0 2 3 1

0

Trong hành trình khai phá sao Hỏa năm 3000, người ta phát hiện rằng đã bắt đầu có dấu hiệu rõ ràng của sự sống trên hành tinh này. Sau khi tiến hành một cuộc rà soát diện rộng, người ta tìm được \(n\) sinh vật trên hành tinh này, các sinh vật được đánh số từ \(1\) đến \(n\), sinh vật thứ \(i\) \((1 \leq i \leq n)\) được gán cho một nhãn \(a_i\) dựa vào các đặc tính của nó.

Khi mẫu vật của \(n\) sinh vật được đưa về Trái Đất, các nhà khoa học tiến hành nghiên cứu các sinh vật này. Một trong những vấn đề được quan tâm hàng đầu là dựa vào các đặc tính đã biết của các sinh vật để nghiên cứu sự tương tác giữa các sinh vật trên với nhau, từ đó có thể phát hiện ra được nhiều đặc tính hơn nữa.

Mỗi lần lấy mẫu, người ta có thể chọn ra một số các sinh vật có chỉ số \(i_1, i_2, \ldots, i_k\) \((0 < k \leq n, 1 \leq i_1 < i_2 < \ldots < i_k \leq n)\). Người ta gọi mức hòa hợp của các sinh vật được chọn là \(\gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) \times \min(a_{i_1}, a_{i_1 + 1}, a_{i_1+2}, \ldots, a_{i_k})\).

Rõ ràng có \(2^n - 1\) cách chọn ra một số các sinh vật. Hai cách chọn được coi là khác nhau nếu tồn tại một sinh vật mà được chọn trong cách này nhưng không được chọn trong cách kia.

Yêu cầu: Hãy tính tổng mức hòa hợp của \(2^n - 1\) cách chọn ra các sinh vật như trên.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq {10}^5)\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq {10}^5)\).

Output

• Gồm duy nhất một số nguyên dương là tổng mức hòa hợp của tất cả \(2^n - 1\) cách chọn ra một số các sinh vật khác nhau, vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư của tổng mức hòa hợp khi chia cho \(({10}^9 + 7)\).

Scoring

• Subtask 1 (\(11\%\) số điểm): \(n \leq 100, a_i \leq 100\).
• Subtask 2 (\(13\%\) số điểm): \(n \leq 2000\).
• Subtask 3 (\(15\%\) số điểm): \(\gcd(a_i, a_j) = 1\), \(\forall 1 \leq i, j \leq n\) và \(i \neq j\).
• Subtask 4 (\(17\%\) số điểm): \(a_i = i\), \(\forall 1 \leq i \leq n\).
• Subtask 5 (\(21\%\) số điểm): \(a_i = 2^k\) \((0 \leq k < 17)\), \(\forall 1 \leq i \leq n\).
• Subtask 6 (\(23\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
10

100

3
1 2 3

19

2
2 4

24

Trang trại của Nam là trang trại sản xuất sữa với chất lượng cao nhất cả nước, gồm những chú bò vui vẻ, việc của các chú là vui chơi và đảm bảo dinh dưỡng để sản xuất ra những li sữa bò thơm ngon, chất lượng nhất có thể.

Các chú bò thường lăn lộn, ăn uống trên đồng cỏ của trang trại. Xem đồng cỏ như một mặt phẳng lớn vô hạn, vì trang trại quá lớn nên Nam đã định nghĩa một hệ trục tọa độ \(O_{xy}\) trên đồng cỏ để các chú bò không bị lạc đường.

Những chú bò vui vẻ có \(n\) "điểm ăn cỏ" yêu thích. Các điểm trên được đánh số từ \(1\) đến \(n\), điểm thứ \(i\) \((1 \leq i \leq n)\) có tọa độ là \((x_i, y_i)\).

Cho \(n\) điểm trên mặt phẳng tọa độ hai chiều, điểm thứ \(i\) có tọa độ là \((x_i, y_i)\). Để các chú bò không đi quá xa trang trại, Trung quyết định xây một hàng rào hình chữ nhật chứa tất cả \(n\) "điểm ăn cỏ" của các chú bò.

Tin tức Nam xây hàng rào đã được lan truyền trong trang trại và khiến các chú bò khá buồn, các chú bò rất yêu thích được ngắm không gian rộng lớn bên ngoài hàng rào nên yêu cầu phải có ít nhất một cặp "điểm ăn cỏ" nằm trên một trong bốn cạnh của hình chữ nhật, để các chú bò vừa ăn cỏ vừa ngắm cảnh cùng nhau.

Yêu cầu: Hãy đưa ra diện tích nhỏ nhất có thể của hình chữ nhật thỏa mãn các yêu cầu trên.

Lưu ý: Ta quy ước hình chữ nhật có chiều dài hoặc chiều rộng bằng \(0\) (suy biến thành một đường thẳng) có diện tích là \(0\).

Input

• Dòng đầu tiên gồm số nguyên dương duy nhất \(n(1 \leq n \leq 5000)\) --- số lượng "điểm ăn cỏ".
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo gồm hai số nguyên \(x_i, y_i (1 \leq x_i \leq 10^3, 1 \leq y_i \leq 10^3)\) --- Mô tả tọa độ của "điểm ăn cỏ" thứ \(i\).

Output

• Gồm một dòng duy nhất là diện tích nhỏ nhất của hình chữ nhật thỏa mãn yêu cầu đề bài. Đáp án được chấp nhận nếu sai số không quá \(10^{-6}\).

Scoring

• Subtask \(1\) (\(29\%\) số điểm): \(n = 3\).
• Subtask \(3\) (\(27\%\) số điểm): \(n \leq 100\).
• Subtask \(3\) (\(23\%\) số điểm): \(n \leq 500\).
• Subtask \(4\) (\(21\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 8
5 1
3 4

5.000000000000

8
16 4
10 6
22 6
24 18
18 20
10 18
26 10
6 14

277.176470588235