TỔNG QUAN BÀI THI NGÀY THỨ HAI
| Bài | Tên bài | Tên chương trình | Tệp dữ liệu | Tệp kết quả | Điểm |
|---|---|---|---|---|---|
| 1 | Trọng yếu | cpo.* | cpo.inp | cpo.out | 7 |
| 2 | Lau cây | crt.* | crt.inp | crt.out | 7 |
| 3 | Tia | ray.* | ray.inp | ray.out | 6 |
Ghi chú: Dấu * được thay thế bởi PY hoặc CPP tùy theo ngôn ngữ lập trình sử dụng.
Bài 1. Trọng yếu (7 điểm)
Cho một đồ thị vô hướng gồm \(n\) đỉnh (được đánh số từ 1 đến \(n\)) và \(m\) cạnh. Đỉnh \(u\) được gọi là đỉnh trọng yếu nếu:
i) Đồ thị có chu trình;
ii) Bỏ đỉnh \(u\) và các cạnh kề với \(u\) thì đồ thị không còn chu trình.
Yêu cầu: Xác định đỉnh trọng yếu có chỉ số nhỏ nhất, nếu không có thì in ra -1.
Dữ liệu vào: Từ tệp cpo.inp
- Dòng đầu tiên ghi số nguyên \(T\) (\(1 \le T \le 10\)) là số lượng bộ test.
- Mỗi bộ test gồm dòng đầu tiên ghi hai số nguyên \(n, m\) (\(1 \le n, m \le 10^5\)).
- \(m\) dòng tiếp theo, mỗi dòng ghi hai số nguyên \(u_i, v_i\) (\(1 \le u_i, v_i \le n\)) biểu diễn cạnh nối giữa hai đỉnh. Đảm bảo không có đa cạnh và không có tự vòng.
Kết quả: Ghi ra tệp cpo.out gồm \(T\) dòng, mỗi dòng chứa chỉ số đỉnh trọng yếu nhỏ nhất tìm được hoặc -1.
Ràng buộc:
- 30% số điểm: \(m \le n + 1\)
- 30% số điểm: \(n \le 1000\)
- 40% số điểm: Không có ràng buộc bổ sung.
Bài 2. Lau cây (7 điểm)
Cho một cây \(T\) gồm \(n\) đỉnh. Mỗi phép "lau" chọn hai nút lá bất kỳ và lau tất cả các cạnh trên đường đi ngắn nhất giữa hai lá đó với chi phí bằng số cạnh \(d\). Quá trình lặp lại với các cặp lá chưa chọn cho tới khi mọi cạnh trên cây được lau ít nhất một lần.
Xét \(Q\) biến thể của cây \(T\). Biến thể \(T_i\) được tạo ra bằng cách thêm \(D_i\) nút lá mới vào cây ban đầu. Yêu cầu tính chi phí nhỏ nhất để lau toàn bộ cạnh của mỗi cây biến thể \(T_i\).
Dữ liệu vào: Từ tệp crt.inp
- Dòng đầu ghi hai số nguyên \(N, Q\) (\(3 \le N \le 10^5; 1 \le Q \le 10^5\)).
- \(N-1\) dòng tiếp theo miêu tả các cạnh của cây ban đầu.
- \(Q\) dòng tiếp theo miêu tả các biến thể: Dòng thứ \(i\) chứa số \(D_i\) và \(D_i\) đỉnh ban đầu được gắn thêm lá mới.
Kết quả: Ghi ra tệp crt.out gồm \(Q\) dòng tương ứng chi phí nhỏ nhất cho từng biến thể.
Bài 3. Tia (6 điểm)
Cho \(n\) tia trên mặt phẳng tọa độ \(Oxy\) và điểm \(M_0(p;q)\). Một đường đi gấp khúc từ gốc tọa độ \(O(0;0)\) đến điểm \(M_0\) được gọi là "an toàn" nếu hoành độ các điểm không giảm và không đoạn thẳng nào trên đường đi cắt bất kỳ tia nào trong \(n\) tia đã cho.
Yêu cầu: Tìm độ dài ngắn nhất của đường đi gấp khúc "an toàn" từ \(O\) đến \(M_0\).
Dữ liệu vào: Từ tệp ray.inp
- Dòng đầu ghi ba số nguyên \(n, p, q\) (\(1 \le n \le 10^5; 0 \le p, q \le 10^6\)).
- \(n\) dòng tiếp theo ghi ba số \(x, y, \theta\) miêu tả tọa độ gốc và góc hướng của mỗi tia.
Kết quả: Ghi ra tệp ray.out độ dài ngắn nhất tìm được với sai số tuyệt đối không quá 1.0.