![]() |
![]() DAY 2 :: Task 3 :: Desciption Description in greek :: Solution :: Data sets Back to Day 2 problems - solutions - data sets TASK 3 - Word counting When Thales went on summer vacations to a distant island with his friend Archimedes, he had to find a way to entertain themselves as there were not many interesting things to do (apparently, the island was not Rhodes). At some point, Thales noticed that different words or phrases were written along the roads. Actually, some phrases did not make sense to him, but this did not prevent him from inventing the following game. To play the game, one just has to think out a word and count how many times it appears in the text along a specific road segment. After playing this game for some time, Thales found an easy way to count the appearances of a word, and decided to challenge himself with a harder game. Thales used a map of the area and marked all possible paths from their current position to the ports from where they could take a boat and return home. Interestingly, he noticed that although different paths might have a common origin, they never crossed after they separate and every path ended at a different port. Thus, the harder game was to count the different appearances of a chosen word along all the distinct paths. This is exactly your task. Input Your program should read the input from a file "wordcount.in". The first line of the file contains an integer N (where 2? N ?15.000) representing the number of lines to follow. The next N -1 lines contain data about the "nodes". All these nodes always form a tree structure. In particular, node 0 represents the origin, i.e. the place where a word to be counted is thought out. The remaining nodes (numbered with integers from 1 to N -1) represent road splits or ports. Thus, each of the following N -1 lines contains two integers representing two nodes, I and J (where 0? I , J ? N -1), and a text S of length L characters (where 1? L ? 1.000), describing a road from node I to node J , where I is always parent of the J , with the text along the road segment. Evidently, there is no road to node 0 and no road starting from a port. The last line of the file contains the word to be counted. Output Your program should write the output into a file "wordcount.out" containing only one integer for the number of distinct appearances of the word along all possible paths. Note : An appearance is identified by its start and end points, whereas the end point follows the start point along a path. An appearance exists only when the concatenation of consecutive letters from the starting point to the ending point (inclusive) forms exactly the word to be counted. An appearance is considered to be different from another one, if it has a different start or end point. All letters found are small, english language alphabet letters. 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 : 2 seconds Example (see figure)
Explanation . The four appearances can be extracted from the following parts of the paths: (0-7-6), (0-7-8), (0-7-2-5), (2-4)
DAY 2 :: Task 3 :: Desciption in greek Θέμα 3 - Μέτρηση λέξεων ( wordcount ) Όταν ο Θαλής πήγε καλοκαιρινές διακοπές σε ένα μακρινό νησί με τον φίλο του Αρχιμήδη, έπρεπε να βρει ένα τρόπο για να ψυχαγωγηθούν επειδή δεν υπήρχαν πολλά ενδιαφέροντα πράγματα για να κάνουν (προφανώς, το νησί δεν ήταν η Ρόδος). Κάποια στιγμή, ο Θαλής παρατήρησε ότι διαφορετικές λέξεις ή φράσεις είχαν γραφεί κατά μήκος των δρόμων. Βασικά, μερικές φράσεις δεν είχαν νόημα γι' αυτόν, αλλά αυτό δεν τον εμπόδισε στο να ανακαλύψει το ακόλουθο παιχνίδι. Για να παιχτεί το παιχνίδι, κάποιος απλά πρέπει να σκεφτεί μία λέξη και να μετρήσει πόσες φορές εμφανίζεται στο κείμενο κατά μήκος κάποιου συγκεκριμένου τμήματος δρόμου. Παίζοντας αυτό το παιχνίδι για κάποιο χρονικό διάστημα, ο Θαλής βρήκε έναν εύκολο τρόπο για να μετρά πόσες φορές μία λέξη εμφανιζόταν, και αποφάσισε να προκαλέσει τον εαυτό του με ένα πιο δύσκολο παιχνίδι. Ο Θαλής χρησιμοποίησε ένα χάρτη της περιοχής και σημάδεψε όλες τις πιθανές διαδρομές από την τοποθεσία που βρίσκονταν προς τα διάφορα λιμάνια από όπου μπορούσαν να πάρουν ένα πλοιάριο για να γυρίσουν στο σπίτι τους. Με έκπληξη πρόσεξε ότι παρόλο που διαφορετικές διαδρομές μπορούσαν να έχουν κοινό το σημείο αφετηρίας τους, στη συνέχεια, από τη στιγμή που χωρίζονταν ποτέ δεν διασταυρώνονταν και το κάθε μονοπάτι τερμάτιζε σε διαφορετικό λιμάνι. Έτσι, το δυσκολότερο παιχνίδι ήταν το να μετρήσουν τις διαφορετικές εμφανίσεις μιας επιλεγμένης λέξης κατά μήκος όλων των κατά μέρους ( distinct ) διαδρομών. Αυτό ακριβώς είναι το έργο σας. Είσοδος Το πρόγραμμα σας πρέπει να διαβάζει τα δεδομένα από το αρχείο εισόδου "wordcount.in". Η 1 η γραμμή από το αρχείο περιέχει 3 ακεραίους Ν (όπου 2? N ?15.000) ο οποίος αντιπροσωπεύει τον αριθμό των γραμμών που ακολουθούν. Οι επόμενες Ν-1 γραμμές περιέχουν πληροφορίες σχετικά με τους «κόμβους». Αυτοί οι κόμβοι πάντα σχηματίζουν μια δενδροειδή δομή. Συγκεκριμένα, ο κόμβος 0 αντιπροσωπεύει το σημείο αφετηρίας, δηλαδή το σημείο όπου μια λέξη που θα μετρηθεί σχηματίζεται ως σκέψη. Οι υπόλοιποι κόμβοι (αριθμημένοι με ακέραιους από το 1 ως το Ν-1) αντιπροσωπεύουν διακλαδώσεις δρόμων ή λιμάνια. Έτσι, κάθε μία από τις ακόλουθες Ν-1 γραμμές περιέχει δύο ακέραιους που αντιπροσωπεύουν δύο κόμβους, Ι και J (όπου 0?Ι, J ?Ν-1), και ένα κείμενο S μήκους L χαρακτήρων (όπου 1? L ?1.000), που περιγράφει ένα δρόμο από τον κόμβο I προς τον κόμβο J , όπου Ι είναι πάντα ο γονέας ( parent ) του J , με το κείμενο κατά μήκους του τμήματος δρόμου. Προφανώς, δεν υπάρχει δρόμος που να καταλήγει στον κόμβο 0 και κανένας δρόμος δεν ξεκινάει από λιμάνι. Η τελευταία γραμμή του αρχείου περιέχει τη λέξη που θα μετρηθεί. Έξοδος Το πρόγραμμα σας θα πρέπει γράφει τ o αποτέλεσμα στο αρχείο "wordcount.out" περιέχοντας μόνον έναν ακέραιο για τον αριθμό των εμφανίσεων της λέξης κατά μήκος όλων των πιθανών διαδρομών. Σημείωση: Μια εμφάνιση χαρακτηρίζεται από τα σημεία αφετηρίας και τερματισμού της, ενώ το σημείο τερματισμού ακολουθεί το σημείο εκκίνησης κατά μήκος της διαδρομής. Μια εμφάνιση υπάρχει μόνο όταν η συνένωση ( concatenation ) συνεχόμενων γραμμάτων από το σημείο εκκίνησης στο σημείο τερματισμού (συμπεριλαμβανομένου) σχηματίζει ακριβώς τη λέξη που θα μετρηθεί. Μια εμφάνιση θεωρείται διαφορετική από κάποια άλλη, εάν έχει διαφορετικό σημείο εκκίνησης ή διαφορετικό σημείο τερματισμού. Όλα τα γράμματα που βρίσκονται είναι πεζά (μικρά) και γράμματα της αγγλικής αλφαβήτου. Μορφή : Και στο input και στο output file, όλοι οι αριθμοί σε μια γραμμή ξεχωρίζουν με ένα μόνο κενό και όλες οι γραμμές τελειώνουν με ένα χαρακτήρα new line . Όριο Χρόνου : 2 δευτερόλεπτα Παράδειγμα
Εξήγηση . Οι τέσσερις εμφανίσεις μπορούν να βγουν από τα ακόλουθα τμήματα διαδρομών: (0-7-6), (0-7-8), (0-7-2-5), (2-4) DAY 2 :: Task 3 :: Solution This problem belongs to the family of string matching problems. The task is to count the different appearances of a chosen word along all distinct parts of paths of a tree structure that contains text in its edges. To solve the problem one should traverse the tree (not necessarily by building it) and use a string matching algorithm. In a brute force algorithm one scans the text that the path forms, while in an optimal solution the KMP algorithm can be used and in both cases identifies occurrences of the word to be counted. DAY 2 :: Task 3 :: Data sets
| ||||||||||
Organized by |
the Greek Computer Society |
and the |
|||||||||
![]() | |||||||||||
|