Weekly Contest #02
Points: 300
Dọc theo con đường tơ lụa những con lạc đà cần mẫn chuyên chở tơ lụa, hương liệu và ngọc ngà đá quý của phương đông. Đá quý được phân thành 26 loại ký hiệu bằng chữ cái la tinh thường từ a đến z. Các lái buôn muốn bán được hàng với giá càng cao càng tốt. Trong chuyến đi này một lái buôn mang theo bộ đá quý gồm n viên. Ông xâu tất cả thành chuỗi và bày ra trên thảm trước một lãnh chúa hùng mạnh. Vị lãnh chúa cân nhắc đánh giá chất lượng bộ đá quý để quyết định có nên mua hay không. Theo quy tắc truyền thống của địa phương, giá trị của chuỗi ngọc phụ thuộc vào sự xuất hiện các cặp ngọc (
Yêu cầu: Cho biết n và xâu S thể hiện các loại ngọc trong chuỗi, cách định giá trị chuỗi ngọc của địa phương. Hãy xác định giá trị của chuỗi ngọc.
Dữ liệu:
- Dòng thứ nhất chứa số nguyên dương T, là số lượng test có trong file dữ liệu
- Mỗi test có cấu trúc như sau:
- Dòng thứ nhất chứa hai số nguyên dương n, k.
- Dòng thứ 2 chứa xâu S.
- Mỗi dòng trong k dòng sau chứa xâu 2 ký tự xác định cặp có giá trị.
Kết quả: Ghi ra một số nguyên – giá trị chuỗi ngọc
Ví dụ:
Input
1
7 3
abacaba
ab
ac
bb
Output
7
* Giới hạn:* 0 < T ≤ 10; 0 < n ≤
* Ràng buộc:*
- Subtask1: 50% số test ứng với 50% số điểm của bài có n ≤
; k ≤ . - Subtask2: 20% số test khác ứng với 20% số điểm của bài có n ≤
; k ≤ - Subtask3: 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì.
Points: 300
Mê cung có
Dãy
phần tử đầu tiên của hai dãy bằng nhau, tức là = , = ,...., =- Phần tử thứ
của dãy nhỏ hơn phần tử thứ của dãy , tức là < .
Ví dụ: dãy
Yêu cầu:
Cho
Dữ liệu:
- Dòng đầu tiên chứa 2 số nguyên
và , - Dòng thứ
trong dòng sau chứa 3 số nguyên , và .
*Kết quả: *
- Dòng đầu tiên chứa số nguyên
, - Dòng thứ 2 chứa
số nguyên – màu của các đoạn theo trình tự đi.
Ví dụ:
Input
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
Output
2
1 3
*Giới hạn: * 2 ≤ n ≤
Ràng buộc:
- Subtask1: 30% số test ứng với 30% số điểm của bài tất cả các đường đi đều có cùng một màu.
- Subtask2: 30% số test khác ứng với 30% số điểm của bài có 1 ≤ c ≤ 9, 2 ≤ n ≤
và 1 ≤ m ≤ . - Subtask3: 40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì.
Cho dãy số nguyên
Yêu cầu: Với mỗi truy vấn dạng
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương
- Dòng thứ hai chứa n số nguyên dương
, , …, - Dòng thứ ba ghi số nguyên dương
là số lượng truy vấn - m dòng cuối cùng, mỗi dòng chứa hai số nguyên
.
Kết quả: Gồm
Ví dụ:
Input
3
1 2 3
3
1 2
2 3
3 3
Output
3
5
3
Giới hạn: 1 ≤ n, m ≤
Ràng buộc:
- Subtask1: 40% số test ứng 40% số điểm của bài có n, m ≤
. - Subtask2: 30% số test khác ứng 30% số điểm của bài có n, m ≤
- Subtask3: 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì.
Một quốc gia nọ có
Dữ liệu vào:
- Dòng một chứa số nguyên dương
là số lượng quốc gia bạn cần giúp đỡ. - Tiếp theo là
bộ dữ liệu, mỗi bộ dữ liệu gồm: - Dòng đầu chứa
số nguyên , số thành phố và số con đường chiều - Mỗi dòng trong
dòng tiếp theo gồm số nguyên : người ta đã xây dựng con đường chiều từ đến .
Dữ liệu ra:
Mỗi dòng là câu trả lời cho một bộ dữ liệu tương ứng: in ra YES nếu quốc vương cần xây thêm đường mới, NO nếu những con đường hiện tại đã thỏa mãn yêu cầu của ông.
Ví dụ:
Input:
2
3 3
1 2
2 3
3 1
3 2
1 2
2 3
Output:
NO
YES
Ràng buộc:
- Có
điểm tương ứng với trường hợp . - Có
điểm tương ứng với trường hợp .
Giải thích:
Trong bộ dữ liệu thứ hai, có