Cho 3 số nguyên dương n, a, b.

Yêu cầu: Đếm số các số nguyên dương nhỏ hơn hoặc bằng n mà chia hết cho cả a và b.

Dữ liệu: Vào từ tệp văn bản CAU1.INP gồm một dòng duy nhất chứa ba số nguyên dương n, a, b (n, a, b ≤ 10^18).

Kết quả: Ghi ra tệp văn bản CAU1.OUT một số duy nhất là kết quả tìm được.

Ví dụ:

    CAU1.INP
        20 2 5
    CAU1.OUT
        2

Cho dãy A gồm n số nguyên a1, a2, ..., an khác nhau đôi một.

Yêu cầu: Chia dãy A thành ít nhất các dãy con (có thể không liên tiếp) sao cho:

• Mỗi phần tử của dãy A thuộc một và chỉ một dãy con.
• Mỗi dãy con có thể có một phần tử hoặc nếu nhiều hơn một thì khi giữ nguyên trật tự như ở dãy ban đầu sẽ cho ta một dãy số tăng dần.

• Nếu hai số ai, aj bất kì (1 ≤ i < j ≤ n) thuộc cùng một dãy con thì mọi số ak (k=1..n) mà ai < ak < aj cũng thuộc dãy con đó.

  Dữ liệu: Vào từ tệp văn bản CAU2.INP gồm:

• Dòng đầu chứa số nguyên dương n (n ≤ 10^5);

• Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (ai ≤ 109 với mọi i = 1..n).

  Kết quả: Ghi ra tệp văn bản CAU2.OUT một số nguyên duy nhất là số dãy con ít nhất tìm được.

Ví dụ:

CAU2.INP
    5
    2 4 1 5 3
CAU2.OUT    
    3
Mô tả
    Các dãy con lần lượt là: 
    Dãy 1: 1
    Dãy 2: 4, 5
    Dãy 3: 2, 3

Ràng buộc:

• Có 40% số điểm có n ≤ 103 và ai ≤ n với mọi i = 1..n;
• Có 40% số điểm tiếp theo có n ≤ 10^5 và ai ≤ n với mọi i = 1..n;
• Có 20% số điểm còn lại không có ràng buộc gì thêm.

Một tài liệu sau khi mã hóa thành một xâu kí tự S có độ dài m bao gồm các chữ cái tiếng Anh sẽ được gửi đi kèm theo với mật mã là một xâu kí tự T có độ dài n cũng gồm các chữ cái tiếng Anh. Do đường truyền không ổn định nên khi gửi tài liệu, có thể một số kí tự của xâu S bị thay bằng kí tự *. Quá trình giải mã, người ta xét tất cả các xâu con liên tiếp độ dài n của S, gọi là: P0, P1, ..Pm-n.

Yêu cầu: Tính số các xâu Pi (i=0..m-n) có thể là hoán vị của xâu T, nếu trong xâu Pi có chứa các kí tự * thì được phép thay mỗi kí tự * đó thành chữ cái tiếng Anh bất kì.

Dữ liệu: Vào từ tệp văn bản CAU3.INP gồm:

• Dòng đầu chứa hai số nguyên dương n, m (n ≤ 3.10^3, m ≤ 3.10^6);
• Dòng thứ hai chứa xâu kí tự T;
• Dòng thứ ba chứa xâu kí tự S.

  Kết quả: Ghi ra tệp văn CAU3.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

CAU3.INP
    3 12
    aab
    abcnbaabfkjd
CAU3.OUT
    2
CAU3.INP
    3 4
    abc
    a**c
CAU3.OUT
    2

Ràng buộc:

• Có 40% số điểm có: độ dài xâu S không quá 1000 và xâu S không chứa kí tự *;
• Có 40% số điểm tiếp theo có: xâu S không chứa kí tự *;
• Có 20% số điểm còn lại không có ràng buộc gì thêm.

