Chấm bài theo link:
https://chuyentinpbc.ucode.vn/contests/cs1-de-co-ban-7-55042
BÀI 1: Cặp số tương đồng
Bạn An rất yêu thích toán học, đặc biệt là Số học. Một ngày nọ, trong lúc giải một bài toán số học, An nhận ra có nhiều cặp số có tổng các chữ số trong biểu diễn thập phân của chúng bằng nhau. Ví dụ cặp số 12 và 30 có tổng các chữ số bằng nhau là 3.
Yêu cầu: Cho 2 số nguyên dương l, r, hãy tìm cặp số tương đồng trong đoạn [l, r] mà có hiệu 2 số là lớn nhất.
Dữ liệu: Vào từ file SIMILAR.INP gồm 1 dòng chứa hai số nguyên l, r không vượt quá 10^7.
Kết quả: Ghi ra file SIMILAR.OUT 1 dòng chứa số nguyên là hiệu lớn nhất tìm được.
Giới hạn: 50% số test có l, r ≤ 10^3.
Ví dụ:
Copy code
SIMILAR.INP
10 30
SIMILAR.OUT
18
Giải thích: Cặp số cần tìm là 12 và 30 (có tổng các chữ số là 1 + 2 = 3 và 3 + 0 = 3). Ngoài ra còn một số cặp tương đồng khác là 14 và 23 hoặc 16 và 25.
BÀI 2: Hình chữ nhật lớn nhất
Trong mặt phẳng Oxy vẽ hình tròn tâm O bán kính R. Ta xác định các hình chữ nhật có tọa độ nguyên, nằm trên hình tròn (O, R) và các cạnh song song với các trục tọa độ (đỉnh của hình chữ nhật nằm trong hoặc trên đường tròn).
Lưu ý:
- Hình vuông là hình chữ nhật có 2 cạnh bằng nhau.
• Điểm M(x0, y0) nằm trong hoặc nằm trên đường tròn khi và chỉ khi các tọa độ của nó thỏa mãn
x0+y0< R2.
Yêu cầu: Xác định giá trị lớn nhất về diện tích trong các hình chữ nhật thỏa mãn yêu cầu trên.
Dữ liệu: vào từ file DIENTICH.INP chứa một số nguyên dương R (R < 104)
Kết quả: Một dòng duy nhất chứa hai số nguyên dương d và L cách nhau khoảng trắng.
Trong đó d: chỉ số của phần tử đầu tiên trong đoạn; L: số phần tử trong đoạn (chiều dài đoạn).
Nếu vô nghiệm thì in ra số 0.
Ví dụ:
| DIENTICH. INP | DIENTICH.OUT |
| 5 | 48 |
| 3 | 16 |
| 1 | 0 |
Giải thích
Hình chữ nhật có diện tích lớn nhất là 48 có đỉnh là (–3,4); (–3,−4); (3,–4); (3,4) nằm trên hình tròn (0,5)
Hình chữ nhật có diện tích lớn nhất là 12 có đỉnh là (–2,2); (–2,−2); (2,−2); (2,2) nằm trong hình tròn (0,3)
Không có hình chữ nhật tọa độ nguyên nằm trong hình tròn (0,1)
BÀI 3. Trò chơi xâu ký tự
Bạn có một xâu gồm N ký tự. Đầu tiên, bạn được sắp xếp lại ký tự trong xâu theo một thứ tự bất kỳ. Sau đó, hãy chia xâu ký tự này thành chính xác k xâu ký tự liên tiếp không rỗng sao cho xâu ký tự có thứ tự từ điển lớn nhất là nhỏ nhất có thể.
Xâu A có thứ tự từ điển nhỏ hơn B khi thỏa một trong những điều kiện sau:
- A là tiền tố của B và A khác B.
- Tồn tại vị trí i (1 <i<min(|A|,|B|)) sao cho A[i] < B[i] và A[j] = B[j] với mọi j (1<j
Ví dụ:
- abc có số thứ tự từ điển nhỏ hơn ad.
- ab có số thứ tự từ điển nhỏ hơn abb,
Dữ liệu: vào từ file STRGAME.INP gồm:
- Dòng thứ nhất chứa hai số N và k (1 <k<N<100);
- Dòng thứ hai gồm xâu chứa N ký tự. Các ký tự là các chữ cái tiếng Anh in thường.
Kết quả: ghi ra file STRGAME.OUT một dòng duy nhất là xâu ký tự có thứ tự từ điển lớn nhất của phương án tối ưu.
Giới hạn:
- 20% số test có xâu ký tự gồm toàn chữ cái a.
- 20% số test tiếp theo có K = N.
• 60% số test còn lại không có ràng buộc gì thêm.
Ví dụ:
| STRGAME. INP | STRGAME.OUT |
| 4 2 baba | ab |
| 4 2 baca | abc |
Giải thích:
• Ở ví dụ đầu tiên, có thể sắp xếp baba thành abab và chia thành 2 xâu con ab và ab. Khi đó xâu có thứ tự từ điển lớn nhất là ab. Cũng có thể xếp thành abba và chia thành 2 xâu abb và a, tuy nhiên phương án này cho xâu có thứ tự từ điển lớn nhất là abb, lớn hơn ab ở phương án đầu tiên.
- Ở ví dụ thứ hai, có thể sắp xếp baca thành abca và chia thành 2 xâu con abc và a. Khi đó xâu ký tự có thứ tự từ điển lớn nhất là abc.
BÀI 4. Khoanh vùng phân loại
Một mảnh vườn hình chữ nhật được chia thành các ô đất gồm M dòng, N cột để ươm các loại cây giống khác nhau. Độ dài cạnh mỗi ô được xem là 1 đơn vị chiều dài, mỗi ô sẽ ươm một trong số các loại cây cần ươm. Để phân vùng các loại cây giống khác nhau trong vườn, người làm vườn tiến hành căng dây để phân biệt theo các đường ranh giới các ô đất. Dây được căng xung quanh mảnh vườn và cạnh của ô nếu 2 ô chứa cạnh đó trồng hai cây giống khác nhau.
Yêu cầu: Tính độ dài của dây cần dùng để khoanh vùng các loại cây trong vườn theo yêu câu.
Dữ liệu: vào từ file VUONGCAY.INP gồm: - Dòng 1: hai số M,N(0 < 100);
- M dòng tiếp theo mỗi dòng chứa N số nguyên dương. Giá trị ở dòng i cột j là aj
với (1<i<M,1<j<N, aij ≤100) để mô tả loại cây được ươm tại ô (i,j) của mảnh vườn (các giá trị giống nhau để chỉ cùng 1 loại cây).
Kết quả: ghi ra file VUONCAY OUT chứa một số nguyên dương duy nhất là chiều dài của dây được dùng khoanh vùng theo yêu cầu của người làm vườn.
Ví dụ:
VUONCAY.INP
VUONCAY.OUT
4 5
| 1 | 1 | 2 | 2 | 4 |
| 3 | 3 | 3 | 4 | 4 |
| 3 | 3 | 3 | 4 | 4 |
| 1 | 2 | 2 | 2 | 2 |
32
Giải thích
Chu vi: 18
- Dây dọc bên trong: 5
- Dây ngang bên trong: 9
Tổng chiều dài dây: 32



Bình luận