Chọn ĐTQG TPHCM 2024

Chọn ĐTQG TPHCM 2024

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Tham quan

Một địa phương tổ chức hội chợ truyền thống. Hội chợ có N gian hàng được đánh số thứ tự từ 1 đến N. Các gian hàng được nối nhau bởi M con đường một chiều, mỗi con đường nối trực tiếp hai gian hàng và giữa hai gian hàng bất kỳ có tối đa một con đường nối chúng. Mỗi khách đến tham quan gian hàng thứ i (1 ≤ i ≤ N) sẽ được tặng số điểm thưởng là c_i và một khách có thể đến một gian hàng nhiều lần nhưng chỉ nhận được điểm thưởng một lần của gian hàng đó.

Sau một hành trình tham quan, ban tổ chức quy đổi điểm thưởng thành quà tặng cho khách tham quan. Do đó, du khách muốn tìm một hành trình qua các gian hàng sao cho tổng điểm thưởng càng nhiều càng tốt. Một hành trình tham quan sẽ xuất phát từ một gian hàng bất kỳ, đi theo các con đường (trong M con đường trên) qua các gian hàng khác và kết thúc tại một gian hàng nào đó. Một gian hàng có thể được đến nhiều lần trong một hành trình.

Yêu cầu : Hãy viết chương trình tính tổng điểm thưởng lớn nhất mà khách có thể nhận được sau một hành trình.

Input

Dòng đầu là hai số nguyên dương N, M, trong đó 1 ≤ N, M ≤ 10⁵. Dòng tiếp theo gồm N số nguyên c₁, c₂, ⋯, c_N cho biết điểm thưởng của các gian hàng, trong đó 0 ≤ c_i ≤ 10⁹. Trên M dòng tiếp theo, mỗi dòng là một cặp số u, v phân biệt với 1 ≤ u, v ≤ N cho biết có đường đi một chiều nối từ gian hàng thứ u sang v. Dữ liệu đảm bảo rằng không có cặp (u, v) nào xuất hiện hơn một lần.

Output

Một số nguyên duy nhất cho biết tổng điểm thưởng lớn nhất mà khách có thể nhận được sau một hành trình.

Scoring

Sample Input 1

3 1
4 5 10
1 2

Sample Output 1

10

Sample Input 2

8 8
10 12 8 16 1 5 12 8
1 2
2 4
4 1
3 2
5 3
2 6
5 7
7 8

Sample Output 2

52

Notes

• Test 1: Khách có thể tham quan gian hàng số 3 với điểm thưởng là 10; nếu đi tham quan gian hàng 1 và 2 thì tổng điểm thưởng là 4 + 5 = 9 thì ít hơn.

• Test 2: Xuất phát từ gian hàng 5, kết thúc ở gian hàng 6 và qua các con đường như sau: 5 → 3 → 2 → 4 → 1 → 2 → 6. Tổng số điểm thưởng là: 1 + 8 + 12 + 16 + 10 + 5 = 52

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Đặt phòng

Có N khách sạn chào giá cho thuê đến các công ty du lịch. Khách sạn thứ i cung cấp thông tin: số phòng trong khách sạn c_i, chỉ số tiện nghi các phòng trong khách sạn f_i và số tiền cho thuê toàn bộ số phòng của khách sạn là p_i. Các phòng trong cùng một khách sạn thì có cùng một chỉ số tiện nghi f.

Các công ty du lịch khi chọn thuê một khách sạn phải chọn thuê toàn bộ số phòng khách sạn đó, không thuê lẻ từng phòng của khách sạn. Dũng đang làm nhân viên bán hàng trong công ty du lịch AlphaTour, nhận được M yêu cầu thuê phòng từ các đại lý, các yêu cầu được đánh chỉ số từ 1 đến M. Yêu cầu thuê thứ i cũng có các thông tin: số phòng cần thuê C_i, chỉ số tiện nghi tối thiểu của các phòng này F_i và giá tiền đề nghị cho yêu cầu này P_i. Các phòng cung cấp cho mỗi yêu cầu không nhất thiết phải thuộc cùng một khách sạn nhưng cần đảm bảo chỉ số tiện nghi của các phòng phải lớn hơn hay bằng chỉ số tiện nghi của yêu cầu đó.

Yêu cầu : Hãy viết một chương trình giúp Dũng chọn thuê những khách sạn nào và chọn đáp ứng những yêu cầu đặt phòng nào để lợi nhuận thu được là nhiều nhất. Lợi nhuận là khoảng tiền chênh lệch giữa chi phí thuê khách sạn và số tiền thu được từ các yêu cầu được chọn.

