Thi thử 24 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Màn hình	100 (p)	1.0s	256M
2	Dãy số tăng	100 (p)	1.0s	256M
3	Bánh mì và bánh rán	100 (p)	1.0s	256M
4	Giờ học giáo dục thể chất	100 (p)	1.0s	256M

1. Màn hình

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: DISP.INP Output: DISP.OUT

Một công ty lớn đã quyết định đưa ra một loại màn hình có đúng $n$ điểm ảnh được xếp thành các hàng và các cột.

Nhiệm vụ của bạn là xác định số hàng điểm ảnh $a$ và số cột điểm ảnh $b$ sao cho:

Có đúng $n$ điểm ảnh trên màn hình, tức là $a \times b = n $;
Số hàng điểm ảnh không vượt quá số cột điểm ảnh, tức là $a \leq b$;
Sự khác biệt $b - a$ càng nhỏ càng tốt;

Input

Gồm một dòng duy nhất chứa số nguyên $n$ ($1 \leq n \leq 10^{9}$).

Output

Gồm một dòng chứa hai số nguyên tương ứng là số hàng và số cột điểm ảnh cần tìm của màn hình.

Scoring

Có 30% số điểm tương ứng với: $1 \leq n \leq 10^{3}$;
Có 30% số điểm tương ứng với: $1 \leq n \leq 10^{7}$;
Có 40% số điểm : Không có thêm ràng buộc nào.

Example

Test 1

Input

Output

2 4

Test 2

Input

Output

5 5

2. Dãy số tăng

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: INCR.INP Output: INCR.OUT

Dãy số $a_1, a_2, \ldots, a_n$ được gọi là tăng nếu $a_1 < a_2 < \cdots < a_n$.

Bạn được cho một dãy số $b_1, b_2, \ldots, b_n$ và một số nguyên dương $d$. Trong mỗi lần thao tác, bạn chọn một phần tử của dãy số và cộng thêm $d$ vào nó. Số thao tác ít nhất là bao nhiêu để biến đổi dãy số đã cho trở thành dãy số tăng.

Input

Dòng đầu tiên chứa hai số nguyên $n$ và $d$ ($1 \leq n \leq 10^5$; $1 \leq d \leq 10^9$).
Dòng thứ hai chứa $n$ số nguyên tương ứng là dãy số $b_1, b_2, ..., b_n$ ($1 \leq b_i \leq 10^9$).

Output

Gồm một số nguyên là số thao tác ít nhất để biến đổi dãy số đã cho trở thành dãy số tăng.

Scoring

Có 30% số test ứng với 30% số điểm thỏa mãn: $1 \leq n, d, b_i \leq 10^2$.
30% số test khác ứng với 30% số điểm thỏa mãn: $1 \leq n \leq 10^3$ và $1 \leq d, b_i \leq 10^6$.
40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.

Example

Test 1

Input

4 2
1 3 3 2

Output

Note

Trong ví dụ trên, ta có dãy số $b$ là: $1, 3, 3, 2$ và $d = 2$. Số thao tác ít nhất để biến đổi dãy số thành dãy số tăng là $3$ và một trong các cách thực hiện như sau:

Thao tác thứ nhất: Cộng thêm $d$ vào phần tử thứ ba, dãy số trở thành: $1, 3, 5, 2$;
Thao tác thứ hai: Cộng thêm $d$ vào phần tử thứ tư, dãy số trở thành: $1, 3, 5, 4$;
Thao tác thứ ba: Cộng thêm $d$ vào phần tử thứ tư, dãy số trở thành: $1, 3, 5, 6$ và là dãy số tăng.

3. Bánh mì và bánh rán

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: DONU.INP Output: DONU.OUT

Mẹ của An đã lên kế hoạch ăn sáng bằng bánh mì hoặc bánh rán cho An trong $n$ ngày (được đánh số từ $1$ đến $n$). Mẹ của An đã viết một xâu $s$ độ dài $n$, trong đó kí tự thứ $i$ ($1 \leq i \leq n$) là '0' hoặc '1' biểu thị ngày thứ $i$ sẽ ăn bánh mì hoặc bánh rán tương ứng.

An thích ăn bánh rán hơn bánh mì, nên anh ta muốn chọn một đoạn gồm $k$ kí tự liên tiếp trong xâu $s$ và thay đổi mỗi kí tự '0' trong đoạn này thành '1'. Gọi $time$ là số ngày liên tiếp dài nhất mà An ăn bánh rán. Bạn hãy giúp An tìm giá trị $time$ lớn nhất mà anh ta có thể đạt được bằng cách chọn một đoạn hợp lý.

