UVa-10360 - Rat Attack - DMOJ: Modern Online Judge

UVa-10360 - Rat Attack

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

UVa

Problem type

Allowed languages

C, C++, Java, Python

Εκφώνηση

ΜΠΑΜ! Άλλη μια θανατηφόρα βόμβα αερίων εκρήγνυται στις αποχετρυσεις του Μανχάταν. Αρουραίοι έχουν πάρει έλεγχο όλων των υπονόμων και το συμβούλιο της πόλης κάνει ότι μπορεί για να κρατήσει τον πληθυσμό τους υπό έλεγχο.

Το Μανχάταν έχει ορθοκανονική πολεοδομία, με τους δρόμους και τις λεωφόρους να τέμνονται κάθετα μεταξύ τους. Τα νερά στους υπονόμους τρέχουν ακριβώς κάτω από τους δρόμους και οι αρουραίοι πάντα στήνουν σκηνές στις διασταυρώσεις τους. Ο μόνος τρόπος να εξουδετερωθούν είναι με χρήση βομβών αερίου, όπως αυτή που εκρήχθη. Όμως, οι βόμβες αερίων δεν είναι επικίνδυνες μόνο για τους αρουραίους. Οι ουρανοξύστες πάνω από το σημείο ρίψης πρέπει να εκκενωθούν νωρίτερα, άρα τα σημεία πρέπει να επιλεχθούν πολύ προσεκτικά.

Οι βόμβες ονομάζονται "έξυπνες βόμβες γι αρουραίους". Είναι έξυπνες επειδή, όταν εκρήγνυται, το αέριο εξαπλώνεται σε τετραγωνική μορφή μέσω των υπονόμων. Η ισχύς της βόμβας δίνεται από έναν αριθμό $d$ ~d~ που ορίζει την τετραγωνική "ακτίνα" (επηρεάζονται όσα τετράγωνα έχουν οριζόντια και κατακόρυφη απόσταση το πολύ $d$ ~d~).

Η περιοχή προς συζήτηση είναι ένα διακριτό πλέγμα $1025\times 1025$ ~1025\times 1025~ τετραγώνων. Επαγγελματίες έχουν δώσει λεπτομερή πληροφόρηση με τα διάφορα σημεία που υπάρχουν φωλιές αρουραίων, καθώς και τον πληθυσμό της κάθε μίας. Σας δίνεται μία βόμβα ισχύος $d$ ~d~ και πρέπει να βρείτε την τοποθεσία ρίψης της βόμβα που εξοντόνει τους περισσότερους αρουραίους.

Η καλύτερη θέση αποφασίζεται από τα παρακάτω κριτήρια:

Το άθροισμα των πληθυσμών των φωλιών εντός της περιοχής εξουδετέρωσης είναι το μέγιστο δυνατό
Αν υπάρχουν παραπάνω από μία τέτοια θέση, τότε η "μικρότερη" θέση προτιμάται (αυτή με μικρότερη συνιστώσα $x$ ~x~ ή, αν είναι ίσες, με μικρότερη $y$ ~y~).

Τυπικά, δωθείσας τοποθεσίας ρίψης $(x_0, y_0)$ ~(x_0, y_0)~, ένα σημείο $(x, y)$ ~(x, y)~ επηρρεάζεται αν και μόνο αν $\max(|x - x_0|, |y - y_0|) \leq d$ ~\max(|x - x_0|, |y - y_0|) \leq d~.

Μορφή εισόδου

Η πρώτη γραμμή έχει έναν θετικό ακέραιο $T$ ~T~, το πλήθος των σεναρίων.

Κάθε σενάριο ξεκινάει με 1 γραμμή με μοναδικό ακέραιο $d$ ~d~, την ισχύ της βόμβας. Η δεύτερη γραμμή έχει το πλήθος φωλιών αρουραίων $n$ ~n~. Ακολουθούν $n$ ~n~ γραμμές, κάθε μία με 3 ακεραίους $x, y, s$ ~x, y, s~, τις συντεταγμένες $(x, y)$ ~(x, y)~ της φωλιάς και τον πληθυσμό της $s$ ~s~.

Τα σενάρια διαχωρίζονται από 1 κενή γραμμή.

Μορφή εξόδου

Υπάρχουν $T$ ~T~ γραμμές, η κάθε μία με τις συντεταγμένες $(x_0, y_0)$ ~(x_0, y_0)~ της βέλτιστης τοποθεσίας ρίψης και το πλήθος αρουραίων που θα εξουδετερωθούν. Οι 3 αριθμοί πρέπει να χωρίζονται από 1 ακριβώς κενό, χωρίς άλλα σύμβολα (παρενθέσεις κ.λπ.).

Περιορισμοί

$1 \leq T \leq$ ~ 1 \leq T \leq ~
$1 \leq d \leq 50$ ~1 \leq d \leq 50~
$0 \leq x, y \leq 1024$ ~0 \leq x, y \leq 1024~
$1 \leq n \leq 20,000$ ~1 \leq n \leq 20,000~
$1 \leq s \leq 255$ ~1 \leq s \leq 255~

Παράδειγμα 1

Είσοδος

Έξοδος

5 5 30

Comments

0

papazacharias_menelaos commented on Oct. 15, 2023, 8:17 a.m. ← edited →

νομίζω το βγαλα

0

athanasopoulos_ilias commented on Oct. 14, 2023, 7:08 a.m. ← edit 3 →

Couldn't make it work... Sorry.

0
athanasopoulos_ilias commented on Oct. 14, 2023, 7:00 a.m. ← edit 7 →
Example layout:\n

32.| T
33.| d
34.| n
35.| x y s
36.| x y s
37.| x y s
38.| ...

39.| d
10.| n
11.| x y s
12.| x y s
13.| x y s
14.| ...

15.| d
16.| n
17.| x y s
18.| x y s
28.| x y s
20.| ...