THT Bảng C Đà Nẵng 2022

Hai xâu được gọi là song sinh nếu như chúng được tạo ra từ cùng một bộ kí tự giống nhau và số
lượng từng loại kí tự trong xâu bằng nhau.
Ví dụ: “tinhoc” và “hoctin” là hai xâu song sinh, “laptrinh” và “laplaptrinh” không phải là hai xâu
song sinh.
Yêu cầu: Cho trước các cặp xâu kí tự chỉ bao gồm các chữ cái viết thường, hãy xác định xem mỗi
cặp xâu có phải là cặp xâu song sinh hay không.

Input

• Đọc từ file văn bản TWINS.INP gồm \(t (t \le 100)\) bộ test, mỗi bộ test gồm hai dòng ghi hai xâu cần kiểm tra chỉ bao gồm các kí tự biết thường và không quá 255 kí tự.

Output

• Ghi ra file văn bản TWINS.OUT tương ứng với mỗi bộ test ghi ra twins nếu là xâu song
  sinh, ngược lại ghi not twins.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Các cặp xâu chỉ có hai kì tự là \(a\) và \(b\).
• Subtask \(2\) (\(50\%\) số điểm): Không ràng buộc gì thêm.

Example

3
tinhoc
hoctin
abc
aabbbcccc
abcabcbcc
aabbbcccc

twins
not twins
twins

Có \(n\) công trình nằm cạnh nhau trên một con đường. Công trình thứ \(i\) có chiều cao là \(A_i\)
. Thành phố
muốn quy hoạch lại con đường sao cho các công trình phải có chiều cao không giảm từ trái sang
phải. Thành phố quyết định sẽ phá bỏ một số công trình để đạt được điều này. Để tiết kiệm chi phí,
số công trình bị phá bỏ phải ít nhất, nếu có nhiều cách phá bỏ, chọn cách có tổng chiều cao nhỏ
nhất.

Input

• Dòng đầu tiên là số nguyên \(n\) - số lượng công trình
• Dòng thứ hai là \(n\) số nguyên \(A_i\) - chiều cao của công trình thứ \(i\)

Output

• Gồm một số nguyên duy nhất là tổng chiều cao của số công trình bị phá bỏ thỏa mãn yêu cầu trên.

Constants

• \(1 \le n \le 10^3\)
• \(1 \le A_i \le 10^9\)

Example

5
1 11 3 11 5 

8

Hôm nay, thầy Mười chính thức trở thành giáo viên chủ nhiệm mới của lớp 11A. Biết được rằng có sự chia rẽ nội bộ trong lớp học, thầy Mười quyết định tổ chức một trò chơi để tăng tính đoàn kết của các bạn trong lớp. Thầy đặt tên trò chơi này là “trò chơi chuyền kẹo”.

Lớp 11A có \(n\) học sinh, được đánh số từ \(1\) đến \(n\). Thầy xếp các học sinh này ngồi thành một vòng tròn, học sinh thứ \(i + 1\) ngồi bên phải học sinh thứ \(i\) và học sinh thứ \(1\) ngồi bên phải học sinh thứ \(n\). Sau đó, thầy phát mỗi học sinh một số viên kẹo, học sinh thứ \(i\) sẽ được phát \(a[i]\) viên. Mục tiêu của trò chơi là các bạn học sinh phải chuyền kẹo qua lại sao cho mỗi bạn thứ \(i\) sẽ nhận được đúng \(b[i]\) viên.

Ở mỗi lượt, cả lớp sẽ thống nhất chọn \(1\) bạn. Bạn học sinh này có thể chuyền \(1\) viên kẹo sang người ngồi bên cạnh mình (bên trái hoặc phải). Tuy nhiên, trong lớp lại có \(k\) cặp bạn tuy ngồi cạnh nhau nhưng lại không ưa nhau. Các cặp bạn này khi \(1\) bạn được chọn sẽ nhất quyết không chuyền kẹo qua cho người kia. Nếu cả 2 bạn bên cạnh đều không chuyền được, thì sẽ không chuyền cho ai cả.

Thầy Mười biết được điều này, nên thầy sẽ chia số kẹo ban đầu sao cho dữ kiện bạn thứ \(i\) nhận được đúng \(b[i]\) viên kẹo luôn được đảm bảo.

Thầy Mười muốn đánh giá tính đoàn kết của cả lớp, nên trước đó thầy muốn tính được số bước ít nhất để thực hiện việc chuyền kẹo. Bạn hãy giúp thầy tính số bước ít nhất này nhé.

Input

• Dòng đầu chứa 2 số nguyên \(n, k (0 \le k \le n \le 10^5)\)
• Dòng thứ 2 chứa \(n\) số nguyên \(a[i] (0 \le a[i] \le 10^6)\), là số kẹo ban đầu của học sinh thứ \(i\)
• Dòng thứ 3 chứa \(n\) số nguyên \(b[i] (0 \le b[i] \le 10^6)\), là số kẹo học sinh thứ i cần được nhận
• Dòng thứ 4 chứa \(k\) số nguyên \(x[i] (1 \le x[i] \le n)\), là vị trí bên trái của cặp bạn thứ \(i\).
• Dữ liệu đảm bảo \(x[1] < x[2] < ... < x[k]\)

Output

• Số bước ít nhất cần tìm thỏa mãn yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(2 \le n \le 300, 0 \le a[i] \le 300\)
• Subtask \(2\) (\(30\%\) số điểm): \(2 \le n \le 3000, 0 \le a[i] \le 10^6\)
• Subtask \(3\) (\(40\%\) số điểm): không có dữ kiện gì thêm

Example

3 1
3 8 0
4 5 2
2

5

3 1
3 8 0
4 5 2
2

Để động viên các bạn học sinh trong lớp học VUI NHỘN nhân dịp lớp đoạt chức vô địch
giải bóng đá cấp trường vừa qua, cô Mười Ba dự định sẽ mua tặng các học sinh của mình những
chiếc áo LV mới nhất.

Lớp học VUI NHỘN có \(n\) học sinh. Cửa hàng cô dự định đến có bán \(k\) màu áo khác nhau.
Cô Mười Ba muốn mua \(n\) chiếc áo cho \(n\) học sinh của mình, đồng thời cô cũng muốn với mỗi màu
áo từ \(1\) đến \(k\), sẽ có ít nhất \(m\) bạn mặc chiếc áo có màu này.

Ông chủ cửa hàng rất thích toán, vì vậy ông đố cô rằng có bao nhiêu cách mua áo khác nhau,
sao cho cô sẽ mua \(n\) chiếc áo, và với mỗi màu áo từ \(1\) đến \(k\) xuất hiện ít nhất \(m\) lần trong \(n\) chiếc áo.
Vì bận tính tiền nên cô không thể tập trung giải quyết bài toán, bạn hãy giúp cô giải bài này để được
giảm giá nhé.

Input

• Một dòng chứa 3 số nguyên dương \(n, k, m (1 \le k \le n, m ∗ k \le n \le 10^6 , 1 \le m \le 2)\)

Output

• Số cách chia thỏa mãn yêu cầu đề bài sau khi mod \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 10, k \le 5\)
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100, k \le 10\)
• Subtask \(3\) (\(20\%\) số điểm): $n \le 3000, k \le $
• Subtask \(4\) (\(10\%\) số điểm): \(n \le m ∗ k + 1\)
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^6, k \le 10^6, m = 1\)
• Subtask \(6\) (\(20\%\) số điểm): \(n \le 10^6, k \le 3000, m = 2\)

Example

3 2 1

6

4 2 2

6