Thông tin
Câu 3. Xâu nguyên tố cùng nhau (5,0 điểm) Cho xâu S chỉ có các kí tự chữ cái và kí tự chữ số có độ dài không vượt quá 10 kí tự. Các số trong xâu S là một dãy các kí tựchữ số liên tiếp được phân tách bởi các kí tự chữ cái, xâu S bắt đầu bằng một kí tự chữ cái vàkết thúc cũng bằng một kí tự chữ cái. Khi thực hiện lấy ra các số trong S, ta thu được một dãy số A gồm n số nguyên drong a1, a2, ..,., an (0<a≤ 10%). Hai số nguyên dương x, y được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. Một đoạn con liên tiếp trong dãy A được gọi là nguyên tố cùng nhau nếu mọi cặp số trong đoạn đó là nguyên tố cùng nhau. Yêu cầu: Tìm đoạn con liên tiếp nguyên tố cùng nhau dài nhất. Dữ liệu vào: Trong tệp sprime.inp ghi xâu S. Dữ liệu ra: Ghi ra tệp sprime.out một số duy nhất là độ dài của đoạn con liên tiếp nguyên tố cùng nhau dài nhất của dãy A. Ví dụ: sprime.inp sprime.out a14a5ac7a6bb 3 ac5b2c3a7b 4 Ràng buộс: Giãi thích Thực hiện tách các số trong xâu S ta thu được dãy A gồm các số 14, 5, 7, 6.Đoạn con liên tiếp nguyên tố cùng nhau dài nhất là đoạn: 5, 7, 6 có độ dài bằng 3. Dãy thu được gồm các số 5, 2, 3, 7 đều là các số nguyên tổ phân biệt nên là nguyên tố cùng nhau, có độ dài bằng 4. 30% số test íng với 30% số điểm có:n ≤ 20;
- 40% số test úng với 40% số điểm có: các số nguyên xuất hiện trongxâu S đều là sốnguyên tố;
- 30% số test ứng với 30% số điểm không có ràng buộc thêm.
Câu 4. Dãy số (3,0 điểm) Cho dãy gồm n số tự nhiên a1, a2, a3,..., a, các số a (1≤i≤n) không quá m và có giá trị đôi một khác nhau, trong đó có đúng một số có giá trị bằng 0. Yêu cầu: Thay thế số 0 thành một giá trị bất kì không được trùng với các giá trị đã có để nhận được một dãy con có các giá trị liên tiếp dài nhất có thể. Dữ liệu vào: Trong tệp seq.inp gồm 2 dòng:
- Dòng đầu ghi hai số nguyên m, n (1 ≤n<m ≤ 10).
- Dòng thứ hai chứa n sô tự nhiên đôi một khác nhau không lớn hơn m. Dữ liệu ra: Ghi ra tệp seq.out độ dải của dãy con có giá trị liên tiếp dài nhất có thể đạt được sau khi thay đổi giá trị của số 0. Ví du: seq.inp seq.out 85 82057 4 Ràng buộc: Giải thích Ta có thể gắn giá trị 6 cho phần tử có giá trị 0, khi đó dãy trở thành 8, 2, 6, 5, 7. Dễ thấy dãy con 8, 6, 5, 7 có các phần tử có giá trị liên tiếp nhau là 5, 6, 7, 8 và có độ dài 4 là dài nhất -40% số test ứng với 40% số điểm có: 1≤n≤ 100;
- 30% số test ứng với 30% số điểm có: 100 <n≤ 1000;
- 30% số test ứng với 30% số điểm có: 1000<n<106