OLP MTTN 2022 - Vòng Chung kết - Bảng Không chuyên

Thời gian rảnh Thuận thường hướng dẫn các em nhỏ học lập trình, dưới đây là một bài toán rèn luyện kĩ năng cũng như tư duy lập trình.

Cho một dãy số nguyên dương \(a_1, a_2, ..., a_n (1 < a_i \le 10^9)\) và số nguyên dương \(t (1 \le t \le 3)\). Gọi \(s_1, s_2, s_3\) tương ứng là số bộ chỉ số \(1 \le i < j < k \le n\) mà \(a_i, a_j, a_k\) là ba cạnh của một tam giác nhọn, tam giác vuông, tam giác tù. Hãy tính giá trị \(s_t\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương \(n, t\);
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n\).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là giá trị \(s_t\) tính được.

Scoring

• Subtask #1 (\(30\%\) số điểm): \(n = 3\) và 10% cho từng giá trị của \(t\);
• Subtask #2 (\(30\%\) số điểm): \(n \le 300\) và 10% cho từng giá trị của \(t\);
• Subtask #3 (\(40\%\) số điểm): \(n \le 3000\)

Example

3 2
3 4 5

1

4 1
3 4 5 6

1

Bể nước nhà Thuận có hai vòi nước cùng chảy vào bể, nếu chỉ mở vòi thứ nhất thì phải mất \(a\) giờ mới đầy bể, còn nếu chỉ mở vòi thứ hai thì phải mất \(b\) giờ mới đầy bể. Thuận muốn biết nếu cả hai vòi cùng mở thì mất bao lâu thời gian để đầy bể.

Input

Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên dương \(a,b\) \((a,b\leq 10^6)\).

Output

Ghi ra thiết bị ra chuẩn một dòng chứa một số thực với độ chính xác \(10^{-5}\) là thời gian để bể đầy nước nếu mở cả hai vòi.

Example

4 5

2.22222

Thuận có một dãy đèn gồm đèn, các đèn được đánh số từ \(1\) đến \(n\). Mỗi đèn có ba trạng thái, trạng thái sáng màu xanh hoặc sáng màu đỏ hoặc tắt. Ban đầu tất cả các đèn đều ở trạng thái tắt. Tương ứng với đèn thứ có công tắc thứ \(i (1 \le i \le n)\), khi tác động vào công tắc này trạng thái đèn thứ \(i\) sẽ thay đổi như sau:

• Nếu đèn đang ở trạng thái tắt sẽ chuyển sang trạng thái sáng màu xanh;
• Nếu đèn đang ở trạng thái sáng màu xanh sẽ chuyển sang trạng thái sáng màu đỏ;
• Nếu đèn đang ở trạng thái sáng màu đỏ sẽ chuyển sang trạng thái tắt.

Thuận đã thực hiện một dãy gồm \(t\) lần tác động vào các công tắc và nhận được dãy đèn gồm \(a\) đèn ở trạng thái sáng màu xanh và \(b\) đèn ở trạng thái sáng màu đỏ. Là người yêu thích Tin học, Thuận muốn tính xem có bao nhiêu dãy gồm đúng \(t\) thao tác để từ trạng thái ban đầu (tất cả các đèn ở trạng thái tắt), sau khi thực hiện dãy thao tác có \(a\) đèn ở trạng thái sáng màu xanh và \(b\) đèn ở trạng thái sáng màu đỏ.

Yêu cầu: Cho các số nguyên \(n, t, a, b\), gọi là số dãy gồm thao tác để từ trạng thái ban đầu nhận được dãy có \(a\) đèn ở trạng thái sáng màu xanh và \(b\) đèn ở trạng thái sáng màu đỏ. Hãy tính \(S \% (10^9 + 7)\), trong đó \(\%\) là phép toán chia lấy dư.

Input

Vào từ thiết bị vào chuẩn gồm một dòng chứa bốn số nguyên \(n, t, a, b\) cách nhau bởi dấu cách \((0 \le a, b; a + b \le n)\);

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là giá trị \(S \% (10^9 + 7)\)

Scoring

• Subtask #1 (\(30\%\) số điểm): \(n, t \le 6\);
• Subtask #2 (\(30\%\) số điểm): \(n, t \le 60\);
• Subtask #3 (\(40\%\) số điểm): \(n, t \le 600\);

Example

2 3 1 1

6

1, 1, 2
1, 2, 1
1, 2, 2
2, 1, 1
2, 1, 2
2, 2, 1

Thành phố Thuận ở được biểu diễn bằng một bảng hai chiều kích thước \(m\times n\). Các hàng của bảng được đánh số từ đến từ trên xuống dưới, các cột của bảng được đánh số từ \(1\) đến \(n\) từ trái sang phải. Khu vực dân cư nằm giao giữa hàng \(i\) và cột \(j\) được gọi là khu vực dân cư \((i, j)\).

Hiện tại có \(k\) siêu thị đang hoạt động, siêu thị thứ \(t (1 \le t \le k)\) sẽ phục vụ các khu vực dân cư nằm trong hình chữ nhật có ô trái trên là khu vực dân cư \((x_t, y_t)\) và ô phải dưới là khu vực dân cư \((u_t, v_t)\). Theo phân tích đánh giá, dân cư một khu vực sẽ hạnh phúc nếu khu vực đó có đúng \(s\) siêu thị phục vụ. Thuận dự định mở một siêu thị, siêu thị cũng sẽ phục vụ các khu vực dân cư nằm trong một hình chữ nhật, Thuận mong muốn số lượng khu vực dân cư có đúng \(s\) siêu thị phục vụ là nhiều nhất.

Yêu cầu: Hãy giúp Thuận xác định một hình chữ nhật là khu vực mà siêu thị của Thuận sẽ phục vụ để số lượng khu vực dân cư có đúng \(s\) siêu thị phục vụ là nhiều nhất.

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng thứ nhất chứa bốn số nguyên dương \(m, n, k\) và \(s (1 \le s \le k \le 10^{15})\)
• Dòng thứ \(t (1 \le t \le k)\) trong \(k\) dòng tiếp theo chứa \(4\) số nguyên dương \(x_t, y_t, u_t, v_t (1 \le x_t \le u_t \le m; 1 \le y_t \le v_t \le n)\)

Output

• Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là số lượng khu vực dân cư có đúng \(s\) siêu thị phục vụ là nhiều nhất.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m, n \le 20\);
• Subtask \(2\) (\(30\%\) số điểm): \(m, n \le 80\);
• Subtask \(3\) (\(30\%\) số điểm): \(m, n \le 400\)

Example

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

8

1 1 1 1
1 1 1 1

0