Trong một buổi học toán, giáo viên viết 2 số nguyên A và B và yêu cầu Tý thực hiện phép cộng. Tý không bao giờ tính toán sai nhưng thỉnh thoảng cậu ta chép các con số một cách không chính xác. Lỗi duy nhất của Tý là ghi nhầm '5' thành '6' hoặc ngược lại.

Cho hai số, A và B, tính tổng lớn nhất và nhỏ nhất mà Tý có thể nhận được nếu bị nhầm.

Input Format: 1 dòng duy nhất chứa 2 số A và B

Ràng buộc: ~1 \leq A \leq B \leq 10^6~

Input 01:

35 36

Output 01:

72 70

Input 02:

891 746

Output 02:

1637 1636

Tại ngân hàng có các mệnh giá băng 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000. Tổng số tiền cần đổi có giá trị bằng N. Hãy xác định xem có ít nhất bao nhiêu tờ tiền sau khi đổi tiền?

Dòng duy nhất chứa số nguyên N

Ràng buộc: 1<=N<=10^9

Đầu ra: In ra số tờ tiền tối thiểu

Input:

138

Output:

6

Cho mảng A gồm N phần tử, nhiệm vụ của bạn là sắp đặt lại vị trí các phần tử trong mảng và tính toán giá trị lớn nhất của biểu thức:

Đầu vào: Dòng 1 chứa số nguyên dương N; Dòng 2 chứa N số nguyên của mảng A[] viết cách nhau một dấu cách

Ràng buộc: 1<=N<=10^6; 1<=A[i]<=10^9;

Đầu ra: In ra kết quả của bài toán chia dư với 10^9 + 7

Input:

6
8 1 7 9 8 1

Output:

150

Cho mảng A[] gồm N số nguyên không âm và số K. Nhiệm vụ của bạn là hãy chia mảng A[] thành hai mảng con có kích cỡ K và N-K sao cho hiệu giữa tổng hai mảng con là lớn nhất. Ví dụ với mảng A[] = {8, 4, 5, 2, 10}, K=2 ta có kết quả là 17 vì mảng A[] được chia thành hai mảng {4, 2} và { 8, 5, 10} có hiệu của hai mảng con là 23-6=17 là lớn nhất.

Đầu vào: Dòng duy nhất chứa 2 số nguyên N và K; Dòng thứ 2 gồm N số của mảng A[]

Ràng buộc: 1<=K<=N<=10^6; 0<=A[i]<=10^9;

Đầu ra: In ra đáp án của bài toán

Input:

6 4
3 10 10 7 5 2

Output:

27

Cho mảng A[] gồm N số, hãy thực hiện các thao tác theo nguyên tắc dưới đây:

1. Ta chọn một mảng con sao cho phần tử ở giữa của mảng con cũng là phần tử ở giữa của mảng A[] (trong trường hợp N lẻ).

2. Đảo ngược mảng con đã chọn trong mảng A[]. Ta được phép chọn mảng con và phép đảo ngược mảng con bao nhiêu lần tùy ý.

Hãy cho biết ta có thể sắp xếp được mảng A[] bằng cách thực hiện các thao tác kể trên hay không?

Ví dụ với mảng A[] = (1, 6, 3, 4, 5, 2, 7} ta có câu trả lời là YES vì: ta chọn mảng con {3, 4, 5) và đảo ngược để nhận được mảng All=(1, 6, 5, 4, 3, 2, 7}, chọn tiếp mảng con {6, 5, 4, 3, 2} và đảo ngược ta nhận được mảng A[]=(1, 2, 3, 4, 5, 6, 7}.

Đầu vào:

Dòng 1 chứa số nguyên dương N là số lẻ.

Dòng 2 chứa N số nguyên của mảng A[]

Ràng buộc: 1 <= N <= 10^6; 0 <= A[i] <= 10^9

Đầu ra: In ra YES hoặc NO là đáp án của bài toán

Input 01:

5
1 4 3 2 5

Output 01:

YES

Input 02:

5
1 3 8 7 3

Output 02:

NO

Cho mảng A[], B[] đều có N phần tử. Nhiệm vụ cúa bạn là tìm giá trị lớn nhất của biểu thức P= A[0]B[0] + A[1]B[1] + ..+A[N-1]*B[N-1] bằng cách tráo đổi vị trí các phần tử của cả mảng A[] và B[].

Đầu vào: Dòng 1 chứa số nguyên dương N; Dòng 2 chứa N số nguyên của mảng A[]; Dòng 3 chứa N số nguyên của mảng B[]

Ràng buộc: 1 <= N＜= 10^5; 0 <= A[i], B[i] <= 10^6

Đầu ra: In ra đáp án của bài toán

Input:

7
9 4 5 3 9 4 10
9 5 3 1 10 1 5

Output:

270

