22ος ΠΔΠ Γ' Φάση
Get out (getout)

[40 Μονάδες]

Ένα τετράγωνος χώρος στάθμευσης (parking) αυτοκινήτων έχει μήκος πλευράς \(N\) μέτρα. Σε αυτόν βρίσκονται σταθμευμένα αυτοκίνητα διαστάσεων \(2\times 1\) μέτρα. Τα αυτοκίνητα είναι σταθμευμένα παράλληλα προς τις πλευρές του τετραγώνου και σε ακέραιες συντεταγμένες, άλλα οριζόντια (κατά μήκος σειρών) και άλλα κάθετα (κατά μήκος στηλών). Κάθε αυτοκίνητο μπορεί να μετακινείται μόνο κατά μήκος του άξονά του και μέσα στο τετράγωνο, εφόσον δεν εμποδίζεται από άλλο αυτοκίνητο, και δεν μπορεί να περιστρέφεται.

Η εταιρεία παροχής φυσικού αερίου θέλει να σκάψει κατά μήκος μίας οριζόντιας γραμμής (σειράς) στη θέση \(R\) μέσα στο χώρο στάθμευσης, για να περάσει έναν υπόγειο αγωγό. Για το σκοπό αυτό πρέπει να μετακινηθούν τα αυτοκίνητα που βρίσκονται πάνω σε αυτή τη σειρά.

Πρόβλημα

Nα αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο: Αφού διαβάσει το μήκος της πλευράς του τετραγώνου, τη θέση όπου θα τοποθετηθεί ο αγωγός, και τις θέσεις των σταθμευμένων αυτοκινήτων, θα υπολογίζει τον ελάχιστο αριθμό κινήσεων που απαιτούνται για να ελευθερωθεί η σειρά του αγωγού. Σε κάθε κίνηση μετακινείται ένα αυτοκίνητο κατά μήκος του άξονά του (εμπρός ή πίσω), μία ή περισσότερες θέσεις.

Aρχεία εισόδου

Τα αρχεία εισόδου με όνομα getout.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν δύο ακέραιους αριθμούς: το μήκος \(N\) της πλευράς του τετραγώνου (\(4 \leq N \leq 8\)) και τη θέση \(R\) της σειράς όπου θα τοποθετηθεί ο αγωγός (\(1 \leq R \leq N\)). Οι επόμενες \(N\) γραμμές περιγράφουν τα αυτοκίνητα που είναι σταθμευμένα οριζόντια, κατά μήκος των σειρών του τετραγώνου. Κάθε γραμμή αρχίζει με το πλήθος \(X_i\) των αυτοκινήτων που είναι σταθμευμένα κατά μήκος αυτής της σειράς, ακολουθούμενο από \(X_i\) ακέραιους αριθμούς: τις συντεταγμένες όπου βρίσκονται τα αυτοκίνητα κατά μήκος της σειράς. (Οι συντεταγμένες είναι μεταξύ \(1\) και \(N\). Ένα αυτοκίνητο οριζόντια σταθμευμένο με συντεταγμένη \(5\) βρίσκεται πάνω στις στήλες \(5\) και \(6\) του τετραγώνου.) Ομοίως, οι επόμενες \(N\) γραμμές περιγράφουν τα αυτοκίνητα που είναι τοποθετημένα κάθετα, κατά μήκος των στηλών του τετραγώνου.

Aρχεία εξόδου

Τα αρχεία εξόδου με το όνομα getout.out είναι αρχεία κειμένου με μόνο μία γραμμή που περιέχει μόνο έναν αριθμό: το ελάχιστο πλήθος κινήσεων. Αν δεν είναι δυνατόν να ελευθερωθεί η σειρά \(R\) για να τοποθετηθεί ο αγωγός, το αποτέλεσμα θα είναι \(-1\).

Παράδειγμα αρχείων εισόδου - εξόδου

getout.in	getout.out
5 4 2 2 4 0 1 2 0 0 1 3 0 1 4 1 3 0	4

Παράδειγμα

Εξήγηση παραδείγματος: Για να ελευθερωθεί η σειρά \(4\) του τετραγώνου, αρκεί να μετακινηθεί το αυτοκίνητο \(\Delta\) δύο θέσεις κάτω, μετά το \(Z\) μία θέση κάτω, μετά το \(\Gamma\) μία θέση αριστερά, και τέλος το \(Ε\) δύο θέσεις κάτω. Χρειάζονται επομένως \(4\) κινήσεις.