Contest ôn tập THT bảng C2 - 2023 #04

Cho số nguyên dương \(L\) và số nguyên dương \(S\).

Yêu cầu: Bạn hãy lập chương trình in ra số nhỏ nhất có thể và số lớn nhất có thể, cặp số này phải thỏa mãn tất cả các điều kiện sau:

• Cặp số đó có \(L\) chữ số.
• Cặp số đó mỗi số có tổng các chữ số của chúng là \(S\).
• Cặp số đó bắt buộc mỗi số phải là một số nguyên dương và không được viết chữ số \(0\) ở đầu, chúng có thể bằng nhau.

Input

• Chứa hai số nguyên dương lần lượt là \(L\) và \(S\) được cách nhau bởi một dòng \((1 \le L \le 100,1 \le S \le 900)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài hai số được cách nhau bởi một dòng. Nếu không tìm được cặp thỏa mãn thì hãy in ra -1.

Example

2
15

69 
96

Cho số nguyên dương \(N\) và dãy số có \(N\) số nguyên \(a_1,a_2,...,a_N\).

Yêu cầu: Bạn hãy in ra tổng của tất cả các giá trị \(∣a_i - a_j∣\) thỏa mãn \(1 \le i < j \le N\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2 \times 10^5)\).
• Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_N\) \((-10^9 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.

Output

• In ra đáp án bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 1000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
5 1 2

8

Cho số nguyên dương \(N\) và dãy số có \(N\) số nguyên \(a_1,a_2,...,a_N\).

Ta sẽ xét dãy \(b = (b_1,b_2,...,b_N)\) và dãy \(c = (c_1,c_2,...,c_N)\) như sau:

• Với mỗi \(1 \le i \le N\) thì \(a_i = b_i + c_i\).
• \(b\) là dãy không giảm. Có nghĩa là \(b_i \le b_{i+1}\) với mọi \(1 \le i \le N-1\).
• \(c\) là dãy không tăng. Có nghĩa là \(c_i \ge c_{i+1}\) với mọi \(1 \le i \le N-1\).

Yêu cầu: Bạn hãy tạo ra dãy \(b\) và \(c\) thỏa mãn các điều kiện trên sao cho giá trị \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣)\) là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2 \times 10^5)\).
• Dòng tiếp theo chứa dãy \(a_1,a_2,...,a_N\) \((-10^9 \le a_i \le 10^9)\), mỗi số cách nhau một khoảng trắng.

Output

• In ra giá trị nhỏ nhất có thể của \(\sum_{i = 1}^{N}(∣b_i∣+∣c_i∣)\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 11\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 -2 3

10

Cho số nguyên dương \(N\) và dãy số nguyên không âm \(x_1,x_2,...,x_N\). Ban đầu tất cả các phần tử trong dãy \(x\) đều bằng \(0\).

Đức có thể dùng hai thao tác sau bao nhiêu lần tùy ý và theo bất kì thứ tự tùy ý:

• Thao tác \(1\): Cho một số nguyên dương \(k\) \((1 \le k \le N)\), tạo dãy số không giảm gồm \(k\) số nguyên không âm \(r_1,r_2,...,r_k\). Với mọi \(1 \le i \le k\) ta sẽ thay \(x_i\) bằng \(x_i + r_i\).
• Thao tác \(2\): Cho một số nguyên dương \(k\) \((1 \le k \le N)\), tạo dãy số không tăng gồm \(k\) số nguyên không âm \(r_1,r_2,...,r_k\). Với mọi \(1 \le i \le k\) ta sẽ thay \(x_{N-k+i}\) bằng \(x_{N-k+i} + r_i\).

Yêu cầu: Cho dãy số nguyên dương có \(N\) số nguyên dương \(a_1,a_2,...,a_N\) được nhập từ bàn phím. Bạn hãy tìm và in ra số lần thao tác ít nhất để dãy \(x\) trùng với dãy \(a\), biết rằng hai dãy \(x\) và \(a\) được gọi là trùng nhau khi với mọi \(1 \le i \le N\) thì \(x_i = a_i\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 2 \times 10^5)\).
• Dòng tiếp theo chứa dãy số \(a_1,a_2,...,a_N\) \((1 \le a_i \le 10^9)\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(1 \le N \le 1000\) và các phần tử trong dãy \(a\) không quá \(5000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 2 1 2 1

3