Input

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \leq k \leq n \leq 10^6$).
Dòng thứ hai chứa xâu $s$ độ dài $n$, chỉ gồm các kí tự '0', '1'.

Output

Gồm một số nguyên là số $time$ lớn nhất.

Scoring

Có 30% số test ứng với 30% số điểm thỏa mãn: $1 \leq k \leq n \leq 10^2$.
30% số test khác ứng với 30% số điểm thỏa mãn: $1 \leq k \leq n \leq 10^3$.
40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.

Example

Test 1

Input

13 2
0101110000101

Output

Note

An cần chọn đoạn kí tự từ thứ 2 đến thứ 3 là "10", sau đó thay đổi kí tự thứ 3 trong $s$ thành '1' và $time$ là 5 ngày: từ thứ 2 đến thứ 6.

Test 2

Input

6 3 
100001

Output

Note

An cần chọn đoạn kí tự từ thứ 2 đến thứ 4 là "000", sau đó thay đổi tất cả các kí tự trong đoạn này từ '0' thành '1' và $time$ là 4 ngày: từ thứ 1 đến thứ 4.

4. Giờ học giáo dục thể chất

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: PHYS.INP Output: PHYS.OUT

Trước giờ học giáo dục thể chất, một lớp gồm $n$ học sinh xếp thành một hàng. Tất cả học sinh trong lớp đều có chiều cao khác nhau. Vị trí thứ $i$ (i = 1, 2, ..., n) tính từ đầu bên trái của hàng là học sinh có chiều cao $pi$ ($1 ≤ p_i ≤ n$).

Khi bắt đầu giờ học, thầy giáo có thể thay đổi thứ tự học sinh trong hàng. Để làm điều này, thầy giáo có thể thực hiện thao tác sau đúng một lần: chọn một đoạn từ vị trí $l$ đến vị trí $r$ ($1 ≤ l ≤ r ≤ n$) và sắp xếp các học sinh trong đoạn này theo chiều cao tăng dần từ trái sang phải. Ví dụ $n = 5$, ban đầu học sinh theo thứ tự có chiều cao là 5, 2, 4, 1, 3 và thầy giáo chọn $l = 1, r = 4$ thì sau khi sắp xếp học sinh sẽ theo thứ tự có chiều cao là 1, 2, 4, 5, 3.

Sử dụng thao tác này, thầy giáo có thể sắp xếp để hai học sinh nào đó cách xa nhau nhất có thể. Khoảng cách giữa hai học sinh bằng sự chênh lệch giữa các vị trí mà hai học sinh đứng. Với mỗi cặp học sinh, thầy giáo tính khoảng cách lớn nhất giữa hai học sinh này sau khi thực hiện đúng 1 thao tác nói trên. Bạn hãy giúp thầy giáo tìm tổng của các giá trị này.

Cụ thể hơn, hãy xét hai học sinh ban đầu ở vị trí $i$ và $j$ ($1 ≤ i < j ≤ n$). Gọi $d(i, j)$ là khoảng cách lớn nhất giữa hai học sinh đó mà thầy giáo có thể đạt được bằng cách chọn một đoạn và sắp xếp. Bạn cần tính tổng tất cả các giá trị $d(i, j)$ với mọi $i, j$ thỏa mãn $1 ≤ i < j ≤ n$.

Input

Dòng đầu tiên chứa một số nguyên $n$ là số học sinh trong lớp ($2 ≤ n ≤ 3000$).
Dòng thứ hai chứa n số nguyên $p_1, p_2, ..., p_n$ là chiều cao của từng học sinh trong hàng ($1 ≤ p_i ≤ n$). Dữ liệu đảm bảo rằng tất cả các số $p_i$ đều phân biệt.

Output

Gồm một số nguyên là câu trả lời cho bài toán.

Scoring

Có 20% số test ứng với 30% số điểm thỏa mãn: $n \leq 10$.
Có 20% số test ứng với 30% số điểm thỏa mãn: $n \leq 50$.
Có 20% số test ứng với 30% số điểm thỏa mãn: $n \leq 100$.
Có 20% số test ứng với 30% số điểm thỏa mãn: $n \leq 600$.
20% số test còn lại ứng với 20% số điểm: Không có thêm ràng buộc nào.

Example

Test 1

Input

5
5 2 4 1 3

Output

Note

Câu trả lời là tổng các số sau: $d(1, 2) = 3, d(1, 3) = 4, d(1, 4) = 4, d(1, 5) = 4, d(2, 3) = 3, d(2, 4) = 3, d(2, 5) = 4, d(3, 4) = 3, d(3, 5) = 3, d(4, 5) = 4.

Test 2

Input

10
2 1 6 8 3 5 9 10 7 4

Output

Test 3

Input

2
2 1

Output