Ôn luyện vào chuyên Tin #03

Cho hoán vị \(A = (a_1 , a_2 ,..., a_N)\) của \(N\) số nguyên dương đầu tiên \(1, 2,..., N (2 ≤ N ≤ 1000)\). Một thuận thế của \(A\) là dãy \(B = (b_1 , b_2 ,..., b_N)\) trong đó \(b_i\) là số lượng các phần tử nhỏ hơn \(a_i\) và đứng trước \(a_i\).

Yêu cầu: Cho một hoán vị \(A\), tính thuận thế \(B\) của \(A\).

Input

• Dòng đầu ghi số \(N\).
• Dòng thứ hai chứa hoán vị \(A\).

Output

• Ghi ra thuận thế \(B\) của hoán vị \(A\).

Example

9
2 1 7 6 5 4 3 8 9 

0 0 2 2 2 2 2 7 8

Cho số tự nhiên \(A\) có \(N\) chữ số và số tự nhiên \(B\) có \(M\) chữ số \((2 ≤ N , M ≤ 200)\). Số nguyên dương \(C\) gồm các tính chất sau đây:

• Có \(N\) + \(M\) chữ số;
• Được tạo bởi từ các chữ số của \(A\) và \(B\);
• Thứ tự trước sau các chữ số của \(B\) trong \(C\) không thay đổi.

Yêu cầu: Tìm số \(C\) nhỏ nhất và số \(C\) lớn nhất.

Input

• Dòng đầu ghi số \(A\).
• Dòng tiếp theo ghi số \(B\).

Output

• Dòng đầu ghi số \(C\) nhỏ nhất
• Dòng tiếp theo ghi số \(C\) lớn nhất

Example

20
4181 

204181
421810

Một giáo viên cần giảng \(N\) vấn đề được đánh số từ 1 đến \(N\) (\(N \le 1000\)). Mỗi một vấn đề \(i\) có thời gian là \(A_i\ (i=1…N)\). Mỗi vấn đề chỉ giảng không quá 1 buổi. Thời gian tối đa của một buổi là \(L\) (\(L \le 500\)). Vấn đề \(i\) phải được giảng trước vấn đề \(i+1\). Trong một buổi có thể bố trí giảng vài vấn đề nhưng nếu thừa lượng thời gian \(t\) thì buổi đó được đánh giá là lãng phí thời gian với mức \(d\) (\(d\) có giá trị như sau):

• \(0\) nếu \(t=0\)
• \(-c\) nếu \(1 \le t \le 10\)
• \((t-10)^2\) nếu \(t>10\)

Trong đó \(c\) là hằng số nguyên dương cho trước.

Yêu cầu: Hãy xếp lịch dạy sao cho số buổi ít nhất và tổng các lãng phí thời gian là nhỏ nhất có thể được.

Dữ liệu

• Dòng đầu tiên là số \(N\ (N \le 1000)\)
• Dòng tiếp theo là \(L\) và \(C\)
• Dòng cuối cùng là \(N\) số thể hiện \(A_1, A_2, …, A_N\) (\(A_1 \le L\))

Kết quả

• Dòng đầu tiên là số buổi của lịch
• Dòng tiếp theo là tổng thời gian lãng phí nhỏ nhất đạt được.

Sample Input 1

10
120 10
80 80 10 50 30 20 40 30 120 100

Sample Output 1

6
2700

Nguồn: HSG 12 QNam 2015

Cho dãy số nguyên \(𝐴 = (𝑎_1, 𝑎_2, … , 𝑎_𝑛)\) và một số nguyên dương \(𝑘 \leq 𝑛\). Với mỗi giá trị \(𝑖\ (1 \leq 𝑖 \leq 𝑛 − 𝑘 + 1)\), hãy xác định giá trị nhỏ nhất trong \(𝑘\) phần tử liên tiếp: \(𝑎_𝑖, 𝑎_{𝑖+1}, … , 𝑎_{𝑖+𝑘−1}\)

Input

• Dòng 1 chứa hai số nguyên dương \(𝑛 \leq 5.10^5, 𝑘 \leq 𝑛\)
• Dòng 2 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛 (\forall 𝑖: 𝑎_𝑖 \leq 10^6)\)

Output

• Ghi ra \(𝑛 − 𝑘 + 1\) dòng, dòng thứ \(𝑖\) ghi giá trị nhỏ nhất trong các phần tử \(𝑎_𝑖, 𝑎_{𝑖+1}, … , 𝑎_{𝑖+𝑘−1}\)

Các số trên một dòng của Input files được ghi cách nhau ít nhất một dấu cách

Scoring

• Subtask \(1\) (\(33.3\%\) số điểm): \(𝑛 \leq 10^3, 𝑘 \leq 𝑛\)
• Subtask \(2\) (\(19.1\%\) số điểm): \(𝑛 \times k \leq 10^7, 𝑘 \leq 𝑛\)
• Subtask \(3\) (\(47.6\%\) số điểm): \(𝑛 \leq 5 \times 10^5, 𝑘 \leq 𝑛\)

Example

5 3
2 1 5 3 4 

1
1
3