Input

Dòng đầu là một số nguyên N (1 ≤ N ≤ 2000). Dòng thứ i trong N dòng tiếp theo cho biết thông tin chào giá của khách sạn thứ i gồm 3 số nguyên m_i, f_i, p_i (1 ≤ m_i ≤ 50, 1 ≤ f_i, p_i ≤ 10⁹). Dòng tiếp theo chứa một số nguyên M (1 ≤ M ≤ 2000). Dòng thứ j trong M dòng tiếp theo cho biết thông tin yêu cầu thuê phòng thứ j gồm 3 số nguyên M_j, F_j, P_j (1 ≤ M_i ≤ 50, 1 ≤ F_i, P_i ≤ 10⁹).

Output

Một số nguyên cho biết lợi nhuận tối đa khi chọn thuê khách sạn và những yêu cầu thuê phòng.

Scoring

Sample Input 1

4
5 15 50
7 20 60
6 17 55
10 18 58
3
10 19 200
10 15 140
10 10 100

Sample Output 1

82

Sample Input 2

4
5 19 50
7 20 60
6 17 55
10 18 58
3
10 19 200
10 15 140
10 10 100

Sample Output 2

172

Notes

• Test 1: Chọn thuê khách sạn số 4 và chọn đáp ứng yêu cầu số 2 để có lợi nhuận cao nhất là 82.

• Test 2: Chọn thuê khách sạn số 1, 2, 4 và chọn đáp ứng yêu cầu số 1, 2 để có lợi nhuận cao nhất là 172.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Drone

Công ty AlphaZone đang thực hiện việc giao nhận hàng dọc trên tuyến đường quốc lộ. Ta có thể xem tuyến quốc lộ này như một đoạn thẳng và các vị trí giao nhận là một điểm trên đoạn thẳng này, được đánh chỉ số liên tiếp từ 0 đến 10⁹. Các điểm lân cận nhau cách nhau 1 đơn vị chiều dài.

Hiện tại công ty dùng xe tải để giao hàng, với phương thức này thì thời gian để giao hàng từ điểm a đến điểm b sẽ là |a - b|. Việc giao hàng bằng xe tải có thể thực hiện trên bất kỳ đoạn đường nào của quốc lộ. Các đoạn đường trên quốc lộ sử dụng xe tải giao hàng là hai chiều.

Công ty đang thử nghiệm giao hàng bằng máy bay không người lái (drone) và đã thiết lập một số tuyến đường có thể vận chuyển bằng drone. Một tuyến đường giao hàng bằng drone được mô tả bằng 3 tham số (x, y, t) cho biết drone có thể giao hàng một chiều từ điểm x đến điểm y và tốn thời gian là t. Có thể giả sử công ty có sẵn xe tải tại tất cả điểm trên quốc lộ và drone có sẵn tại những tuyến đường được chọn triển khai thử nghiệm, và bạn được tuỳ chọn hình thức giao hàng bằng xe tải, drone hay kết hợp cả hai. Mỗi đơn hàng bạn chỉ được tối đa một lần sử dụng drone, số lần dùng xe tải để giao hàng là không giới hạn.

Yêu cầu : Cho trước M đơn hàng cần giao và thông tin về các tuyến đường được chọn thử nghiệm giao hàng bằng drone. Hãy viết một chương trình cho biết thời gian tối thiểu để giao từng đơn hàng.

Input

Dòng đầu là hai số nguyên N, M lần lượt cho biết số tuyến đường giao hàng bằng drone và số đơn hàng. Dòng thứ i trong N dòng tiếp theo mô tả một tuyến đường giao hàng bằng drone gồm 3 số x_i, y_i và t_i cho biết drone có thể giao hàng từ x_i đến y_i và tốn t_i thời gian (0 ≤ x_i, y_i, t_i ≤ 10⁹). Dòng thứ j trong M dòng tiếp theo gồm hai số nguyên a_j, b_j cho biết đơn hàng thứ j cần giao từ vị trí a_j đến vị trí b_j (0 ≤ a_j, b_j ≤ 10⁹).

Output

Gồm M dòng, dòng thứ j là một số nguyên cho biết thời gian tối thiểu cần để giao đơn hàng thứ j.

Scoring

Sample Input 1

5 3
5 10 2
12 20 1
18 7 3
15 25 3
22 12 4
6 20
12 30
15 22

Sample Output 1

7
11
6

