Thi thử 16 - 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	Tìm xâu ký tự	100 (p)	1.0s	256M
2	Ghép tranh	100 (p)	1.0s	256M
3	Cách nhiệt	100 (p)	1.0s	256M
4	Chia quà	100 (p)	1.0s	256M

1. Tìm xâu ký tự

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

Trong giờ sinh hoạt của lớp 9A, cô giáo chủ nhiệm chia học sinh lớp 9A thành hai tổ để tổ chức các trò chơi tập thể và bạn An được chia vào tổ $1$. Cô chủ nhiệm cho trước hai chuỗi A, B chứa các chữ cái trong bảng chữ cái tiếng Anh (có cả chữ hoa và chữ thường). Chuỗi A có độ dài $n$, chuỗi B có độ dài $m$. Nếu tổ nào đếm số lần xuất hiện các hoán vị của chuỗi A trong chuỗi B chính xác sẽ chiến thắng.

Bạn hãy giúp An tìm đáp án để chiến thắng trò chơi trên.

Input

Dòng duy nhất chứa hai số nguyên $n$ ($n \leq 1000$) và $m$ ($m \leq 10^6$), $n$ kí tự chuỗi A và $m$ kí tự chuỗi B

Output

Gồm một dòng duy nhất là số lần xuất hiện các hoán vị của chuỗi A trong chuỗi B.

Example

Test 1

Input

4 11
cAda
AbrAcadAbRa

Output

Note

Có 2 lần bắt đầu ở vị trí 4 và 5.

2. Ghép tranh

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

Trò chơi của lớp 9A là trò chơi ghép tranh. Cô chủ nhiệm cho một bức tranh có $N$ mảnh ghép và một số nguyên $K$ ($1 \leq K \leq N \leq 50$). Lần lượt, từng tổ sẽ thay phiên nhau lên ghép tranh với số mảnh ghép mỗi lần không được vượt quá $K$.

An nhận thấy rằng cần phải tìm tất cả các cách ghép tranh khác nhau để chiến thắng trò chơi. Một cách ghép tranh khác nhau nếu tồn tại ít nhất một mảnh ghép được ghép trong một cách nhưng bị bỏ qua ở cách khác.

Xác định số cách ghép tranh khác nhau để An có thể hoàn thành bức tranh.

Input

Gồm một dòng lần lượt là hai số nguyên $N$ và $K$.

Output

Gồm một dòng duy nhất là số cách ghép tranh khác nhau để An có thể hoàn thành bức tranh.

Example

Test 1

Input

4 3

Output

Note

Có tất cả 7 cách ghép tranh:
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1

3. Cách nhiệt

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

Trò chơi thứ ba của lớp 9A là trò chơi xếp các khối hình vuông. Cô chủ nhiệm cho mỗi tổ N ($0 < N ≤ 10^5$) khối hình vuông, các khối hình vuông của tổ 1 giống các khối hình vuông của tổ 2. Trên mỗi khối hình vuông có một số nguyên $a_i$ ($1 \leq i ≤ N, 1 ≤ a_i ≤ 1000$) thể hiện khả năng cách nhiệt của khối hình vuông đó. Nếu xếp lần lượt các khối hình vuông theo trình tự $a_1, a_2,... a_n$, thì độ cách nhiệt của khối là:

$a_1 + a_2 + ... + a_n + max(0, a_2 - a_1) + max(0, a_3 - a_2) + ... + max(0, a_N - a_{N - 1})$

Bạn hãy giúp An xếp các khối hình vuông sao cho độ cách nhiệt của cả khối là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên $n$ (số lượng khối hình vuông).
$n$ dòng tiếp theo, mỗi dòng là các giá trị $a_i$ (Khả năng cách nhiệt của từng khối hình vuông).

Output

Gồm một dòng duy nhất là độ cách nhiệt lớn nhất có thể đạt được.

Example

Test 1

Input

Output

4. Chia quà

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

Để kết thúc buổi sinh hoạt lớp 9A vui vẻ, cô chủ nhiệm đã chuẩn bị N ($N \leq 500000$, $N$ là một số chẵn) phần quà cho hai tổ. Mỗi tổ sẽ dán một giá trị ưa thích (là một số nguyên dương nhỏ hơn hoặc bằng 100) mà mình nghĩ vào phần quà. Sau đó, cô chủ nhiệm chia cho mỗi tổ $\frac{N}{2}$ phần quà sao cho tổng giá trị ưa thích của hai tổ là lớn nhất.

Bạn hãy giúp cô chủ nhiệm tìm tổng giá trị ưa thích lớn nhất của hai tổ theo cách chia quà trên.

Input

Dòng đầu tiên chứa số nguyên $N$ (số lượng phần quà).
$N$ dòng tiếp theo, mỗi dòng gồm 2 số $a_i, b_i$ ($ 1 \leq a_i, b_i \leq 100$) là giá trị ưa thích của 2 tổ.

Output

Gồm một dòng duy nhất là tổng giá trị ưa thích lớn nhất của hai tổ theo cách chia quà trên.

Example

Test 1

Input

Output