Độ khó: Dễ (1/4 điểm)

Có ~X~ mặt sàn hình chữ nhật có cùng kích thước là ~M~ mét (m) và ~N~ mét (m). Chủ đầu tư muốn sử dụng nhiều nhất những viên gạch nguyên vẹn hình vuông có kích thước cạnh là ~K~ xăng-ti-mét (cm) để lát toàn bộ mặt sàn. Phần mặt sàn còn lại, sẽ được dùng gạch thẻ để trang trí.

Yêu cầu: Hãy tính số lượng viên gạch nguyên vẹn hình vuông nhiều nhất được sử dụng để lát tất cả các mặt sàn.

Dữ liệu vào từ tệp văn bản LATSAN.INP:

• Dòng đầu tiên gồm một số nguyên dương ~X~ ~(1 \le X \le 100)~;
• Dòng thứ hai gồm một số nguyên dương ~M~ ~(1 \le M \le 10^3)~;
• Dòng thứ ba gồm một số nguyên dương ~N~ ~(1 \le N \le 10^3)~;
• Dòng thứ tư gồm một số nguyên dương ~K~ ~(1 \le K \le 100)~.

Kết quả ghi ra tệp văn bản LATSAN.OUT:

• Một số nguyên dương là kết quả bài toán.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

2
1
2
6

Sample Output

1056

Giải thích: Có ~2~ mặt sàn, mỗi mặt sàn có kích thước ~1~ m ~\times~ ~2~ m, tương ứng là ~100~ cm ~\times~ ~200~ cm; viên gạch vuông kích thước ~6~ cm ~\times~ ~6~ cm; số viên gạch vuông nguyên vẹn tối đa được sử dụng trên ~2~ mặt sàn là ~528 \times 2 = 1056~ viên.

Độ khó: Trung bình (2/4 điểm)

Trong một trò chơi nhập vai, người chơi thu thập được ~N~ thanh kiếm được đánh số từ ~1~ tới ~N~. Mỗi thanh kiếm ~i~ có chỉ số tấn công ~a_i~ và chỉ số phòng thủ ~b_i~. Quy tắc để phân loại các thanh kiếm như sau:

• Một thanh kiếm ~i~ bị coi là vô dụng (bị thống trị hoàn toàn) nếu tồn tại một thanh kiếm ~j~ khác ~(j \ne i)~ sao cho: ~a_j \ge a_i~ và ~b_j \ge b_i~;
• Ngược lại, nếu không tồn tại bất kỳ thanh kiếm ~j~ nào thống trị được thanh kiếm ~i~ theo cả hai chỉ số như trên thì thanh kiếm ~i~ được coi là hữu dụng.

Biết rằng không có hai thanh kiếm nào trùng nhau cả hai chỉ số (tức là không tồn tại ~i \ne j~ sao cho ~a_i = a_j~ và ~b_i = b_j~).

Yêu cầu: Hãy đếm số lượng thanh kiếm hữu dụng.

Dữ liệu vào từ tệp văn bản THANHKIEM.INP:

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 \le N \le 10^5)~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i, b_i~ ~(1 \le a_i, b_i \le 10^9)~ lần lượt là chỉ số tấn công và phòng thủ của thanh kiếm thứ ~i~.

Kết quả ghi ra tệp văn bản THANHKIEM.OUT:

• Một số nguyên dương là kết quả bài toán.

Ràng buộc:

• Có ~80\%~ số test ứng với ~80\%~ số điểm có ~N \le 1000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

4
3 2
2 4
4 1
1 3

Sample Output

3

Giải thích:

• Thanh kiếm ~1, 2, 3~ là hữu dụng;
• Thanh kiếm ~4~ ~(1, 3)~ bị thanh kiếm ~2~ ~(2, 4)~ thống trị hoàn toàn vì ~2 \ge 1~ và ~4 \ge 3~ ~\rightarrow~ Vô dụng.

Độ khó: Khá (3/4 điểm)

Cho một chuỗi ký tự ~S~ chỉ chứa những ký tự in thường trong bảng chữ cái tiếng Anh và hai số nguyên dương ~K, X~. Một chuỗi ký tự được gọi là "chuỗi đa dạng" nếu tồn tại ít nhất ~K~ ký tự khác nhau mà ~K~ ký tự đó xuất hiện tối thiểu ~X~ lần.

Ví dụ: với ~K = 3, X = 2~ thì chuỗi "aabcabdc" là chuỗi đa dạng vì có ~3~ ký tự 'a', 'b', 'c' đều xuất hiện ít nhất ~2~ lần. Chuỗi "dzzzdda" không phải là chuỗi đa dạng vì có ~3~ ký tự khác nhau nhưng chỉ có ~2~ ký tự 'd', 'z' xuất hiện ít nhất ~2~ lần.

Có thể thực hiện thao tác đổi một ký tự trong ~S~ thành một ký tự bất kỳ khác.

Yêu cầu: Hãy xác định độ dài chuỗi con liên tiếp ngắn nhất của ~S~ là một chuỗi đa dạng với tối đa một thao tác đổi.

Dữ liệu vào từ tệp văn bản DADANG.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~K, X~ ~(1 \le K \le 26;\ 1 \le X \le 10^5)~;
• Một dòng duy nhất chứa một chuỗi ký tự ~S~ có độ dài không vượt quá ~10^5~.

Kết quả ghi ra tệp văn bản DADANG.OUT:

• Một số nguyên duy nhất là kết quả của bài toán. Nếu không có chuỗi con thoả mãn thì in ra ~-1~.

