Cho dãy gồm tám số nguyên là một hoán vị của tập {1; 2; 3; 4; 5; 6; 7; 8}.
Hãy xác định xem dãy đã cho là đơn điệu tăng, đơn điệu giảm hay không đơn điệu.

Dữ liệu

• Một dòng gồm 8 số nguyên dương là một hoán vị của tập {1; 2; 3; 4; 5; 6; 7; 8}.

Kết quả

Ghi ra một dòng:

• "ascending" nếu dãy đơn điệu tăng;
• "descending" nếu dãy đơn điệu giảm;
• "mixed" nếu dãy không đơn điệu.

Ví dụ

Ràng buộc

• Subtask 1: 25% điểm, số thứ i (1 ≤ i ≤ 8) có giá trị đúng bằng i;
• Subtask 2: 25% điểm, số thứ i (1 ≤ i ≤ 8) có giá trị bằng 8 - i + 1;
• Subtask 3: 50% điểm còn lại không có thêm ràng buộc bổ sung.

Cho ba số nguyên dương L, R, k.
Hãy đếm số lượng các số nguyên tố trong đoạn [L, R] mà có tổng chữ số chia hết cho k.

Dữ liệu

• Một dòng chứa ba số nguyên dương L R k
  (1 ≤ L ≤ R ≤ 10⁷, 1 ≤ k ≤ 100).

Kết quả

• Ghi ra một số nguyên là kết quả tìm được.

Ví dụ

Ràng buộc

• Subtask 1: 35% điểm, 1 ≤ L, R ≤ 10;
• Subtask 2: 20% điểm, 1 ≤ L ≤ R ≤ 100;
• Subtask 3: 45% điểm còn lại không có thêm ràng buộc bổ sung.

Cho xâu S chỉ chứa các ký tự chữ cái tiếng Anh viết thường.
Một xâu con của S là một dãy các ký tự liên tiếp trong xâu S.

Ví dụ: "cd" là xâu con của "abcde" còn "ac" thì không.

Hãy tính độ dài xâu con dài nhất mà xuất hiện ít nhất hai lần trong S.

Dữ liệu

• Dòng 1: số nguyên N (1 ≤ N ≤ 200 000) – độ dài xâu S;
• Dòng 2: gồm N chữ cái tiếng Anh viết thường mô tả xâu S.

Kết quả

• Ghi ra một số nguyên là độ dài xâu con dài nhất xuất hiện ít nhất hai lần trong S;
• Nếu không có xâu con nào thỏa mãn, in ra 0.

Ví dụ

Ràng buộc

• Subtask 1: 20% điểm, N ≤ 3;
• Subtask 2: 60% điểm, N ≤ 200;
• Subtask 3: 20% điểm còn lại không có thêm ràng buộc bổ sung.

Bạn An lên kế hoạch đi ăn vặt ở phố đi bộ. Trên phố đi bộ đó có R cửa hàng bán đồ ăn vặt.

Nếu An ghé thăm cửa hàng thứ i (1 ≤ i ≤ R) thì:

• Mức độ vui vẻ tăng thêm Vᵢ;
• Tốn thêm Tᵢ phút để ăn;
• Ăn được thêm Fᵢ đơn vị thức ăn.

An muốn chọn ghé thăm một số cửa hàng sao cho:

• Tổng thời gian ăn không quá M phút;
• Tổng lượng thức ăn không quá U đơn vị;
• Mỗi cửa hàng chỉ được ghé thăm không quá một lần.

Hãy giúp An chọn tập cửa hàng để ghé thăm sao cho tổng mức độ vui vẻ là lớn nhất.

Dữ liệu

• Dòng 1: ba số nguyên M U R
  (1 ≤ M ≤ 300, 1 ≤ U ≤ 100, 1 ≤ R ≤ 150);
• R dòng tiếp theo, mỗi dòng gồm ba số nguyên Vᵢ Tᵢ Fᵢ.

Kết quả

• Ghi ra một số nguyên duy nhất là tổng mức độ vui vẻ lớn nhất có thể đạt được.

Ví dụ

Ràng buộc

• Subtask 1: 35% điểm, 1 ≤ M ≤ 100, 1 ≤ U ≤ 55, 1 ≤ R ≤ 12;
• Subtask 2: 30% điểm, 1 ≤ M ≤ 240, 1 ≤ U ≤ 75, 1 ≤ R ≤ 50;
• Subtask 3: 35% điểm còn lại không có thêm ràng buộc bổ sung.