Untitled
unknown
plain_text
a year ago
5.6 kB
15
Indexable
Bai 4: Sau khi biết tin Eagle xây dựng hệ thống điện và ăn bớt được rất nhiều kinh phí, Hugo rất tức vì khi anh xây cầu anh đã không ăn bớt được đồng nào. Do đó anh quyết phá hệ thống điện của Eagle. Do sợ bị phát hiện nên anh sẽ chỉ phá hệ thống điện ở trên 1 hòn đào, và anh muốn tìm hòn đảo nào sau khi phá xong thì hệ thống điện của Eagle bị chia cắt thành nhiều phần nhất. Hãy giúp Hugo tìm hòn đảo này. Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 100. Mỗi bộ test được tổ chức theo khuôn dạng sau: Dòng đầu tiên ghi lại số tự nhiên N không lớn hơn 100 là số hòn đảo. Những dòng kế tiếp ghi lại ma trận biểu diễn hệ thong mạng lưới điện, trong đó 0 được hiểu là không có đường dây điện nối giữa điểm i và j, 1 được hiểu có đường dây điện trực tiếp giữa điểm i và điểm j (1<=i, j <= N). Output Với mỗi bộ test, in ra màn hình trên một dòng một số duy nhất là hòn đảo bị phá hủy hệ thống điện thỏa mãn yêu cầu bài toán (nếu có nhiều đảo cùng thỏa mãn yêu cầu thì in ra đảo có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống điện, hãy in ra số 0. Example Input: 2 5 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 5 0 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 0 1 1 1 0 Output: 3 0 Output of 5 testcase: 0 1 8 4 0 5 10 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 10 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 15 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 15 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 15 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 ================================================================== bai 5: Our friend Picko is very reach and he wants to open lots of restaurants with delivery. The main food will be, of course, pizza. He has certain number of potential locations for the restaurants, and he knows the locations of the solitaires with lots of people which will often be his customers. Delivery of each restaurant will cover all the solitaires in given radius. Picko can open only limited number of restaurants, and he wants that restaurants on the locations which will cover maximal number of people in solitaires. Write a program that will calculate maximal number of people which we can cover with delivery. Input In the first line of the input file there are two integers K and R, separated with space, number of restaurants and radius of delivery, 1 ≤ K ≤ 10, 1 ≤ R ≤ 500. In the second line there is integer M, number of locations, K ≤ M ≤ 20. In each of the next M lines there are two integer X and Y, separated with space, coordinates of each location, -1000 ≤ X,Y ≤ 1000. In the next line there is integer N, number of solitaires, 1 ≤ N ≤ 100. In each of the next N lines there are three integers X, Y and S, separated with space, X and Y are coordinates of each solitaire, and S is number of people in that solitaire, -1000 ≤ X,Y ≤ 1000, 1 ≤ S ≤ 100. We consider that solitaire is in radius of some restaurant if distance between them is less or equal to R. There are no two locations of restaurants on the same place. Output In only line of the output file we have to write maximal number from the text above. Sample Input 3 2 2 3 1 0 4 0 7 0 4 0 0 1 3 0 7 5 0 9 8 0 1 2 2 3 -2 0 0 1 3 0 8 -3 1 1 -3 0 1 -3 -1 1 -2 -1 1 0 0 3 0 2 1 2 1 3 4 0 2 3 3 5 0 0 1 6 2 3 6 6 7 2 8 0 1 2 0 5 3 0 6 1 1 0 1 3 2 3 3 6 2 6 2 4 8 6 3 Output #1 18 #2 12 #3 17
Editor is loading...
Leave a Comment