COCI-11 (2011) - Γύρος #3 - 4 (Robot)

View as PDF

Submit solution

All submissions

Best submissions

Points: 45 (partial)

Time limit: 1.0s

Memory limit: 32M

Author:

HSIN

Problem type

Allowed languages

C, C++, Java, Pascal, Python

Robot

Ο Mirko δημιούργησε ένα νέο ρομπότ και αποφάσισε να το δοκιμάσει σε μια γιγάντια πίστα δοκιμών. Μπορούμε να φανταστούμε το κομμάτι δοκιμής ως σύστημα 2D συντεταγμένων. Το ρομπότ ξεκινά από ένα σημείο $(0,\;0)$ ~(0,\;0)~ και λαμβάνει ένα σύνολο εντολών που υποδηλώνονται με τα γράμματα $S,\;J,\;I,\;Z$ ~S,\;J,\;I,\;Z~, καθένα από αυτά επισημαίνει μια κατεύθυνση προς την οποία πρέπει να κινείται το ρομπότ.
Πιο συγκεκριμένα, εάν ένα ρομπότ βρίσκεται στο $(x,\;y)$ ~(x,\;y)~, $S$ ~S~ ("βόρεια") σημαίνει ότι πρέπει να μετακινηθεί στο $(x,\;y+1)$ ~(x,\;y+1)~, $J$ ~J~("νότος") σημαίνει ότι πρέπει να μετακινηθεί στο $(x,\;y- 1)$ ~(x,\;y- 1)~, I («ανατολή») σημαίνει ότι πρέπει να μετακινηθεί στο $(x+1,\;y)$ ~(x+1,\;y)~ και $Z$ ~Z~ ("δυτικά") σημαίνει ότι πρέπει να μετακινηθεί στο $(x-1,\;y)$ ~(x-1,\;y)~.
Ενώ το ρομπότ λαμβάνει οδηγίες και κινείται στην πίστα δοκιμών, ο Mirko επαληθεύει τη θέση του με τον ακόλουθο τρόπο. Το κομμάτι δοκιμής περιέχει $N$ ~N~ σταθερά σημεία ελέγχου. Μετά από κάθε εντολή, κάθε ένα από τα σημεία ελέγχου μετρά την απόσταση $-$ ~-~Μανχάταν από το ρομπότ. Στη συνέχεια, οι αποστάσεις από όλα τα σημεία ελέγχου αθροίζονται και αποστέλλονται στον Mirko.
Υποθέτοντας ότι το ρομπότ κινείται σύμφωνα με τις οδηγίες χωρίς σφάλμα, υπολογίστε το άθροισμα των αποστάσεων σε όλα τα σημεία ελέγχου μετά από κάθε εντολή.
Παρατήρηση: Η απόσταση $-$ ~-~Μανχάταν των σημείων $(x1,\;y1)$ ~(x1,\;y1)~ και $(x2,\;y2)$ ~(x2,\;y2)~ είναι ίση με $|x1 - x2| + |y1 - y2|$ ~|x1 - x2| + |y1 - y2|~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει θετικούς ακέραιους αριθμούς $N$ ~N~ (αριθμός σημείων ελέγχου, $1 \leq N \leq 100\,000)$ ~1 \leq N \leq 100\,000)~ και $M$ ~M~ (αριθμός εντολών, $1 \leq M \leq 300\,000)$ ~1 \leq M \leq 300\,000)~, που χωρίζονται από ένα μόνο διάστημα.
Καθεμία από τις ακόλουθες $N$ ~N~ γραμμές περιέχει συντεταγμένες ενός σημείου ελέγχου: δύο ακέραιους χωρισμένους στο διάστημα $x,\;y$ ~x,\;y~, με απόλυτη τιμή μικρότερη από $1\,000\,000$ ~1\,000\,000~ (εκατομμύριο). Είναι πιθανό δύο σημεία ελέγχου να έχουν τις ίδιες συντεταγμένες - η απόσταση προς το καθένα από αυτά προστίθεται στο άθροισμα.
Η ακόλουθη γραμμή περιέχει μια σειρά από $M$ ~M~ χαρακτήρες από το σύνολο ${S,\;J,\;I,\;Z}$ ~{S,\;J,\;I,\;Z}~, την ακολουθία εντολών που αποστέλλονται στο ρομπότ.