Notes

Đơn hàng 1: Xe tải giao hàng từ điểm 6 đến điểm 12, tốn thời gian: 6; dùng drone giao từ điểm 12 đến 20, tốn thời gian: 1. Tổng thời gian là: 7

Đơn hàng 2: Có thể để drone giao hàng từ điểm 12 đến điểm 20, tốn thời gian: 1; xe tải giao hàng từ điểm 20 đến điểm 30, tốn thời gian: 10. Tổng thời gian là: 11

Đơn hàng 3: Xe tải giao hàng từ điểm 15 về điểm 12, tốn thời gian: 3; Dùng drone giao hàng từ điểm 12 đến 20, tốn thời gian: 1; xe tải giao hàng từ điểm 20 đến 22, tốn thời gian: 2. Tổng thời gian là: 6.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Đèn đường

Một con đường được xem như một trục số dương xét từ 0 đến 2³¹ - 1. Hai công ty A và B nhận thi công lắp đặt đèn đường. A thi công các đèn trên lề trái con đường, B thi công các đèn trên lề phải con đường. A lắp đặt đèn đầu tiên ở vị trí a và cứ cách d₁ đơn vị độ dài thì đặt tiếp một cái nữa, như thế các đèn được lắp tại các vị trí có toạ độ a, a + d₁, a + 2d₁, ⋯. B thi công tương tự nhưng sẽ lắp đặt đèn đầu tiên ở vị trí b và cách d₂ đơn vị độ dài thì đặt tiếp một cái nữa, như thế các đèn được lắp tại các vị trí có toạ độ b, b + d₂, b + 2d₂, ⋯.

Lan thường chạy bộ trên con đường này vào sáng sớm, xuất phát tại một vị trí L tuỳ ý (L là số nguyên thuộc [0; 10⁵]) và chạy đến vị trí L + k (k là số nguyên thuộc [1; 10⁹]). Do trời chưa sáng hẳn nên Lan chỉ thấy rõ cảnh vật hai bên đường ở vị trí x mà tại đó có cả đèn được lắp trên lề trái và lề phải. Lan muốn chọn vị trí xuất phát thích hợp để chạy qua được nhiều nhất những vị trí x.

Yêu cầu : Hãy viết một chương trình cho biết số lượng nhiều nhất các vị trí mà Lan có thể thấy rõ cảnh vật hai bên đường.

Input

Một dòng duy nhất gồm các số nguyên dương d₁, a, d₂, b, k có giá trị không vượt quá 10⁹.

Output

Một số nguyên duy nhất là số lượng nhiều nhất các vị trí mà Lan có thể thấy rõ cảnh vật.

Scoring

Sample Input 1

2 1 2 2 2024

Sample Output 1

0

Sample Input 2

2 1000 4 1000 2024

Sample Output 2

507

Sample Input 3

2 1 3 1 1000000000

Sample Output 3

166666667

Notes

• Test 1: A chỉ lắp đèn ở vị trí lẻ, còn B lắp ở vị trí chẵn. Không có vị trí nào có cả đèn hai bên đường.

• Test 2: Lan có thể xuất phát từ vị trí 1000 và khi đi qua các vị trí chia hết cho 4 thì có cả đèn hai bên đường. Từ 1000 đến 3024 có tất cả 507 vị trí như thế.

• Test 3: Lan có thể xuất phát từ vị trí 1 và khi đi qua các vị trí chia 6 dư 1 thì có cả đèn hai bên đường. Từ 1 đến 10⁹ sẽ có tất cả 166666667 vị trí như thế.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. Dãy bập bênh

Một dãy được gọi là dãy con của dãy Y nếu như nó được tạo bằng cách xóa đi một vài phần tử của Y (hoặc không xóa phần tử nào) và giữ nguyên thứ tự các phần tử còn lại.

Dãy số nguyên c₁, c₂, ⋯, c_k được gọi là bập bênh nếu như k ≥ 3 và thỏa mãn một trong hai điều kiện sau: c₁ < c₂ > c₃ < c₄ > ⋯ hoặc c₁ > c₂ < c₃ > c₄ < ⋯, hay nói một cách tổng quát, ta luôn có (c_i - c_i-1)(c_i - c_i+1) > 0 với mọi 1 < i < k.

Yêu cầu : Cho hai dãy số nguyên a, b lần lượt có m, n phần tử, hãy viết chương trình cho biết độ dài của dãy con chung bập bênh dài nhất của hai dãy a, b.

Input