Hoàng yêu thích các số may mắn. Ta biết rằng một số là số may mắn nếu biểu diễn thập phân của nó chỉ chứa các chữ số may mắn là 4 và 7. Ví dụ, các số 47, 744, 4 là số may mắn và 5, 17, 467 không phải. Hoàng muốn tìm số may mắn bé nhất có tổng các chữ số bằng n. Hãy giúp anh ấy.

Đầu vào: Dòng duy nhất chứa số nguyên dương n

Ràng buộc: 1<=n<=10^6;

Đầu ra: In ra đáp án của bài toán, nếu không tồn tại đáp án thì in ra -1

Input:

16

Output:

4444

Cho xâu kí tự chỉ bao gồm các kí tự in thường, hãy kiểm tra xem có thể sắp đặt lại các kí tự trong xâu sao cho không có 2 kí tự kề nhau nào giống nhau hay không?

Đầu vào: Dòng duy nhất chứa xâu S

Ràng buộc: 1<=len(S)<=10000;

Đầu ra: Nếu có thể sắp đặt lại xâu kí tự in ra YES, ngược lại in ra NO.

Input:

aqeaaqwq

Output:

YES

Cho hai số nguyên dương S và D, trong đó S là tổng các chữ số và D là số lượng các chữ số của một số. Nhiệm vụ của bạn là tìm số nhỏ nhất thỏa mãn S và D?

Đầu vào: 1 dòng gồm 2 số S, D

Ràng buộc: 1<=S,D<=1000;

Đầu ra: In ra số nhỏ nhất có D chữ số và có tổng bằng S, nếu không tìm được đáp án thì in ra -1

Input:

12 8

Output:

10000029

Cho dãy số A gồm N phần tử là các số nguyên. Hãy tính tích lớn nhất của 2 hoặc 3 phần tử trong dãy.

Đầu vào: Dòng đầu tiên là N; Dòng thứ 2 là N phần tử của mảng A

Ràng buộc: 1<=N<=1000; 0<=abs(A[i])<=10^6

Đầu ra: In ra tích lớn nhất của 2 hoặc 3 phần tử trong mảng

Input:

5
-9 4 3 -3 1

Output:

108

Trong một cuộc thi lập trình đồng đội, có N nam và N nữ. Sức mạnh code của nam thứ i là Ai, của nữ thứ i là Bi. Cần ghép mỗi bạn nam với một bạn nữ thành 1 đội. Độ chênh lệch của đội được tính bằng Ai * Bi. Ban tổ chức muốn tổng độ chênh lệch của tất cả N đội là nhỏ nhất có thể để giải đấu cân bằng.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên mảng A (1 <= A_i <= 10^5).

Dòng 3: N số nguyên mảng B (1 <= B_i <= 10^5).

Kết quả ra: Tổng độ chênh lệch nhỏ nhất.

Ví dụ:

Input:

3
3 1 1
6 5 4

Output:

23

(Ghép: 34 + 15 + 16)

Trong Hội xuân tại Thái Nguyên, Ban tổ chức có các mệnh giá tiền thưởng: 1, 2, 5, 10, 20, 50, 100, 200, 500 (đơn vị nghìn đồng). Một học sinh trúng thưởng số tiền là N nghìn đồng. Ban tổ chức muốn trao thưởng cho học sinh này bằng số lượng tờ tiền ít nhất có thể. Hãy tính số tờ tiền ít nhất cần dùng.

Dữ liệu vào: Số nguyên dương N (1 <= N <= 10^9).

Kết quả ra: Số lượng tờ tiền ít nhất.Ví dụ:

Input:

845

Output:

6

(Giải thích: 1 tờ 500, 1 tờ 200, 1 tờ 100, 2 tờ 20, 1 tờ 5).

Có N bục đá xếp thành hàng ngang, đánh số từ 0 đến N-1. Bục thứ i có ghi số Ai, nghĩa là từ bục này, con ếch có thể nhảy tiến lên phía trước tối đa Ai bước. Ếch đang ở bục 0, hỏi cần ít nhất bao nhiêu lần nhảy để ếch đến được bục N-1? Dữ liệu đảm bảo luôn có cách đi tới đích.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Ai (0 <= Ai <= 10^5).

Kết quả ra: Số lần nhảy ít nhất.

Ví dụ:

Input:

5
2 3 1 1 4

Output:

2

(Nhảy từ 0 đến 1 (1 bước), nhảy từ 1 đến 4 (3 bước)).

Cho số tự nhiên m và số nguyên s không âm. Nhiệm vụ của bạn là tìm số lớn nhất và nhỏ nhất có m chữ số và tổng chữ số bằng s.

Ràng buộc: 1 ≤ m ≤ 100: 0 ≤ s ≤ 900

In ra số lớn nhất, nhỏ nhất có thể đạt được, mỗi số in ra trên 1 dòng. Nếu không có đáp án thì in ra 1 dòng "NOT FOUND".

Input:

2 15

Output:

96
69