Sàn một nhà thi đấu là một hình chữ nhật kích thước 𝑚 × 𝑛 được chia thành lưới ô vuông đơn vị, các hàng được đánh số từ 1 tới 𝑚 từ trên xuống và các cột được đánh số từ 1 tới 𝑛 từ trái qua phải, ô nằm trên giao của hàng 𝑖 và cột 𝑗 được gọi là ô (𝑖,𝑗). Khi mới được xây dựng, tất cả các ô là ô trống và được coi là có độ cao bằng 0. Trong quá trình sử dụng, nhà thi đấu đã tổ chức 𝑘 sự kiện thể thao đánh số từ 1 tới 𝑘, ở sự kiện thứ p (p=1..k) người ta trải thêm các tấm nệm vào tất cả các ô thuộc hình chữ nhật có góc trái trên là (x𝑝, y𝑝) và góc phải dưới là (u𝑝, v𝑝) và làm tăng độ cao của những ô này lên 1 đơn vị. Tức là bao gồm tất cả các ô (𝑖,𝑗) có x𝑝 ≤ 𝑖 ≤ u𝑝 và y𝑝 ≤ 𝑗 ≤ vp. Sắp tới có cuộc thi trượt Patin tại nhà thi đấu. Vì các tấm nệm mềm không thích hợp cho môn thể thao này, Ban tổ chức muốn chọn một hình vuông có các cạnh song song với các cạnh sàn nhà và toàn bộ các ô bên trong hình vuông đó đều cao bằng nhau để đặt lên đó một tấm phủ cứng làm sân trượt Patin. Yêu cầu: Tìm cạnh hình vuông lớn nhất mà Ban tổ chức có thể sử dụng như mô tả trên.

Dữ liệu: Vào từ tệp văn bản CAU4.INP gồm:

• Dòng đầu chứa 3 số nguyên dương m, n, k (m, n ≤ 2000, k ≤ 10^5);
• Dòng thứ p trong k dòng tiếp theo ghi 4 số nguyên dương x𝑝, y𝑝, u𝑝, v𝑝 (xp ≤ u𝑝 ≤ m , y𝑝 ≤ v𝑝 ≤ n với mọi p = 1..k).

  Kết quả: Ghi ra tệp văn bản CAU4.OUT gồm một số nguyên duy nhất là cạnh hình vuông lớn nhất tìm được.

Ví dụ:

CAU4.INP    
    6 6 4
    2 2 3 6
    2 2 6 3
    2 4 4 5
    4 2 6 4 
CAU4.OUT    
    3   
Mô tả
    Độ cao của sàn thi đấu thể hiện ở bảng dưới, các ô gạch chân là hình vuông được chọn.
    0 0 0 0 0 0
    0 2 2 2 2 1
    0 2 2 2 2 1
    0 2 2 2 1 0
    0 2 2 1 0 0
    0 2 2 1 0 0

Ràng buộc:

• Có 40% số điểm có m, n, k ≤ 200;
• Có 30% số điểm tiếp theo có m, n ≤ 200;
• Có 30% số điểm còn lại không còn ràng buộc gì thêm.

Hà có N cuốn sách mới, đánh số từ 1 đến N, em sẽ xếp N cuốn sách này vào các ngăn xếp. Là một người rất nguyên tắc nên mỗi cuốn sách khi xếp vào (và lấy ra) đều sẽ được Hà thực hiện theo thứ tự xác định, cuốn thứ i có thứ tự xếp vào là ai (i=1..N). Mỗi lần lấy sách ra đọc, Hà cũng sẽ lấy cả N cuốn ra và cuốn thứ i có thứ tự lấy ra là bi (i=1..N). Với hai cuốn sách thứ i, j khác nhau bất kì (i, j=1..N) khi được xếp vào chung một ngăn xếp, nếu thứ tự xếp vào của cuốn i bé hơn thứ tự xếp vào của cuốn j thì thứ tự lấy ra của cuốn i phải lớn hơn thứ tự lấy ra của cuốn j (hoặc ngược lại). Tức là nếu ai < aj và bi > bj (hoặc ai > aj và bi < bj) thì hai cuốn i, j mới có thể xếp chung một ngăn xếp.

Yêu cầu: Tính số ngăn xếp ít nhất để Hà có thể xếp vào và lấy ra được N cuốn sách như mô tả trên.

Dữ liệu: Vào từ tệp văn bản CAU5.INP gồm:

• Dòng đầu chứa số nguyên dương T là số test (T ≤ 3);
• Tiếp theo là T test, mỗi test gồm:
  • Dòng đầu chứa số nguyên dương N (N ≤ 2.10^5);
  • Dòng thứ hai chứa N số nguyên dương a1, a2,.., aN (ai ≤ N và khác nhau đôi một với mọi i = 1..N).
  • Dòng thứ ba chứa N số nguyên dương b1, b2,.., bN (bi ≤ N và khác nhau đôi một với mọi i = 1..N).

    Kết quả: Ghi ra tệp văn bản CAU5.OUT gồm T dòng là kết quả của T test, mỗi test ghi ra một số nguyên là số ngăn xếp ít nhất tìm được.

Ví dụ:

CAU5.INP
    1
    5
    3 5 2 4 1
    3 2 5 1 4
CAU5.OUT
    2

Ràng buộc:

• Có 30% số điểm có: T = 3 và số ngăn xếp ít nhất không quá 2;
• Có 30% số điểm tiếp theo có: T = 2 và N ≤ 10;
• Có 40% số điểm còn lại có: T = 1 và N > 10.