Dòng đầu chứa hai số nguyên dương m, n cho biết độ dài của hai dãy con (1 ≤ m, n ≤ 10⁴). Dòng thứ hai gồm m số nguyên dương a₁, a₂, ⋯, a_m. Dòng thứ ba gồm n số nguyên dương b₁, b₂, ⋯, b_n. Các số trong hai dãy đều không vượt quá 10⁴.

Output

Một số nguyên duy nhất là độ dài lớn nhất của dãy con chung bập bênh, nếu không tồn tại dãy như thế thì in ra 0.

Scoring

Sample Input 1

7 6
1 3 5 4 6 2 3
1 2 5 4 3 6

Sample Output 1

4

Sample Input 2

6 6
1 2 3 4 5 6
6 5 4 3 2 1

Sample Output 2

0

Notes

• Test 1: Dãy con chung bập bênh dài nhất (1, 5, 4, 6) có độ dài 4.

• Test 2: Các dãy đã cho đều tăng hoặc giảm nên không tồn tại dãy con bập bênh nào.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. Freeship

Nhân dịp khai trương cửa hàng bánh rán Doracake, cửa hàng có chương trình giao hàng miễn phí cho tất cả các đơn hàng giao đi. Do chỉ có một nhân viên giao hàng, chủ cửa hàng muốn biết với K đơn hàng cần giao được thống kê đến hiện tại, một khách hàng phải chờ nhiều nhất là bao lâu từ lúc đặt hàng đến lúc nhận hàng. Nhân viên sẽ giao hàng theo thứ tự đặt hàng, đảm bảo rằng đơn đặt trước phải được giao trước.

Thành phố có N địa điểm được đánh số từ 1 đến N, cửa hàng được đặt tại địa điểm số 1. Các địa điểm được kết nối bằng M con đường hai chiều. Có tối đa một con đường nối hai địa điểm. Một địa điểm được đảm bảo có thể đến được từ bất kỳ địa điểm nào. Giả sử thời gian giao hàng tại các địa điểm và thời gian lấy bánh tại cửa hàng là không đáng kể. Vào thời điểm t = 0 thì nhân viên giao hàng đã ở cửa hàng và sẵn sàng giao hàng.

Yêu cầu : Hãy viết chương trình cho biết thời gian khách hàng phải chờ nhiều nhất là bao lâu.

Input

Dòng đầu là hai số nguyên N, M (2 ≤ N ≤ 1000, 1 ≤ M ≤ 5000) lần lượt là số lượng địa điểm và số con đường trong thành phố. Dòng thứ i trong M dòng tiếp theo chứa 3 số nguyên u_i, v_i, d_i (1 ≤ u_i, v_i ≤ N; u_i ≠ v_i; 0 ≤ d_i ≤ 10⁸) cho biết con đường hai chiều nối hai địa điểm u_i và v_i cần thời gian d_i để giao hàng, thời gian này áp dụng cho cả hai chiều từ u_i đến v_i và từ v_i đến u_i. Dòng tiếp theo chứa một số nguyên K (1 ≤ K ≤ 1000) cho biết số lượng đơn hàng. Dòng thứ j trong K dòng tiếp theo chứa 3 số nguyên s_j, u_j và t_j (2 ≤ u_j ≤ N, 0 ≤ s_j ≤ t_j ≤ 10⁸) cho biết đơn hàng thứ j được đặt vào thời điểm s_j tại địa điểm u_j và bánh của đơn hàng này ra lò vào thời điểm t_j. Đơn bánh thứ j chỉ được mang đi giao vào thời điểm lớn hơn hay bằng t_j. Các đơn hàng được cho theo thứ tự thời điểm đặt tăng dần và đơn hàng đặt trước cũng sẽ có thời điểm bánh ra lò trước (nếu s_i < s_j thì t_i < t_j).

Output

Một số nguyên là thời gian nhiều nhất khách hàng phải chờ.

Scoring

Sample Input 1

5 5
1 2 4
2 4 3
2 3 3
3 4 2
1 5 5
3
1 3 3
2 4 5
4 5 7

Sample Output 1

22

Notes

Thời điểm 5, nhân viên nhận bánh của đơn hàng 1 và 2 tại cửa hàng. Giao bánh cho đơn hàng 1 tại thời điểm 12, đơn hàng 2 tại thời điểm 14. Nhận bánh đơn hàng 3 tại thời điểm 21, giao bánh đơn hàng 3 tại thời điểm 26. Thời gian chờ lâu nhất ở đơn hàng 3 là 22.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.