DAY 2 :: Task 1 :: Desciption

Description in greek :: Solution :: Data sets

Back to Day 2 problems - solutions - data sets

TASK 1 - Sailing race

In light of the forthcoming Balkan Olympic sailing cup in Rhodes Island, the organizing committee decided to come up with a new task for the competing boats to make the race even more mind-challenging. The committee placed a number of floating signs in a straight line, at various distances in the sea. All boats start concurrently from a specific point on this line and must visit all signs on the line. The race stops for each boat when all signs have been visited. To win, a boat must have visited all signs and covered the minimum sum of cumulative distances.

The cumulative distance of the first visited sign is the distance of the visited sign from the starting sign. The cumulative distance of all the rest visited signs is the distance from the previous sign plus the cumulative distance of the previous sign.

To help the crew understand the new race rules, the organizing committee labeled the starting sing as 0 (zero) and all other signs on the right of the starting sign with positive integers according to their distance from the starting sign. In the same manner, all signs on the left of the starting sign were given negative integer values according to their distance from the starting sign. Thus, if the signs are placed on the {-3,1,5} positions, then the sum of cumulative distances for the visiting order {-3,1,5} is 3+(4+3)+(4+7) = 21.

Your task is to write a program that (a) reads from the input file the sequence of signs based on their distances, (b) calculates the minimum sum of cumulative distances for some visiting order of the signs, and (c) writes the result to the file output.

For example, if the visiting order is {1, 3, 4, 10, -2, -5, -6, -9} the sum of cumulative distances is 1+3+4+10+ 22+25+26+29=120. The best order is {1, 3, 4, -2, -5, -6, -9, 10} with sum of cumulative distances 1+3+4+10+13+14+17+36=98.

Input

Your program should read the input from a file "sailrace.in". The first line of the file contains an integer L (where 1= L =200) representing the number of signs each boat must visit NOT including the starting sign. The second line contains the sequence of signs sorted in increasing order, excluding the starting sign. The range of distance of the signs is [-700, 700] and all distances are always integers.

Output

Your program should write the output into a file "sailrace.out" containing only one positive integer for the minimum sum of cumulative distances covered by a boat for a selected visiting order .

Example

sailrace.in
8
-9 -6 -5 -2 1 3 4 10

sailrace.out
98

Format : In both input and output files, all numbers in a line are separated with a single space and all lines terminate with a newline character.

Time limit: 4 seconds

back to top


DAY 2 :: Task 1 :: Desciption in greek

Θέμα 1 - Αγώνας Ιστιοπλοΐας ( Sailing race )

Εν όψει του επερχόμενου Βαλκανικού Ολυμπιακού κυπέλου ιστιοπλοΐας στο νησί της Ρόδου, η οργανωτική επιτροπή αποφάσισε να εισάγει μια νέα εργασία για τα αγωνιζόμενα σκάφη για να δώσει στον αγώνα μια πρόσθετη νοητική πρόκληση. Η επιτροπή τοποθέτησε έναν αριθμό επιπλεόντων πινακίδων σε ευθεία γραμμή, σε διάφορες αποστάσεις στη θάλασσα. Όλα τα σκάφη αρχίζουν ταυτόχρονα από ένα συγκεκριμένο σημείο σε αυτή τη γραμμή και πρέπει να επισκεφθούν όλες τις πινακίδες στη γραμμή. Ο αγώνας σταματά για κάθε σκάφος όταν έχει επισκεφθεί όλες τις πινακίδες. Για να νικήσει ένα σκάφος πρέπει να έχει επισκεφθεί όλες τις πινακίδες και να έχει καλύψει το ελάχιστο άθροισμα των αθροιζόμενων ( cumulative ) αποστάσεων.

Η αθροιζόμενη ( cumulative ) απόσταση της πρώτης επισκεφθείσας πινακίδας είναι η απόσταση της πινακίδας αυτής από την πινακίδα εκκίνησης. Η αθροιζόμενη ( cumulative ) απόσταση για όλες τις υπόλοιπες επισκεφθείσες πινακίδες είναι η απόσταση από την προηγούμενη πινακίδα συν την αθροιζόμενη ( cumulative ) απόσταση της προηγούμενης πινακίδας.

