Luyện tập 23-4-2024-1

Mật hiệu

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 6

Đề bài

Mật hiệu ban đầu của tổ chức AVENGERS là một xâu ~K~ kí tự ~S = S_1 S_2 \dots S_K~ chỉ chứa các kí tự chữ cái Latin thường. Để đảm bảo tính bảo mật của mật hiệu, mật hiệu sẽ được thay đổi mỗi ngày. Giám đốc của AVENGERS mỗi ngày sẽ gửi cho các nhân viên một số nguyên ~X~ với hàm ý: đảo ngược các kí tự trong mật hiệu hiện tại từ kí tự thứ ~X~ đến kí tự thứ ~K - X + 1~ để được mật hiệu mới. (ví dụ mật hiệu hiện tại là 'abcdefgh', và số ~X~ nhận được là 2 thì mật hiệu mới là 'agfedcbh').

Sau ~M~ ngày hoạt động, giám đốc chỉ lưu lại dãy ~M~ con số đã chuyển cho các nhân viên lần lượt là ~X_1, X_2, \dots, X_M~ với suy nghĩ có dãy số này Ông ta sẽ dễ dàng có được mật hiệu của ngày thứ ~M~. Thật không may là số ngày ~M~ quá lớn, Ông mất quá nhiều thời gian để tìm ra mật hiệu đó.

Bạn hãy viết chương trình giúp Ông ta tìm mật hiệu đó.

Input

Dữ liệu vào: cho trong tệp MATHIEU.INP có cấu trúc như sau:

Dòng thứ nhất ghi xâu mật hiệu ban đầu ~S_1 S_2 \dots S_K~ (~2 \leq K \leq 2 \cdot 10^5~)
Dòng thứ hai chứa số ngày ~M~ (~2 \leq K \leq 10^5~)
Dòng tiếp theo chứa dãy ~M~ số ~X_1, X_2, \dots, X_M~ (~1 \leq X_i, 2 \cdot X_i \leq K~ với mọi ~i~ từ 1 đến ~M~)

Output

Dữ liệu ra: ghi vào tệp MATHIEU.OUT xâu mật hiệu hiện tại sau ~M~ ngày.

Ví dụ

Sample Input

abcdefgh
3
2 1 3

Sample Output

hbfedcga

Giới hạn

Thời gian: 2.0s
Bộ nhớ: 256M
Input: mathieu.inp
Output: mathieu.out

Săn bắn

Nộp bài

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 7

Đề bài

Trong thời gian ôn thi vất vả, BigZ nghĩ ra một trò chơi để giải trí cho bản thân và các bạn trong đội tuyển như sau:

Có ~N~ (~1 \leq N \leq 10^6~) con chim đậu thành một hàng. Con thứ ~i~ có sức mạnh là ~a[i]~ (~1 \leq a[i] \leq 10^9~). Những con chim rất đoàn kết, vì vậy khi bạn bắn con chim thứ ~i~, thì 3 con chim ~i - 1~ (nếu ~i > 1~), ~i~, ~i + 1~ (nếu ~i < N~) sẽ hợp sức lại chống trả. Vì vậy bạn mất ~a[i - 1] + a[i] + a[i + 1]~ năng lượng để bắn chết con chim thứ ~i~. Sau đó, các con chim còn lại đứng xích lại gần nhau thành một hàng liền kề.

BigZ luôn bắn con chim có sức mạnh lớn nhất, nếu có nhiều con cùng có sức mạnh lớn nhất, anh ta sẽ bắn con có số thứ tự nhỏ nhất. Cho đến khi lũ chim chết hết anh ta sẽ giàu to. Tuy nhiên anh không mang theo máy tính nên không biết mình sẽ mất bao nhiêu năng lượng. Hãy giúp BigZ!

Input

Dòng 1: Chứa số nguyên dương ~N~.
Dòng 2: Gồm ~N~ số nguyên dương ~a[i]~.

Output

Một dòng duy nhất ghi năng lượng cần dùng.

Ví dụ

Sample Input 1

5
1 2 3 4 5

Sample Output 1

Giới hạn

Thời gian: 2.0s
Bộ nhớ: 256M

Subtasks

Subtask 1: 25% test có ~N \leq 1000~.
Subtask 2: 25% test có ~N \leq 100000~.
Subtask 3: 25% test có ~a[i] \leq 1000000~.
Subtask 4: 25% test còn lại không có giới hạn thêm.

Cặp đôi hoàn hảo

Nộp bài

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 7

Đề bài

XYZ là một công ty lớn trong lĩnh vực công nghệ phần mềm và tới đây họ chuẩn bị thực hiện một dự án lớn có thể thu lại lợi nhuận khổng lồ cho công ty. XYZ gồm ~n~ nhân viên, các nhân viên được đánh số từ ~1~ đến ~n~, nhân viên thứ ~i~ có một chỉ số năng lực dùng bằng ~i~. Tổ chức nhân sự của công ty XYZ có dạng đồ thị cây. Mỗi nhân viên có đúng một cấp trên trực tiếp, có một nhân viên duy nhất là tổng giám đốc, không ai là cấp trên của nhân viên này. Ta gọi nhân viên ~i~ là cấp trên của nhân viên ~j~ nếu nhân viên ~i~ là cấp trên trực tiếp của nhân viên ~j~, hoặc nhân viên ~i~ là cấp trên của nhân viên ~u~ và nhân viên ~u~ là cấp trên trực tiếp của nhân viên ~j~.

Để chuẩn bị tốt việc phân công công việc trong dự án lớn sắp tới, ban lãnh đạo công ty muốn đếm số cặp nhân viên hoàn hảo trong công ty. Hai nhân viên ~i~ và ~j~ là một cặp đôi hoàn hảo nếu họ thỏa mãn hai điều kiện sau:

~i~ là cấp trên của ~j~.
Chênh lệch năng lực giữa hai nhân viên không vượt quá ~k~, tức là ~|i - j| \leq k~.

Yêu cầu: Bạn hãy giúp ban lãnh đạo công ty XYZ đếm số cặp đôi hoàn hảo này.

Input

Dòng đầu tiên chứa 2 số nguyên ~n, k~ (~1 \leq n, k \leq 10^5~).
~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~u, v~ (~1 \leq u, v \leq n~) miêu tả mối quan hệ nhân viên ~u~ là cấp trên trực tiếp của nhân viên ~v~. Dữ liệu đảm bảo các mối quan hệ trong công ty tạo thành một cấu trúc cây.

Output

Ghi ra một dòng duy nhất là kết quả của bài toán.

Ví dụ

Sample Input 1

Sample Output 1

Sample Input 2