Tin học trẻ C1 - HảI Dương - Bình Phước 2024

Lớp của Thuận tổ chức đi chơi du lịch đến Nha Trang. Khi đến Nha Trang, họ có một buổi chiều tắm biển rất vui vẻ. Sau khi chơi vui vẻ, họ quyết định trở về khách sạn. Đoạn đường từ biển về khách sạn có độ dài là \(l\) mét. Mỗi người đều có thể đi bộ với vận tốc là \(v_{1}\) mét mỗi giây. Tuy nhiên, do đã chơi cả chiều nên ai cũng thấm mệt, họ quyết định gọi xe để trở về khách sạn. Xe có thể chở tối đa \(k\) người trong cùng một thời điểm và có vận tốc là \(v_{2}\) mét mỗi giây. Mọi người sẽ chia nhau lên xe và đi bộ, tuy nhiên mỗi người sẽ chỉ lên xe nhiều nhất một lần.

Hãy xác định khoảng thời gian ngắn nhất để tất cả \(n\) người đều trở về được khách sạn, coi khoảng thời gian lên xe và xuống xe là ngay lập tức và ta có thể bỏ qua khoảng thời gian này.

Input

• Một dòng chứa năm số nguyên \(n, l, v_{1}, v_{2}, k\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq l \leq 10^{9}, 1 \leq v_{1} < v_{2} \leq 10^{9}, 1 \leq k \leq n)\).

Output

• Đưa ra một số thực là khoảng thời gian ngắn nhất (tính theo giây) để cả \(n\) người đều trở về được khách sạn. Sai số tối đa cho phép là \(10^{-6}\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(k = n\).
• Subtask \(2\) (\(30\%\) số điểm): \(\left\lceil \frac{n}{2} \right\rceil \leq k \leq n\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5 10 2 4 5

2.5

Một công xưởng đã sản xuất ra một dãy \(n\) con chip được gắn liền kề với nhau, con chip thứ \(i\) đang hoạt động ở công suất \(a_{i}\). Vì được gắn liền kề nhau nên công suất của những con chip có sự tác động lẫn nhau và làm ảnh hưởng đến công suất hoạt động của cả đoạn. Ta định nghĩa tổng công suất của các con chip trong một đoạn chip \([l, r]\) \((1 \leq l \leq r \leq n)\) được xác định bởi giá trị nhỏ nhất của đoạn chip đó. Để chiết xuất một đoạn chip hoạt động hiệu quả, nhà sản xuất muốn biết rằng với mỗi số nguyên \(x\) từ \(1\) đến \(n\), đoạn chip có độ dài \(x\) có tổng công suất lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 2 \times 10^{5})\) là số lượng chip của công xưởng.
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là công suất hoạt động của các con chip.

Output

• Gồm \(n\) số nguyên dương trên 1 dòng, số nguyên thứ \(x\) là tổng công suất lớn nhất của đoạn chip độ dài \(x\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 1000\).
• Subtask \(3\) (\(10\%\) số điểm): \(a_{i} \leq 100\).
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 5000\).
• Subtask \(5\) (\(35\%\) số điểm): không có ràng buộc gì thêm.

Example

4
2 1 4 5

5 4 1 1

Trong Geometry Dash, các chướng ngại vật thường có thể được chia thành hai loại chướng ngại vật chính là gai nhọn và bức tường. Việc thiết kế chướng ngại vật được gọi là thiết kế hay nếu như các chướng ngại vật bức tường không được đặt cạnh nhau quá nhiều. Một màn chơi đương nhiên sẽ hay nếu như màn chơi ấy được thiết kế hay.

Hiểu được điều này, Tèo đã vẽ ra \(t\) kế hoạch kinh doanh và mỗi kế hoạch có dạng như sau: Với mỗi kế hoạch Tèo sẽ dùng số tiền \(n\) đô la ít ỏi của mình để mua \(n\) chướng ngại vật trong game nhằm thiết kế một màn chơi hay để sinh lời. Tèo chọn ra một số \(k\) phong thủy là số bức tường tối đa có thể được đặt cạnh nhau. Dựa trên số cách có thể thiết kế màn chơi mà Tèo quyết định có dùng phương án này hay không.

Yêu cầu: Với mỗi kế hoạch, bạn hãy giúp Tèo đếm số cách thiết kế màn chơi nhé.