Για να βοηθήσουν το πλήρωμα να καταλάβει τους νέους κανόνες του αγώνα, η οργανωτική επιτροπή έβαλε επιγραφή 0 (μηδέν) στην πινακίδα εκκίνησης και σε όλες τις πινακίδες δεξιά από αυτή θετικούς ακέραιους, σύμφωνα με την απόστασή τους από την πινακίδα εκκίνησης. Κατά τον ίδιο τρόπο, σε όλες οι πινακίδες αριστερά της πινακίδας εκκίνησης έβαλαν αρνητικές ακέραιες, σύμφωνα με την απόστασή τους από την πινακίδα εκκίνησης. Έτσι, αν οι πινακίδες βρίσκονται στις θέσεις {-3,1,5}, τότε το άθροισμα των αθροιζόμενων ( cumulative ) αποστάσεων για τη σειρά επίσκεψης {-3,1,5} είναι 3+(4+3)+(4+7)=21.

Το έργο σας είναι να γράψετε ένα πρόγραμμα το οποίο (α) διαβάζει από το αρχείο εισόδου την ακολουθία των πινακίδων με βάσει των αποστάσεών τους, (β) υπολογίζει το ελάχιστο άθροισμα των αθροιζόμενων ( cumulative ) αποστάσεων για κάποια σειρά επίσκεψης των πινακίδων και (γ) γράφει το αποτέλεσμα στο αρχείο εξόδου.

Για παράδειγμα, αν η σειρά επίσκεψης είναι {1, 3, 4, 10, -2, -5, -6, -9} το άθροισμα των αθροιζόμενων ( cumulative ) αποστάσεων είναι 1+3+4+10+ 22+25+26+29=120. Η καλύτερη σειρά είναι {1, 3, 4, -2, -5, -6, -9, 10} με άθροισμα αθροιζόμενων (cumulative ) αποστάσεων 1+3+4+10+13+14+17+36=98.

Είσοδος

Το πρόγραμμά σας θα πρέπει να διαβάζει την είσοδο από το αρχείο " sailrace . in ". Η πρώτη γραμμή του αρχείου περιέχει έναν ακέραιο L (όπου 1? L ?200) που αντιπροσωπεύει τον αριθμό των πινακίδων που πρέπει να επισκεφθεί το κάθε σκάφος ΜΗ συμπεριλαμβανομένης της πινακίδας εκκίνησης. Η δεύτερη γραμμή περιέχει την ακολουθία πινακίδων ταξινομημένη κατά αύξουσα σειρά, εξαιρώντας την πινακί"α εκκίνησης. Το εύρος των αποστάσεων των πινακίδων είναι [-700,700] και όλες οι αποστάσεις είναι πάντα ακέραιοι αριθμοί.

Έξοδος

Το πρόγραμμά σας θα πρέπει να γράψει στο αρχείο εξόδου " sailrace . out ", το οποίο περιέχει έναν μόνο θετικό ακέραιο για το ελάχιστο άθροισμα αθροιζόμενων ( cumulative ) αποστάσεων που κάλυψε ένα σκάφος για μια επιλεγμένη σειρά επίσκεψης.

Παράδειγμα

sailrace.in
8
-9 -6 -5 -2 1 3 4 10

sailrace.out
98

Μορφή : Και στο input και στο output file, όλοι οι αριθμοί σε μια γραμμή ξεχωρίζουν με ένα μόνο κενό και όλες οι γραμμές τελειώνουν με ένα χαρακτήρα new line .

Όριο Χρόνου : 4 δευτερόλεπτα

back to top


DAY 2 :: Task 1 :: Solution

This problem is the Traveling Repairman Problem, a variation of the Traveling Salesman Problem. For the case that all points are in a line, the task is to calculate the minimum sum of cumulative distances for a visiting order of points and it can be solved using dynamic programming.

back to top


DAY 2 :: Task 1 :: Data sets

Download Data Sets

back to top


 

 

 

Organized by
the Greek
Computer Society

and the
University of the Aegean

under the auspices
of the Ministry of National Education and Relegious Affairs
design by Ad Hoc Applied Informatics Ltd