Nguồn đề: [Freecontest] https://drive.google.com/drive/folders/1A2njPndxtO_yWkPjwnCjJkYJmT0NBnUq

*Lời giải: * https://drive.google.com/file/d/1NLdbkjsWj3viGpmnPlaj-VilrFjx0akz/view?usp=sharing

Một số nguyên dương x được gọi là đẹp, nếu có thể biểu diễn x thành tổng các số chẵn. Nói cách khác, tồn tại một dãy số ~a_1, a_2, .., a_k~ sao cho:

• Với mọi ~1 \leq i \leq k~, ~a_i~ là số chẵn.
• ~a_1 + a_2 + ... + a_k = x~

Cho số nguyên dương n, hãy cho biết n có phải số đẹp hay không.

Input

Dòng 1: Một số nguyên dương n ~(1 ≤ n ≤ 10^2).~

Kết quả

Nếu n là số đẹp, in ra 'YES'. Ngược lại, in ra 'NO'

Sample Input 1

12

Sample Output 1

YES

Sample Input 2

100

Sample Output 2

YES

Sample Input 3

1

Sample Output 3

NO

Nguồn đề: [Freecontest] https://drive.google.com/drive/folders/1uKg2pAWKYfTb77mF8GclbaBb3HTiHT

*Lời giải: * https://drive.google.com/file/d/1imDygPrrGvQKudqPNFx5MZvaz3E9iSbV/view?usp=sharing

*Solution: * https://drive.google.com/file/d/1y1ssS3wdr5n_Nge95I4plChV7Kv0V252/view?usp=sharing

Bi là một học sinh giỏi trong lớp. Sắp tới, Bi phải thi để nhận chứng chỉ cho M môn học trong vòng N ngày. Mỗi môn học được đánh số từ 1 đến M và để nhận được chứng chỉ thứ i thì cần bỏ ra ~t_i~ ngày để ôn tập và các ngày ôn tập không cần liên tiếp. Một ngày Bi có thể tham gia thi, ôn tập hoặc nghỉ ngơi.

Bạn được biết lịch tổ chức các kì thi của M môn học sắp tới trong vòng N ngày. Hãy giúp Bi lên lịch sao cho số ngày cần là ít nhất để có thể lấy được M chứng chỉ.

Input

Dòng 1: Gồm 2 số nguyên N, M ~( 1 \leq N, M \leq 10^5)~

Dòng 2: Gồm N số nguyên ~X_1, X_2, .., X_N~ với ~X_i (0 \leq X_i \leq M)~ thể hiện cho ngày thứ i có kì thi để lấy chứng chỉ ~X_i~. Nếu ~X_i=0~ thì ngày đó không có kì thi nào được tổ chức.

Dòng 3: Gồm M số nguyên ~t_1, t_2, .., t_M~ với ~t_i (1 \leq t_i \leq 10^5)~ là số ngày cần ôn tập để lấy được chứng chỉ thứ i.

Kết quả

Gồm 1 số duy nhất là số ngày ít nhất để Bi có thể nhận được tất các các chứng chỉ.

Nếu không thể lấy trong vòng N ngày thì xuất -1.

Sample Input 1

9 2
1 1 2 0 1 2 1 1 2
2 1

Sample Output 1

5

Giải thích

• Bi sẽ ôn tập ngày 1 cho môn thứ 2 và thi nó vào ngày thứ 3.

• Bi sẽ ôn tập ngày 2 và 4 cho môn thứ 1 và thi nó vào ngày thứ 5.

*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/14mUwz9rvb78k4IL-GTDSkNR7PSbS4xPq/view

*Lời giải: * https://drive.google.com/file/d/1ACRIlL6TB5QrfL3eMzycZG9Ww33kVKcY/view

Cân bằng của một mảng được định nghĩa là số cặp chỉ số (i,j) (i < j) với giá trị bằng nhau ~(a_i = a_j)~. Ví dụ cân bằng của mảng a = [1,1,2,2,1] là 4. Số cặp chỉ số với giá trị bằng nhau là (1,2), (1,5), (2,5) và (3,4).

Cho một mảng a có n phần tử, in ra tổng cân bằng của tất cả các mảng con của a.

Một mảng b được định nghĩa là mảng con của mảng a nếu ta có thể thu được mảng b sau khi xóa một vài phần tử (có thể là không hoặc tất cả phần tử) ở đầu và cuối của mảng a.

Input

• Dòng đầu tiên gồm một số nguyên T số test ~(1 \leq T \leq 100)~
• Dòng đầu tiên của mỗi test chứa số n ~(1 \leq n \leq 10^{4} )~
• Dòng thứ hai chứa n số lần lượt là phần tử trong mảng a : ~a_1, a_2, a_3, ... , a_n (1 \leq a_i \leq 10^9)~

Output

• Với mỗi test, in ra một số là tổng cân bằng của tất cả mảng con của a

Sample Input 1

2 
4
1 2 1 1
4
1 2 3 4

Sample Output 1

6
0

Giải thích

• Test 1 : [1,2] cân bằng là 0, [1,1] cân bằng là 1, [1,2,1] cân bằng là 1, [2,1,1] cân bằng là 1, [1,2,1,1] cân bằng là 3. Đáp án là 6.

