Bài tập Code bruteforce, contest, review, sorting, training Dumv 20/03/2025 0 Comments

findSafeHouse

Conan là một thám tử và Haibara là một trong những người bạn tốt nhất của anh. Anh đã nhờ Haibara làm gián điệp để khám phá ra kẻ giết người trong một vụ án. Không may, nhiệm vụ của Haibara đã không đi theo kế hoạch và cô đã bị phát hiện. Cô rất hoảng loạn và cần tìm nơi trú ẩn an toàn càng nhanh càng tốt. Hãy giúp Haibara tìm được ngôi nhà an toàn nhất dựa trên vị trí hiện tại của cô ấy.

Cho mảng house chứa thông tin về n ngôi nhà an toàn xung quanh vị trí của Haibara. Mỗi phần tử thứ i của mảng house sẽ có dạng [d_i,m_i]. Trong đó:

d_i là khoảng cách từ ngôi nhà đến vị trí của Haibara, tính bằng km
m_i là số đồng tiền xu mà ngôi nhà đang có.

Biết x là khoảng cách tối đa mà Haibara có thể di chuyển, những điều kiện để chọn nhà an toàn sẽ là:

Ngôi nhà an toàn nhất phải ở vị trí không lớn hơn x và phải chứa ít nhất y đồng xu.
Nếu có nhiều hơn một ngôi nhà thỏa mãn điều kiện, bạn phải chọn ngôi nhà gần nhất.
Nếu có nhiều hơn một ngôi nhà an toàn và có cùng khoảng cách so với vị trí hiện tại, bạn phải chọn ngôi nhà có chứa nhiều đồng xu nhất.
Nếu có nhiều hơn một ngôi nhà an toàn thỏa mãn tất cả các điều kiện trên, bạn phải chọn ngôi nhà với chỉ số nhỏ nhất.

Đừng quên rằng Haibara đang gặp nguy hiểm, vì vậy hãy tìm và in ra màn hình ngôi nhà thích hợp. Nếu không thể tìm được căn nhà thích hợp thì trả về -1.

Ví dụ:

Với n = 4, x = 4, y = 6, house = [[3,7], [3,8],[2,4],[5,2]], thì kết quả sẽ là findSafeHouse(n,x,y,house) = 2.
Ở trường hợp này, bạn cần tìm ngôi nhà thứ 2 house[2] =[3,8] bởi vì:
Ở đây, bạn sẽ cần tìm ngôi nhà có vị trí cách vị trị của Haibara không lớn hơn 4 km và phải chứa tối thiểu 6 đồng tiền xu.
Như vậy bạn có thể chọn ngôi nhà an toàn thứ 1 hoặc ngôi nhà an toàn thứ 2, nhưng dựa trên điều kiện thứ ba thì ngôi nhà an toàn thứ 2 là phù hợp nhất.

Đầu vào/Đầu ra:

[Thời gian chạy] 0.5s với C++, 3s với Java and C#, 4s với Python, GO và JS
[Đầu vào] integer n
Số lượng ngôi nhà.
1 ≤ n ≤ 500
[Đầu vào] integer x
1 ≤ x ≤ 1000
[Đầu vào] integer y
1 ≤ y ≤ 500
[Đầu vào] matrix.int house
1 ≤ house.size() ≤ 500
house[i] = 2
1 ≤ house[i][0], house[i][1] ≤1000
[Đầu ra] integer
Số thứ tự của ngôi nhà an toàn phù hợp nhất với Haibara ( số thứ tự của nhà đếm từ 1). Nếu không thể tìm được căn nhà phù hợp thì trả về -1.