Ràng buộc:

• Có ~60\%~ số test ứng với ~60\%~ số điểm có độ dài chuỗi ~S~ không vượt quá ~100~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có độ dài chuỗi ~S~ không vượt quá ~1000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

2 3
abcacbabac

Sample Output 1

6

Giải thích: Chọn chuỗi con "acbaba" và thực hiện thao tác đổi ký tự c thành ký tự b được chuỗi con "abbaba" có ~2~ ký tự 'a' và 'b', mỗi ký tự xuất hiện ~3~ lần.

Sample Input 2

2 2
abcde

Sample Output 2

-1

Giải thích: Không thể chọn được một chuỗi con với tối đa một thao tác đổi để tồn tại ít nhất ~2~ ký tự khác nhau, mỗi ký tự xuất hiện tối thiểu ~2~ lần.

Độ khó: Khá (3/4 điểm)

Định nghĩa chuỗi ngoặc đúng:

• Chuỗi rỗng là chuỗi ngoặc đúng;
• Nếu ~X~ là chuỗi ngoặc đúng thì ~(X)~ cũng là chuỗi ngoặc đúng;
• Nếu ~X~ và ~Y~ là hai chuỗi ngoặc đúng thì ~XY~ cũng là chuỗi ngoặc đúng.

Ví dụ:

• Chuỗi ngoặc đúng: "", "()", "(())", "()()", "(())()()",…
• Chuỗi ngoặc không đúng: "(", "()(", "())(", ")()(",…

Cho chuỗi ~S~ có độ dài ~N~, chỉ gồm hai loại ký tự '(' và ')'. Chọn hai số nguyên dương ~L~ và ~R~ ~(1 \le L \le R \le N)~, xoá tất cả các ký tự từ vị trí thứ ~L~ đến vị trí thứ ~R~ của chuỗi ~S~.

Ví dụ: ~S =~ "(())()))". Chọn ~L = 3~ và ~R = 6~; đoạn cần xoá là đoạn ký tự được gạch giữa trong chuỗi: "(())()))". Chuỗi ~S~ sau khi xoá: ~S =~ "(())".

Yêu cầu: Hãy đếm số cách chọn ~L, R~ để chuỗi sau khi xoá là một chuỗi ngoặc đúng.

Dữ liệu vào từ tệp văn bản XOANGOAC.INP:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^5)~;
• Dòng thứ hai chứa xâu ~S~ gồm ~N~ ký tự '(' và ')'.

Kết quả ghi ra tệp văn bản XOANGOAC.OUT:

• Một số nguyên dương là kết quả bài toán.

Ràng buộc:

• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~N \le 200~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm có chuỗi ban đầu là chuỗi ngoặc đúng;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 2000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

5
())()

Sample Output 1

6

Giải thích: Các cách xoá thoả mãn:

• ~L = 1;\ R = 5~: ~S =~ "())()" = "";
• ~L = 1;\ R = 3~: ~S =~ "())()" = "()";
• ~L = 2;\ R = 4~: ~S =~ "())()" = "()";
• ~L = 3;\ R = 5~: ~S =~ "())()" = "()";
• ~L = 2;\ R = 2~: ~S =~ "())()" = "()()";
• ~L = 3;\ R = 3~: ~S =~ "())()" = "()()".

Sample Input 2

4
(())

Sample Output 2

2

Giải thích: Các cách xoá thoả mãn:

• ~L = 1;\ R = 4~: ~S =~ "(())" = "";
• ~L = 2;\ R = 3~: ~S =~ "(())" = "()".

Độ khó: Khó (4/4 điểm)

Cho dãy số gồm ~N~ số nguyên ~A_1, A_2, \ldots, A_N~. Cần chia dãy thành các nhóm thoả mãn:

• Mỗi nhóm chứa ít nhất một phần tử;
• Mỗi nhóm là các phần tử liên tiếp;
• Mỗi phần tử thuộc đúng một nhóm;
• Không có giá trị nào xuất hiện trong nhiều hơn ~2~ nhóm.

Ví dụ: ~A = [1, 2, 1, 1, 1, 2]~, có thể chia thành ~4~ nhóm ~[1]~ | ~[2]~ | ~[1, 1, 1]~ | ~[2]~;

Cách chia không đúng là: ~[1]~ | ~[2]~ | ~[1, 1]~ | ~[1, 2]~ vì số ~1~ xuất hiện ở ~3~ nhóm.

Yêu cầu: Hãy tìm cách chia dãy số ra được nhiều nhóm nhất. In ra số lượng nhóm nhiều nhất có thể chia thoả mãn yêu cầu.

Dữ liệu vào từ tệp văn bản CHIANHOM.INP:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 2 \times 10^5)~;
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ ~(|A_i| \le 10^9)~.

Kết quả ghi ra tệp văn bản CHIANHOM.OUT:

• Một số nguyên dương là số lượng nhóm nhiều nhất chia được.

Ràng buộc:

• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~N \le 20~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm dãy số đã cho theo thứ tự không giảm;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 2000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc thêm.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

5
1 2 1 2 1

Sample Output

3

Giải thích: Có thể chia dãy thành ba nhóm hợp lệ là ~[1]~ | ~[2]~ | ~[1, 2, 1]~. Giá trị ~1~ và ~2~ đều chỉ xuất hiện trong hai nhóm. Không thể chia dãy thành bốn nhóm hợp lệ. Cách chia khác cũng thoả mãn: ~[1, 2, 1]~ | ~[2]~ | ~[1]~.