XAUCON Xâu con

 Xâu a được gọi là xâu con của xâu b nếu a là một đoạn các kí tự liên tiếp trong b. Ví dụ: ‘aba’ là xâu con của xâu ‘bbaba’, nhưng không là xâu con của xâu ‘aabbaa’.

            Yêu cầu: Cho hai xâu s₁, s₂. Tìm độ dài của xâu con chung ngắn nhất p của s₁ và s₂ với điều kiện p chỉ xuất hiện đúng một lần trong s₁ và đúng một lần trong s₂.

Input:

·        Dòng đầu ghi xâu s₁

·        Dòng thứ hai ghi xâu s₂

Mỗi xâu dài không quá 5000 kí tự chỉ gồm các chữ cái ‘a’…’z’.

Output: ghi độ dài của xâu con chung ngắn nhất p. Nếu không tồn tại p xuất – 1.

Input	Output
abcabc cabbcab	3

TRIP455 Chuyến đi

TRIP455 Chuyến đi

Giáo sư X tổ chức cho 𝑛 học sinh của mình đi làm tình nguyện tại hành tinh Alpha. Các học sinh được đánh số từ 1 tới 𝑛, mỗi học sinh sẽ tới trường và lên tàu vũ trụ bay tới hành tinh Alpha.

Số lượng tàu cũng như số lượng học sinh lên mỗi tàu là không hạn chế, tuy nhiên vì việc phóng tàu vũ trụ khá phức tạp nên hai lần phóng tàu liên tiếp phải cách nhau đúng Δ giây.

Khi một con tàu được phóng, tất cả các học sinh đã đến trường trước hoặc bằng thời điểm phóng tàu sẽ lên tàu và đi luôn. Những học sinh đến sau thời điểm phóng tàu sẽ phải đợi chuyến tàu kế tiếp (cách Δ giây so với chuyến tàu vừa phóng).

Yêu cầu: Cho biết thời điểm mỗi học sinh đến trường, hãy giúp giáo sư X xác định thời điểm phóng con tàu đầu tiên để tổng thời gian chờ đợi của các học sinh là nhỏ nhất.

Input

·        Dòng 1 chứa hai số nguyên dương 𝑛, Δ cách nhau bởi dấu cách (𝑛 ≤ 10⁵; Δ ≤ 10⁹)

·        Dòng 2 chứa 𝑛 số nguyên cách nhau bởi dấu cách lần lượt là thời điểm 𝑛 học sinh tới trường, các thời điểm này là số nguyên không âm và không quá 10⁹ .

Output: một số nguyên duy nhất là tổng thời gian chờ đợi (tính bằng giây) của 𝑛 học sinh.

Input	Output
5 4 9 3 7 6 11	3

Giải thích phương án tối ưu: Tàu đầu tiên phóng vào thời điểm 3, dãy các thời điểm phóng tàu là 3, 7, 11, 15, ….

·        HS 1 đợi 2 giây lên chuyến 3.

·        HS 2 đợi 0 giây lên chuyến 1

·        HS 3 đợi 0 giây lên chuyến 2

·        HS 4 đợi 1 giây lên chuyến 2

HS 5 đợi 0 giây lên chuyến 3