22ος ΠΔΠ Γ' Φάση
Lines man (lines_man)
[25 Μονάδες]
Επεξήγηση εκφώνησης
Μας δίνεται το μήκος \(A\) ενός γηπέδου ποδοσφαίρου και η θέση της μπάλας \(Y_i\) σε κάθε στιγμή \(i = 1, \ldots , M\). Μας ζητείται να υπολογίσουμε πόσο θα μετακινηθεί ο κάθε επόπτης.
Λύση
Κάνουμε την εξής βασική παρατήρηση:
Παρατήρηση: Ο κάθε επόπτης ακολουθεί την μπάλα όσο είναι στο δικό του μισό, διαφορετικά βρίσκεται στη μέση.
Αυτό μπορούμε να το επιβεβαιώσουμε για τον πρώτο επόπτη κοιτώντας τις δυνατές περιπτώσεις για την μετακίνηση της μπάλας.
Επομένως, η θέση του πρώτου επόπτη τη στιγμή \(i\) είναι
\[x_1(i) = \min(Y_i, A/2).\]Συνεπώς, η συνολική μετακίνηση \(L_1\) του πρώτου επόπτη είναι
\[L_1 = \lvert x_1(1) - x_1(0)\rvert + \lvert x_1(2) - x_1(1)\rvert + \ldots + \lvert x_1(M) - x_1(M-1)\rvert = \sum_{i = 1}^M \lvert x_1(i) - x_1(i-1)\rvert,\]με την αρχική θέση να είναι \(x_1(0) = A/2\). Αντίστοιχα, η θέση του δεύτερου επόπτη είναι,
\[x_2(i) = \max(Y_i, A/2),\]και η συνολική του μετακίνηση \(L_2\) είναι,
\[L_2 = \lvert x_2(1) - x_2(0)\rvert + \lvert x_2(2) - x_2(1)\rvert + \ldots + \lvert x_2(M) - x_2(M-1)\rvert = \sum_{i = 1}^M \lvert x_2(i) - x_2(i-1)\rvert.\]με την αρχική θέση να είναι πάλι \(x_2(0) = A/2\). Ο παρακάτω κώδικας υλοποιεί αυτή τη λύση:
#include <algorithm>
#include <cstdio>
int main() {
FILE *fi = fopen("lines_man.in", "r");
long A, M;
fscanf(fi, "%ld%ld", &A, &M);
long x1 = A/2, x2 = A/2, total_x1 = 0, total_x2 = 0;
for (long i = 0; i < M; ++i) {
long cur_ball_pos;
fscanf(fi, "%ld", &cur_ball_pos);
long new_x1 = std::min(cur_ball_pos, A/2);
total_x1 += std::abs(new_x1 - x1);
x1 = new_x1;
long new_x2 = std::max(cur_ball_pos, A/2);
total_x2 += std::abs(new_x2 - x2);
x2 = new_x2;
}
fclose(fi);
FILE *fo = fopen("lines_man.out", "w");
fprintf(fo, "%ld %ld\n", total_x1, total_x2);
fclose(fo);
return 0;
}
Ο αλγόριθμος αυτός χρειάζεται \(\mathcal{O}(M)\) χρόνο και \(\mathcal{O}(1)\) μνήμη.
Σημείωση: Αν γνωρίζουμε τη συνολική μετακίνηση της μπάλας και την συνολική μετακίνηση του πρώτου επόπτη, τότε μπορούμε να υπολογίσουμε τη συνολική μετακίνηση του δεύτερου επόπτη με μία αφαίρεση (δείτε εδώ).