Input

• Dòng đầu tiên chứa \(T\) \((T \leq 10\)).
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số \(n\) và \(k\) \((1 \leq n \leq 10^{5}, 0 \leq k \leq \min(n, 20))\).

Output

• Gồm \(t\) dòng, dòng thứ \(i\) là kết quả của kế hoạch thứ \(i\), vì kết quả rất lớn nên chỉ cần in ra số dư của kết quả khi chia cho \(220220061\).

Scoring

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

Example

2
3 1
5 1

5
13

Hôm nay anh em nhà Hiếu chơi một trò chơi với hoán vị. Anh em nhà Hiếu được cho một dãy hoán vị \(p_{1}, p_{2}, \ldots, p_{n}\) (hoán vị là một dãy số mà mỗi số nguyên từ \(1\) tới \(n\) được xuất hiện chính xác một lần). Trọng số của phần tử thứ \(i\) trong hoán vị là \(a_{i}\).

Đầu tiên, Hiếu và em trai chọn một phần tử thứ \(i\) \((1 \leq i < n)\), sau đó chia dãy hoán vị làm hai phần. Hiếu sẽ lấy các phần tử của dãy hoán vị từ vị trí thứ \(1\) đến vị trí thứ \(i\) (lấy các phần tử có giá trị từ \(p_{1}\) đến \(p_{i}\)), còn em trai của Hiếu sẽ lấy các phần tử của dãy hoán vị từ vị trí thứ \(i + 1\) đến vị trí thứ \(n\) (lấy các phần tử có giá trị từ \(p_{i + 1}\) đến \(p_{n}\)).

Sau đó, Hiếu và em trai thực hiện "trao đổi" các phần tử cho nhau. Cụ thể hơn, Hiếu có thể đưa cho em trai một, hoặc vài số (có thể là không đưa) bất kì trong dãy hoán vị của Hiếu cho em trai. Ngược lại, em trai cũng có thể đưa Hiếu một, hoặc vài số (cũng có thể không đưa) bất kì trong dãy hoán vị của mình cho Hiếu. Việc trao đổi số \(p_{i}\) sẽ tốn một chi phí là \(a_{i}\).

Mục tiêu của trò chơi là trao đổi các số trong dãy hoán vị, sao cho giá trị của số lớn nhất trong các phần tử mà Hiếu sở hữu sau khi trao đổi nhỏ hơn giá trị của số nhỏ nhất trong các phần tử mà em trai của Hiếu sở hữu sau khi trao đổi. Trò chơi cũng được tính là thành công nếu một trong hai dãy trở thành dãy rỗng.

Ví dụ, nếu \(p = [3, 1, 2]\) và \(a = [7, 1, 5]\) thì họ có thể thực hiện trò chơi như sau: chia dãy \(p\) thành hai phần là \([3, 1]\) và \([2]\) rồi đổi chỗ phần tử có giá trị bằng \(2\) từ phần thứ hai sang phần thứ nhất (chi phí là \(5\)). Nếu \(p = [3, 5, 1, 6, 2, 4], a = [9, 2, 9, 9, 3, 9]\) thì ta chia \(p\) thành hai phần là \([3, 5, 1]\) và \([6, 2, 4]\), và đổi phần tử có giá trị bằng \(5\) từ phần thứ nhất sang phần thứ hai, đổi phần tử có giá trị bằng \(2\) từ phần thứ hai sang phần thứ nhất (chi phí là \(5\)).

Bạn hãy giúp anh em nhà Hiếu tính chi phí nhỏ nhất cần sử dụng để sau khi thực hiện tất cả các thao tác, hai dãy mà anh em nhà Hiếu nhận được là thỏa mãn yêu cầu đề bài.

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) \((2 \leq n \leq 2 \times 10^{5})\) là độ dài của hoán vị.
• Dòng thứ hai chứa \(n\) số nguyên \(p_{1}, p_{2}, \ldots, p_{n}\) \((1 \leq p_{i} \leq n)\). Dữ liệu đảm bảo dãy chứa các phần tử có giá trị từ \(1\) đến \(n\), mỗi giá trị xuất hiện chính xác một lần.
• Dòng thứ ba chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).

Output

• Đưa ra một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3
3 1 2
7 2 5

5