Nguồn đề: ICPC Miền Trung 2021 https://oj.vnoi.info/problem/icpc21mtn

Cho bạn 2 chuỗi kí tự S và T, hãy tìm chuỗi kí tự X có thứ tự từ điển nhỏ nhất thỏa mãn hai điều kiện sau:

• X là chuỗi con S.
• X là hoán vị của T.

A được gọi là chuỗi con của B, nếu có thể có được A bằng cách xóa đi một vài kí tự(có thể không xóa) của B.

Input

Dòng 1: Chuỗi kí tự S ~( 1 \leq |S| \leq 10^{5} )~

Dòng 2: Chuỗi kí tự T ~( 1 \leq |T| \leq 10^{3} )~

Cả hai chuỗi kí tự S và T chỉ chứa các chữ cái thường ('a'-'z')

Kết quả

In ra chuỗi X có thứ tự từ điển nhỏ nhất thỏa mãn hai điều kiện trên.

Nếu không tồn tại chuỗi X in ra -1

Sample Input 1

bcadca
dacb

Sample Output 1

badc

Sample Input 2

uuuuuu
uzt

Sample Output 2

-1

Nguồn đề: https://codeforces.com/contest/1391/problem/C

Một hoán vị có độ dài n là một mảng gồm n số nguyên phân biệt từ 1 đến n có thứ tự bất kì.

Xem xét một hoán vị p độ dài n, chúng ta sẽ xây dựng một đồ thị có n đỉnh bằng hai chuỗi thao tác sau:

• Với mỗi i ~( 1 \leq i \leq n)~, tìm j lớn nhất sao cho ~ 1 \leq j < i~ và ~ p_j > p_i ~, ta thêm 1 cạnh vô hướng giữa đỉnh i và đỉnh j.

• Với mỗi i ~( 1 \leq i \leq n)~, tìm j bé nhất sao cho ~ i < j \leq n~ và ~ p_j > p_i ~, ta thêm 1 cạnh vô hướng giữa đỉnh i và đỉnh j.

Trong trường hợp không tồn tại j, chúng ta không thêm cạnh.

Ví dụ: n = 4, p = [3, 1, 4, 2], các cạnh đồ thị ta thêm là (1,3), (2,1), (2,3), (4,3).

Một hoán vị được gọi là đẹp nếu, từ hoán vị đó ta xây dựng được một đồ thị có ít nhất một chu trình đơn giản - simple cycle.

Cho n hãy tìm số lượng các hoán vị đẹp có độ dài n. Kết quả có thể rất lớn hãy chia dư cho ~10^9 + 7~.

Input

Dòng 1: Chứa một số nguyên n ~(3 \leq n \leq 10^6)~

Kết quả

In ra số lượng các hoán vị đẹp có độ dài n, chia dư cho ~10^9 + 7~

Sample Input 1

4

Sample Output 1

16

Sample Input 2

583291

Sample Output 2

135712853

Giải thích

Có 16 hoán vị đẹp có độ dài bằng 4. Ví dụ một trong số đó là [4, 2, 1, 3], có một chu trình độ dài 4: 4 -> 3 -> 2 -> 1 -> 4

Các đỉnh ~v_1, v_2, ..., v_k~ tạo thành một chu trình đơn giản nếu thỏa mãn các điều kiện sau:

• ~ k \ge 3~
• ~v_i \ne v_j ~ với mọi cặp i,j. ~ 1 \leq i < j \leq k~
• Có một cạnh giữa ~v_i ~ và ~ v_{i+1} ~ với mọi ~ 1 <= i < k~
• Có một cạnh giữa ~v_1 ~ và ~ v_k ~.

Nguồn đề: HackerEarth https://www.hackerearth.com/problem/algorithm/abcd-strings/description/

Đếm số xâu có độ dài là N, chỉ chứa các kí tự 'a', 'b', 'c', 'd' và không chứa các xâu đặc biệt.

Đáp án có thể rất lớn, hãy chia dư cho 1000000007.

Input

• Dòng đầu tiên chứa T, số testcase. ~( 1 \leq T \leq 200 )~
• Dòng thứ 2 chứa N độ dài của xâu, K số lượng các xâu đặc biệt ~( 1 \leq N \leq 10^{15}, 1 \leq K \leq 50 )~ .
• K dòng tiếp theo mỗi dòng chữa một xâu đặc biệt S. ~( 1 \leq len(S) \leq 3,~ S cũng chỉ chứa các kí tự 'a', 'b', 'c', 'd' )

Output

• Với mỗi testcase, In ra kết quả cần tìm.

Test

• 20đ : ~( 1 \leq N \le 10 )~
• 80đ : ~( 1 \leq N \leq 10^{15} )~

Sample input 1

5
4 8
cac
dbb
abb
ddd
dad
aaa
dbb
cad
3 1
aca
2 7
abb
aac
aab
dcc
bbc
caa
cba
1 4
cbb
ddd
ccb
cdc
5 5
aad
bda
aac
ddb
bdc

Sample output 1

202
63
16
4
789